kenju's blog

About Programming and Mathematics

社内勉強会で "Dynamo: Amazon’s Highly Available Key-value Store" について発表した

Background

以前も書いたが、論文『Dynamo: Amazon's Highly Available Key-value Store』を読んだときに、Dynamo を手がかりに分散コンピューティングにおける Consistent Hashing や Quorum Model などのアルゴリズムについて知ることができた。

itiskj.hatenablog.com

そんな中、最近チームでAWS DynamoDB をチームで使う人が増えてきたり、Microservices な設計で分散コンピューティングの知見が設計時に求められてきたりしたので、この論文のサマリを伝えるという体をとりながら、基本的な概念について図や口頭での説明をしながら発表した。スライドに起こす過程で、論文の内容を復習することもできた。

「Consistent Hashing の図がわかりやすかった」「Merkle Tree は知らなかった」とか、「DDIA 面白そうですね」といった好評価ももらえたので、発表して良かったとも思う。

『仕事ではじめる機械学習』を読んで

仕事ではじめる機械学習

仕事ではじめる機械学習

本書を手にとって読んだのはだいぶ前になる(おそらく、紙版発売直後に購入した気がする)が、最近機械学習プロジェクトを ML team と合同で推進していることもあって、復習に読んでみた。

機械学習プロジェクトが日本で雨後の筍のように出現する中で、

  • ビジネスに組み込むときにどういう視点を持つべきか
  • そもそも機械学習を本当にする必要があるのか、しなくてよい道はないのか
  • 機械学習システムはレガシーでメンテナンスコストが高い、その将来性も見据えているか

といった、実際経験していないとなかなか言えない意見を丁寧に述べてある、貴重な本である。これを読めば、決して「明日から機械学習プロジェクトを推進できる」というわけではなく、むしろビジネスに組み込む前に「何を情報として持っておくべきか」「どのような判断時に、いかなる判断材料を揃えるべきか」といった観点を得るための本である。また、機械学習の各アルゴリズムについては軽く述べられてある程度であり、それは別の書籍でキャッチアップする必要があるが、現場に適用できるアルゴリズムのカタログとして、浅く広くキーワードを探りたい、といったときにも有用であろう。

Reading Notes

機械学習プロジェクトの流れ

  1. 問題を定式化する
  2. 機械学習をしないで良い方法を考える
  3. システム設計を考える
  4. アルゴリズムを選定する
  5. 特徴量、教師データとログの設計をする
  6. 前処理をする
  7. 学習・パラメータチューニング
  8. システムに組み込む

機械学習を用いるシステムの難しさ

  • 確率的な処理があるため、自動テストがしにくい
  • 長期運用していると、トレンドの変化などで入力の傾向が変化する
  • 処理のパイプラインが複雑になる
  • データの依存関係が複雑になる
  • 実験コードやパラメータが残りやすい
  • 開発と本番の言語・フレームワークがばらばらになりやすい

機械学習を含めたプロダクトをビジネスとして成功させる上で重要なメンバー

  • プロダクトに関するドメイン知識を持った人
  • 統計や機械学習に明るい人
  • データ分析基盤を作れるエンジニアリング能力のある人
  • 失敗しても構わないとリスクを取ってくれる責任者

Go Tips: Parse String or Int Type Array for JSON

Problem

時々、String / Integer が混ざった top level array な JSON を返す API に出くわすことがある。Web Socket で通信量を制限したいときなど、このような形をとるのだろうか。

[
  100,
  "type",
  "sub type",
  "unix timestamp"
]

自分であればこのような fragile な API は(本当にパフォーマンスが要求されない限り)設計しないだろうが、世の中に公開されている API がこのような形式になっていることも多い。そして、それを Go で Parse したいことも多い。

Solution

json.UnmarshalJSON がカスタマイズできることを利用する。例えば、" で始まるときは String、そうでないときは Integer であることを想定する。このロジック自体がだいぶ危険な香りがするが、interface{} で parse するよりは declarative である。

type StringOrInt string

func (soi *StringOrInt) UnmarshalJSON(b []byte) error {
    // when starting with ", it might be string
    if b[0] == '"' {
        return json.Unmarshal(b, (*string)(soi))
    }

    // if not, convert int to string
    var i int
    if err := json.Unmarshal(b, &i); err != nil {
        return err
    }
    str := strconv.Itoa(i)
    *soi = StringOrInt(str)
    return nil
}

Usage

message := new([]StringOrInt)
if err := c.ReadJSON(message); err != nil {
    log.Fataln("read:", err)
}
log.Printf("message=%+v\n", *message)

Go Tips: Declare KB/MB/GB/TB const in Go with iota & bit operation

Go のちょっとした Tips. https://www.udemy.com/go-fintech/ にて知った、KB/MB/GB/TB の const 定義のちょっとおもしろい方法。iota, bit operation について理解できればたやすい。

package main

import "fmt"

const (
    _ = iota
    KB int = 1 << (10 * iota)
    MB
    GB
    TB
)

func main() {
    fmt.Printf("KB: %d\n", KB)
    fmt.Printf("MB: %d\n", MB)
    fmt.Printf("GB: %d\n", GB)
    fmt.Printf("TB: %d\n", TB)
}

Output:

KB: 1024
MB: 1048576
GB: 1073741824
TB: 1099511627776

How does this work?

const 定義の部分は、省略しないならばこういう風にかける。

const (
    _ = iota
    KB int = 1 << (10 * iota)
    MB int = 1 << (10 * iota)
    GB int = 1 << (10 * iota)
    TB int = 1 << (10 * iota)
)

さらに、iota は 0 始まりの increment 数なので、

The values of iota is reset to 0 whenever the reserved word const appears in the source (i.e. each const block) and increments by one after each ConstSpec e.g. each Line https://github.com/golang/go/wiki/Iota

const (
    _ = 0
    KB int = 1 << (10 * 1)
    MB int = 1 << (10 * 2)
    GB int = 1 << (10 * 3)
    TB int = 1 << (10 * 4)
)

ということになり、結果として KB/MB/GB/TB の位上がりをうまく表現している。

蛇足で、bit operation は 2 進数でどうなっているかを見てみれば、慣れていない人でも理解できると思う。%b を渡して base 2 で出力させてみる。

fmt.Printf("KB: 1 << (10 * 1) = %b\n", 1 << (10 * 1))
fmt.Printf("MB: 1 << (10 * 2) = %b\n", 1 << (10 * 2))
fmt.Printf("GB: 1 << (10 * 3) = %b\n", 1 << (10 * 3))
fmt.Printf("TB: 1 << (10 * 4) = %b\n", 1 << (10 * 4))

Output:

KB: 1 << (10 * 1) = 10000000000
MB: 1 << (10 * 2) = 100000000000000000000
GB: 1 << (10 * 3) = 1000000000000000000000000000000
TB: 1 << (10 * 4) = 10000000000000000000000000000000000000000

『Go言語による並行処理』を読んで並行ストリーム処理のためのライブラリ "kenju/go-pipeline" を作り始めた

以下の記事で書いたように、『Go言語による並行処理』を読んだ。 第四章でストリーム処理のための言語パターンがいくつか紹介されていた。

itiskj.hatenablog.com

そこで、紹介されていたコードをベースに、いくつか自分なりの解釈を加えてライブラリ化した。

github.com

What's this?

書籍で紹介されていた機能に加えて、以下の機能を追加実装した。

  • interface だけではなく、string / int / float32 型それぞれのメソッドを用意
  • channel 間のキャンセルには独自の channel ではなく標準パッケージの context.Context 型を利用
  • Map, Reduce, Generator などのロジックも追加実装
    • Functional Programming な概念はストリーム処理と相性が良く、Map/Reduce があればかなり多くのロジックは組み立てることができるはず
  • CI/CD パイプラインのセットアップ
    • Circle CI を利用。go fmtgo lint も組み込んで開発を続けやすいように整えた

Documentation

最小限のドキュメントは godoc に書いてあるので、そちらを参照されたい。

https://godoc.org/github.com/kenju/go-pipeline

How to use this?

pipeline.Take

例えば、pipeline.Take の例。int 型のチャンネルを pipeline.GeneratorInt で生成し、任意の数を取得している。

ctx, cancel := context.WithCancel(context.Background())
defer cancel()

for v := range pipeline.TakeInt(ctx, pipeline.GeneratorInt(ctx, 1, 2, 3, 4, 5), 3) {
    fmt.Printf("%v ", v)
}

Output

1 2 3

pipeline.Map

string 型向けの pipeline.Map の使用例。channel から適宜渡されてくる string 型の値に対して、map function を適用していく。 これと pipeline.Reduce を組み合わせれば、簡単な MapReduce は書けると思う。

ctx, cancel := context.WithCancel(context.Background())
defer cancel()

mapFn := func(v string) string { return "**" + v + "**"}
for v := range pipeline.MapString(ctx, mapFn, pipeline.GeneratorString(ctx, "hello", "world")) {
    fmt.Println(v)
}

Output

**hello**
**world**

Example

以前、以下の記事で紹介したような、作業効率化のためのライブラリをメンテナンスしていたが、今回を機に concurrency 化した。その際に、go-pipeline を用いた。

itiskj.hatenablog.com

以下が使用箇所。go-groom では、pipeline.Takepipeline.FanIn を利用している。

https://github.com/kenju/go-groom/blob/c32ff7a37a8182497dd780f341b6de6da99b2c88/pipeline.go#L38

   pipelines := pipeline.Take(ctx, pipeline.FanIn(ctx, executionPipeline...), len(paths))
    for result := range pipelines {
        fmt.Printf(result.(execResult).Dir + "\n")
        if result.(execResult).Error != nil {
            fmt.Printf("\tError: %v\n", result.(execResult).Error)
        }
        fmt.Printf("\t" + result.(execResult).Out + "\n")
    }

Future's Work

基本的な機能については書ききったが、テストが書ききれていない。 また、latest version はまだ v0.1.2 であり、go-groom 以外の場所で適用の機会を探っていきながら、major を v1 にあげて production ready までもっていきたい。

『Go言語による並行処理』を読んで

Go言語による並行処理

Go言語による並行処理

Background

Go でパフォーマンスが求められる Microservices を書く計画が来期あるので、並行処理に対する知見を深めておく目的で読んだ。

My Impression

本書を読んで一番良かった点は、第四章デザインパターンと第六章の goroutine の内部実装に関する章を読めた点。

まず、デザインパターンについては、エラーハンドリングやパイプライン、Queue や orDone などの実務でよくあるパターンについて、実際のコードと共に書かれてある点が非常に参考になった。

また、goroutine の内部実装については、ワークスティーリングや継続の概念について説明しながら、Go が goroutine をタスク、その後の計算処理を継続として扱い、プロセッサ(コンテキスト、P)間で継続を盗み合うことで最適化を実現している点を理解することができた。特に、OS スレッド(マシン、M)が、コンテキストを引き離して管理することで、他のブロックされていない OS スレッドに処理を引き渡しながら、全体としてホストマシンの CPU を余すところなく動かし続けることができる理由を理解することができた。

第二に、適宜 Benchmark をとりながら、パフォーマンスについて議論している点が信頼できた。現場では当たり前だが、一般論や感覚で論を進めるのではなく、データドリブンで、かつ再現性のあるベンチコードを載せながらいかに goroutine が性能を向上させるのかについて語られている点が、読んでいて気持ちよかった。

Japanese Edition v.s. Original English Edition

一次ソースにあたることを普段から意識しているので、最初はオリジナルの英語版を Kindle で購入するつもりだった。しかし、Twitter 上での日本語版への評判が良かった点、翻訳者やレビュアーの Go 開発者の方々はもともと Go を書いている中で知っていた点、日本語版 PDF が英語版の Kindle とかなり値段の差があった点を受けて、日本語版を購入した。

結果として、これが非常に良かった。というのも、本書内に随時訳注が記載されているのだが、本書の間違いを指摘したり、足りない点を補足したり、ソースコードエビデンスを取りに行ったりしており、その点英語版には無いであろうから得をした気分。

How did I read this?

まず、一通り読みながら、第三章および第四章に関しては、実際に手を動かしながら読み進めていった。やはり、手を動かさないとわからないこともある。

すべてのソースコードGitHub で公開されているので、そちらも参照されたい。

Keywords

Implementation

  • atomic package
    • atomic.AddInt32
    • atomic.LoadInt32
  • sync package
    • sync.WaitGroup
    • sync.Mutex
    • sync.RWMutex
    • sync.Cond
    • sync.NewCond
    • sync.Once
    • sync.Pool
  • context package
    • context.Context
    • context.BackGround()
    • context.WithCancel
    • context.WithTimeout
    • context.WithDeadline
  • runtime
    • runtime.GOMAXPROCS

2018 年振り返り

今年も 2018 年を振り返ってみる。

itiskj.hatenablog.com

Jobs

社会人人生、最も成果を出せて、かつ最も成長した一年だったと振り返っている。この一年だけでも、かなり多くのチャレンジができたし、それに見合う評価もしてもらった。

メインの仕事しては、以下の通り。我ながら頑張ったと思う。もちろん、支えてくれる家族や、サポートしてくれるチームメンバーやリーダーの力があったから。

  • 広告配信最適化による CT 目標ベースでの自動配信システムの構築
  • ネットワーク広告改善施策 (link)
  • Python を用いたリアルタイムログ基盤の保守・運用
  • AWS x Go を用いたリアルタイムログ基盤のフルスクラッチ開発 (link)
  • DMP (Data Management Platform) を活用したターゲティング機構の開発
  • BFF/GraphQL/React を用いた大規模なレガシーアプリケーションのリアーキテクチャリング
  • TV CM 施策のための Go/gRPC buffering の性能試験実施
  • 在庫割当問題の Linear Programming 問題を適用した最適化システムの構築
  • 小規模な Rails Application のフルスクラッチ開発
  • 20 % ルールを活用した社内ライブラリのリファクタリング

後半からは広告チームのチームリーダーも経験させてもらって、メンバーの成長やチーム開発での成果に責任をもつようにもなった。基本的に僕はマネジメントスキルを磨いていくつもりはなく、Technical Specialist として Tech Lead や Engineering Lead としてキャリアを進めていくつもりなんだけれど、このタイミングでリーダーを任せてもらったことは、後にも先にもない機会だし、ありがたいと感謝している。 更に、来年はグループリーダーとしてチャレンジさせて貰える機会ももらったので、更に今の部長から多くを学んでいきたいし、成果として目に見える形で恩を返していきたいとも思っている。

Presentation

2017 年と打って変わって、たくさんの外部発表の機会があった。発表のための発表もほとんどなく、基本的には仕事の成果を発表する機会としてチャレンジできた。外部発表するためにはある程度の成果も出す必要があって、いい感じのサイクルが回っていたように思う。特に TOKYO Rails Meetup #37 で、完全に英語で 20 分の発表をした機会は、自分の殻を打ち破る思い出深い発表でもあった。

Books

今年一番の出会いは、なんといっても "Designing Data-Intensive Applications". 存在自体は 2017 年から知っていたのだが、社内勉強会に後押しされて読み始めた。これが最高に良かった。分散システムを作る地道で泥臭い努力や、枯れたアルゴリズムから最新の研究成果まで、幅広く網羅されている学術よりの教科書。実際に手を動かしてみないとわからないものは多いものの、分散システムや Microservices を設計し開発していく僕らにとって避けては通れない一冊。この本との出会いが、自分がエンジニアとして進んでいきたい道を明らかにしてくれたという意味でも、2018 年ベストの一冊。

itiskj.hatenablog.com

次に痺れた本としては、『The Hardware Hacker』。著者のハードウェア開発における半生が最高にロックで、読んでてこんなにページをめくるのが楽しい本は初めてかもしれない。一気に通読した。僕は Software Engineer だけれども、物を作りたい、裏側を知りたい、そして自分の思う通りにハックしたいという哲学や精神には通ずるところがあって、心躍る一冊だった。

itiskj.hatenablog.com

"Writing An Interpreter in Go" は、技術書の中ではダントツで面白かった。SICP などコンパイラインタプリタを開発する書籍はたくさんある中で、現場で比較的使われている言語で、初学者にとってもわかりやすくインタプリタの概念を説明しながら、スクラッチインタプリタを開発していくスタイルが気に入った。ちょうど当時は Go を初めて仕事で開発していたこともあって、Go の勉強がてらにも用いた。

itiskj.hatenablog.com

番外編だが、"Winny の技術" も外せない。Distributed Computing の文脈から、P2P とその周辺技術に興味が出てきて調べていく過程で出会った本。著者の天才性、発送の独創性、それを形にしてしまうプログラミング能力を兼ね備えた人物は、本当に稀有だったのだろう。

itiskj.hatenablog.com

その他、オンラインゲームやキャリアパスを考えるための書籍あたりも印象に残っている。

Thesis

今年は、年で 40 ~ 50 本近くの論文を読めた。週で数十本読んでいる本職の人には敵わないけれど、読みたいと思った論文はなんやかんや時間を見つけて読めたので良かった。仕事の延長で、広告配信最適化や CTR 予測の文脈から派生して読んだ本数が一番多かった。次に、"Designing Data-Intensive Application" を読んでいる途中であげられた参考文献を読んだ本数が多かった。

一番面白かったのは、Google Ad で使用されている Photon の論文。これをきっかけにストリーム処理系に興味が出たし、その後の"cookpad storeTV の広告配信を支えるリアルタイムログ集計基盤" の仕事につながった。

itiskj.hatenablog.com

普段から割とヘビーに使っている AWS DynamoDB のアーキテクチャにまつわる論文も面白かった。いかに高可用性・高信頼性のある分散データシステムを作るかという点で、実務の観点から非常に参考になる論文だった。

itiskj.hatenablog.com

Spark Streaming で用いられている micro batching の手法、D-Streams の論文もためになった。ストリーム処理系では、リアルタイム性を担保しながら、分散システムにおける典型的な信頼性担保の手法のほかにも考えることが山ほどある。Apache Kafka や Apache Spark (Streaming), Apache Flink あたりの documents を読んでいると、ストリーム処理系における典型的な課題に対してどう解決しているかが参考になった。そのうちの一つ。

itiskj.hatenablog.com

Weekend Projects

本業が絶好調だった一方で、趣味開発の時間では目立ったせいかはなかった。社内で開発した一部を OSS で公開したり、eslint-plugin-compat のメンテナになったりしたけれど、個人的にはもっと大きな成果を出したかった。

とはいえ、本業での成果がきちんと外部でも評価されたし、何より本業でのコーディングが楽しかったので、良しとした。とはいえやはり、来年はここで一つ狙っていこうと思っている。

Game

昨年はゼルダに傾倒していたけれど、秋口くらいまでは仕事と子育てで全く余裕がなかった。ただ、秋すぎくらいにドラゴンクエストビルダーズ 1 for Switch を購入し、息抜きにプレイする時間は増えた。

このドラゴンクエストビルダーズが、もともと LEGO 好き人間としてはドハマリしてしまって、頭で考えた設計図を限られたリソースの中で、いかにクリエイティブに作るか、という面白みに熱狂してしまった。

メインクエスト自体はまだまだ進める余地があるので、しばらく遊べそう。

『作って動かす ALife』を読んで

作って動かすALife ―実装を通した人工生命モデル理論入門

作って動かすALife ―実装を通した人工生命モデル理論入門

Background

先日、『Winny の技術』という P2P ネットワークの技術書を読んだ。

itiskj.hatenablog.com

その本は P2P 及び Winny の技術的背景がメインのトピックなのだが、著者がもともとは人工知能やシュミレーションに造詣が深かったらしく(むしろ P2P よりそちらが本業)、Winny を作り上げた際に数千台の Node をシュミレーション実験し、性能試験を行うという一節があった。

P2P、ひいては自律分散型のネットワークにおけるコンピュータは、まるで生き物のようなだなと感じることがある。一つ一つの行動理論は、人の手によって書かれたプログラムに基づくルールベースかもしれない。しかし、そんなコンピュータが数千台、数万台も集まって、相互に干渉しながら行動するとき、全体としての動きが有機的でカオス性を帯びてきて、まるで生き物のような、群れをなしたような動きをする。

そんな妄想をしていたところに、ちょうど飛び込んできたのがこの本だった。もともと店頭で目にしたことはあり、いつかは読んでみたいと思っていたところ。最近仕事で非常に簡単な機械学習アルゴリズム(一種の最適化問題)を Python で実装していたり、先に述べたような自律分散型ネットワークにおけるシュミレーションへの興味関心などもあいまって、気づいたら購入していた。

Impression

Artificial Life, 通称 ALife の入門書とも言える。Python によるプログラムは最小限で、GitHub から落としてすぐに手元で動かせることを念頭に置かれており、ハンズオン形式で手を動かして何かを作り上げるタイプの本ではない。誤植は見かけなくはないが、もともと日本語で出版されているということもあり、誤訳や違和感のある訳によって読み心地が損なわれる、ということはない。

「生命とは何か」という究極の問いに答えるべくして形成された ALife という学問体系を、過去の数学者の理論の変遷や、最近のロボティクス界隈の事例を踏まえながら浅く広く紹介している。この本を通して「ALife 面白い、もっと学んでみたい」という人が増やしたいという思いが伝わってくるような、初心者にも易しく、それでいて丁寧な文章が続いている。

そして、自分のその一人となった。

ALife、すごくエキサイティングな分野だと思う。もちろん生命の行動をほぼ完全にシュミレーションできる時代はまだ先だろうが、少なくとも数年、十数年以内に ALife から創発されたプロダクトや"生命体"を日常生活で見ることはもっと増えてくるのではないだろうか。iRobotics のように商業的に成功している事例もすでにある。それでいて、哲学的・存在論的な問を突き詰めるという非常に理論的な分野でもある。

もともとは自律分散型ネットワークの俯瞰的な行動体型を観察する手法の一つとして、生命に擬似させたシュミレーションは面白いのではないかと思っていたということもあり、ヒットした。しばらく、自分の脳内から離れないだろう。

Keywords

Integrate CSRF Protection of Rails with Apollo Client (GraphQL)

If you want to integrate CSRF Protection of Rails with Apollo, here is the step:

  • simply get the token from meta[name=csrf-token] with document.querySelector
    • this is basically embedded with csrf_meta_tags
  • append it to headers of Apollo Link
    • separate authentication logic to middleware, if you like

Example Implementation

The Middleware pattern are introduced by Apollo's official document

https://www.apollographql.com/docs/react/advanced/network-layer.html

Of course, you can simply write the headers values into HttpLink constructor's options directly.

import React from 'react';
import PropTypes from 'prop-types';

import { ApolloProvider } from 'react-apollo';
import { ApolloClient } from 'apollo-client';
import { HttpLink } from 'apollo-link-http';
import { InMemoryCache } from 'apollo-cache-inmemory';
import { ApolloLink, concat } from 'apollo-link';

const httpLink = new HttpLink({ uri: '/graphql' });
const authMiddleware = new ApolloLink((operation, forward) => {
  operation.setContext({
    headers: {
      'X-CSRF-Token': document.querySelector('meta[name=csrf-token]').getAttribute('content'),
    },
  });
  return forward(operation);
});

const client = new ApolloClient({
  link: concat(authMiddleware, httpLink),
  cache: new InMemoryCache(),
});

export default class GraphQLProvider extends React.Component {
  static propTypes = {
    children: PropTypes.node.isRequired,
  }

  render() {
    return (
      <ApolloProvider client={client}>
        {this.props.children}
      </ApolloProvider>
    );
  }
}

Simple Pager PoC for Relay Connection Specification

Background

In order to implement pagination, there are mainly 2 types of methods:

  1. Offset-based
  2. Cursor-based
    • Relay-style cursor connection is one of cursor-based specifications

Cursor-based works well with streaming-like user interfaces (e.g. timeline of Twitter), and Offset-based does with simple pagination with page number.

Relay describes "Cursor Connection" Specification.

Here is an example of the GraphQL query.

query audiences($cursor: String) {  
  users(first: 80, after: $cursor) {
    edges {
      cursor
      node {
        id
        name
      }
    }
    pageInfo {
      startCursor
      endCursor
      hasNextPage
      hasPreviousPage
    }
  }
}

However, sometimes you are required to implement page-number supported pagination with Cursor Connection. This requires more work and inconsistent architecture, so basically you should avoid this case. Just for who you need this, here is an PoC of page-number supported pagination with Cursor Connection specification.

PoC

GraphQLProvider

GraphQLProvider is an abstraction as an GraphQL client. We use Apollo Client in this case, but any client can go with it.

import React from 'react';
import PropTypes from 'prop-types';

import { ApolloProvider } from 'react-apollo';
import { ApolloClient } from 'apollo-client';
import { HttpLink } from 'apollo-link-http';

const client = new ApolloClient({
  link: new HttpLink({ uri: '/graphql' }),
});

export default class GraphQLProvider extends React.Component {
  static propTypes = {
    children: PropTypes.node.isRequired,
  }

  render() {
    return (
      <ApolloProvider client={client}>
        {this.props.children}
      </ApolloProvider>
    );
  }
}

QueryProvider

QueryProvider is an abstraction layer for GraphQL query operations. Loading and ErrorMessage components can be anything you want.

import React from 'react';
import PropTypes from 'prop-types';
import qql from 'graphql-tag';
import { Query } from 'react-apollo';

import Loading from 'components/atoms/Loading';
import ErrorMessage from 'components/atoms/ErrorMessage';
import GraphQLProvider from 'components/providers/GraphQLProvider';

export default class QueryProvider extends React.Component {
  static propTypes = {
    query: PropTypes.string,
    render: PropTypes.func,
  };

  render() {
    return (
      <GraphQLProvider>
        <Query query={qql(this.props.query)}>
          {({ loading, error, data, fetchMore }) => {
            if (loading) {
              return <Loading></Loading>;
            }

            if (error) {
              console.error(error);
              return <ErrorMessage></ErrorMessage>;
            }

            return this.props.render(data, fetchMore);
          }}
        </Query>
      </GraphQLProvider>
    );
  }
}

PaginationProvider

PaginationProvider is an abstraction layer for pagination with Cursor Connection Specification. This has the core logic of handling pagination algorithm with Cursor Connection.

import React from 'react';
import PropTypes from 'prop-types';

import QueryProvider from 'components/providers/QueryProvider';
import Pager from 'components/atoms/Pager';

export default class PaginationProvider extends React.Component {
  static propTypes = {
    query: PropTypes.string.isRequired,
    connectionName: PropTypes.string.isRequired,
    render: PropTypes.func.isRequired,
  };

  render() {
    return (
      <QueryProvider
        query={this.props.query}
        render={(data, fetchMore) =>
          <InnerPaginationProvider
            connection={data[this.props.connectionName]}
            connectionName={this.props.connectionName}
            fetchMore={fetchMore}
            render={this.props.render}
          >
          </InnerPaginationProvider>
        }
      ></QueryProvider>
    );
  }
}

class InnerPaginationProvider extends React.Component {
  static propTypes = {
    connection: PropTypes.object,
    connectionName: PropTypes.string.isRequired,
    fetchMore: PropTypes.func,
    render: PropTypes.func.isRequired,
  };

  constructor(props) {
    super(props);
    this.state = {
      connection: [],
      endCursors: [this.props.connection.pageInfo.endCursor],
      page: 1,
    };
  }

  componentDidMount() {
    this.updateConnection(this.props.connection);
  }

  updateConnection(con) {
    this.setState({ connection: con.edges.map(edge => edge.node), });
  }

  incrementPage() {
    this.setState({ page: this.state.page + 1, });
  }

  decrementPage() {
    this.setState({ page: this.state.page - 1 });
  }

  /**
   * Append endCursor to this.state.endCursors uniquly
   */
  appendEndCursors(pageInfo) {
    const appended = this.state.endCursors.some(cur => cur === pageInfo.endCursor);
    if (!appended) {
      this.setState({ endCursors: this.state.endCursors.concat(pageInfo.endCursor) });
    }
  }

  onClickPrevButton() {
    // do nothing if on the first page
    if (this.state.page == 1) {
      return;
    }

    let cursor;
    if (this.state.page == 2) {
      /*
       * Pass null to start from the starting point.
       * doc (https://www.apollographql.com/docs/react/features/pagination.html#relay-cursors) says:
       * > If null is passed for the cursor relay will ignore it and provide results starting from the beginning of the data set
       */
      cursor = null;
    } else {
      cursor = this.state.endCursors[this.state.page - 3];
    }

    this.props.fetchMore({
      variables: { cursor, },
      updateQuery: (previousResult, { fetchMoreResult }) => {
        const newConnection = fetchMoreResult[this.props.connectionName];
        if (newConnection.edges.length > 0) {
          this.updateConnection(newConnection);
          this.decrementPage();
        }
        return previousResult;
      },
    });
  }

  onClickNextButton() {
    this.props.fetchMore({
      variables: {
        cursor: this.state.endCursors[this.state.page - 1],
      },
      updateQuery: (previousResult, { fetchMoreResult }) => {
        const newConnection = fetchMoreResult[this.props.connectionName];
        if (newConnection.edges.length > 0) {
          this.updateConnection(newConnection);
          this.incrementPage();

          this.appendEndCursors(newConnection.pageInfo);
        }
        return previousResult;
      },
    });
  }

  render() {
    return (
      <React.Fragment>
        <Pager
          onClickPrevButton={() => this.onClickPrevButton()}
          onClickNextButton={() => this.onClickNextButton()}
          page={this.state.page}
        ></Pager>
        {this.props.render({ connection: this.state.connection })}
      </React.Fragment>
    );
  }
}

Pager

Pager component is a simple pagination buttons. You can decorate as like as you want with CSS.

import React from 'react';
import PropTypes from 'prop-types';

export default class Pager extends React.Component {
  static propTypes = {
    page: PropTypes.number.isRequired,
    onClickPrevButton: PropTypes.func,
    onClickNextButton: PropTypes.func,
  };

  render() {
    return (
      <div>
        <button className='button btn-default' onClick={() => this.props.onClickPrevButton()} >Prev</button>
        <button className='button btn-default' onClick={() => this.props.onClickNextButton()} >Next</button>
        <span> page {this.props.page}</span>
      </div>
    );
  }
}

Usage

Here is an example of usage of the PaginationProvider.

const query = () => `
query users($cursor: String) {
  users(first: 20, after: $cursor) {
    edges {
      cursor
      node {
        id
        name
      }
    }
    pageInfo {
      startCursor
      endCursor
      hasNextPage
      hasPreviousPage
    }
  }
}
`;

export default class UsersList extends React.Component {
  render() {
    return (
      <PaginationProvider
        query={query()}
        connectionName='users'
        render={({ connection }) =>
          <UsersListItem users={connection} />
        }
      >
      </PaginationProvider>
    );
  }
}

How to Integrate Rails with React.js

Rails application で React.js を render したいときの、ちょっとした Tips.

基本戦略

  • React component 専用に data-react-class のような data attributes を定義する
  • data-react-class 属性のついた document element を見つけ、Dynamic Import で該当クラスを import
  • ^ らへんの規約は ViewHelper に隠蔽し、form_authenticity_token なども ViewHelper 経由で渡す
  • props は data-reactPropsJSON で受け渡す

PoC

ViewHelper

React components は、基本的に ComponentHelper#render_react_component を用いることとする。

module ComponentHelper
  def render_react_component(name, props: {}, options: {}, &block)
    # ここに共通で渡したい props を定義する
    react_props = props.reverse_merge(
      authenticity_token: form_authenticity_token,
      signed_in: user_signed_in?,
    )
    html_options = options.reverse_merge(
      data: {
        react_class: name,
        react_props: (react_props.is_a?(String) ? react_props : react_props.to_json),
      },
    )
    content_tag(:div, '', html_options, &block)
  end
end

View

ComponentHelper#render_react_component を呼び出すだけ。

= render_react_component(:MyComponent,
    props: { foo: bar },
    options: { id: 'my-component' })

JavaScript

共通 layout とかから読み込ませる。

import React from 'react';
import ReactDOM from 'react-dom';

// ここに React Component を追加していく
const componentMap = {
  MyComponent: import("../components/MyComponent"),
};

// data-react-props 経由で渡された JSON String を parse する
function parseProps(container) {
  let props;
  try {
    props = JSON.parse(container.dataset.reactProps);
  } catch (e) {
    console.error(e);
  }
  return props;
}

// 該当する React component を Dynamic Import して mount する
async function mount(container) {
  const componentName = container.dataset.reactClass;
  if (componentMap.hasOwnProperty(componentName)) {
    console.time(componentName);

    const componentModule = await componentMap[componentName];
    const ComponentType = componentModule.default;
    const props = parseProps(container);
    const component = <ComponentType {...props} />;

    ReactDOM.render(component, container, () => {
      console.timeEnd(componentName);
    });
  } else {
    console.error(`No component registered: ${componentName}`);
  }
}

// 特定の data attributes がついた全 document element を走査し、mount する
async function mountAll() {
  for (const container of document.querySelectorAll('*[data-react-class]')) {
    mount(container);
  }
}

// jQuery の $(() => { ... }) と同じ意味
// ref. http://youmightnotneedjquery.com
if (document.readyState !== 'loading') {
  mountAll();
} else {
  document.addEventListener('DOMContentLoaded', domLoadedHandler);
}

Manage .tfstate with `terraform state` subcommands

terraform supports terraform state subcommands for state file management.

Use Case 1: Visualize Your State

To list all resources, use state list:

$ terraform state list
aws_api_gateway_rest_api.TestAPI
aws_lambda_function.test_function
...

In order to look upon each resources' details, state show is handy:

$ terraform state show aws_api_gateway_rest_api.TestAPI
id        = ***
action = ***
...

Use Case 2: Remove Orphan Resources from .tfstate

When you run terraform apply and error occurs, some resources can be orphan resources. They exists in .tfstate file, but they are not more supposed to manage via terraform.

In such cases, use state rm to remove items from .tfstate file:

$ terraform state rm aws_api_gateway_rest_api.TestAPI

Be sure that those resources are not physically destroyed. In such case, use terraform destroy instead.

Items removed from the Terraform state are not physically destroyed. Items removed from the Terraform state are only no longer managed by Terraform. For example, if you remove an AWS instance from the state, the AWS instance will continue running, but terraform plan will no longer see that instance.

Use Case 3: Upload a local .tfstate to Remote State

This is where state push command comes in.

First, declare your backend in any .tf files:

terraform {
  backend "s3" {
    bucket = "my-bucket"
    key    = "key/terraform.tfstate"
    region = "ap-northeast-1"
  }
}

And then, run below command to push your local .tfstate to the specified backend:

$ terraform state push ./terraform.tfstate

You can use state pull to download the state from remote state.

$ terraform state pull > ./terraform.tfstate

『Winny の技術』を読んで

Winnyの技術

Winnyの技術

How to buy?

"達人出版会" で PDF を購入できる。Amazon だと中古のものしか売っていなかった。

Background

最近 "DDIA" を読んだこともあり、Distributed Computing について興味を持ち、論文を読んでみたり PoC を書いてみたりしていた。Consistent Hashing や Merkle Tree, Distributed Hash Table (DHT) など。

itiskj.hatenablog.com

その過程で、分散ノード間における情報伝達の技術が、P2P 技術でも実用に耐えうるレベルで開発・研究されてきたことを知った。したがって、自然な流れとして P2P 技術についても調べてみようと Wikpedia やネットをあさっていたところ、この本にたどり着いた。

もちろん Winny金子勇氏については以前から知っていたこともあり、これを機会に P2P の技術的背景について調べてみようという機運が高まった。

My Impression

2005 年にこの本が書かれたという事実、当時 P2P 技術がここまで発展していたという事実に驚愕を受けた。書籍の説明も、明快な図やコンセプト、適切な比喩や設計上の工夫・失敗談も書かれており、一エンジニアとしても刺激を受ける内容であった。

P2P 技術という意味では、プロトコルや使用技術は古いのかもしれない(要調査)が、少なくとも今の自分にとっては必要な技術を、わかりやすく説明してくれたという意味で、今良くべき本だったのかもしれない。あまりに内容が面白すぎて、一晩で一気に読み終えてしまった。

Keywords

  • Napster / Gnutella / Freenet / Winny
  • 上流・下流にノードを分割するコンセプト
  • キャッシュファイル・ダウンロードファイル・アップロードファイル
  • 検索キーワードをベースにしたノード間のクラスタリング
  • オーバーレイネットワーク
  • 検索(検索リンク・拡散クエリ・検索クエリ)
  • ノード管理・クエリ管理・キー管理・タスク管理
  • 自動ダウンロード機構
  • 無視フィルタ機構
  • 多重ダウンロード
  • 数千ノードのシュミレーション
  • キャッシュシステム
  • キャッシュファイルヘッダ
  • キーの上書き
  • タイマーを用いたキーの寿命管理
  • 「中継」を用いた匿名性の担保
  • プロキシ
  • クラスタリング(一次元トーラス)

Introduction to Consistent Hashing and PoC in Ruby

What's Consistent Hashing?

https://en.wikipedia.org/wiki/Consistent_hashing

  • one of hashing methods
  • it was originated from the paper from MIT in 1997

Why You Need Consistent Hashing

  • effective way to handle multiple computers node over distributed networks

When to Use Consistent Hashing

  • cashing over distributed nodes
  • load balancing over multiple servers
  • store some data over multiple distributed computers

Improved Consistent Hashing

Read https://medium.com/@dgryski/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8 for more details.

PoC

Implementation

require 'digest'

class HashFunc
  def initialize
    @func = lambda{|x| Digest::SHA256.digest(x) }
  end

  def call(x)
    @func.call(binarize(x))
  end

  private

  def binarize(x)
    if x.is_a?(Integer)
      x.to_s(2) # make it binary
    elsif x.is_a?(String)
      x
    else
      raise "Unsupported Type: #{x.class}"
    end
  end
end

class Ring
  attr_reader :nodes
  def initialize(hash_func)
    @nodes = []
    @hash_func = hash_func
  end

  def add_node(id)
    @nodes << Node.build(id, @hash_func)
    @nodes = nodes.sort
  end

  def get(key)
    hashed = @hash_func.call(key)
    # TODO: implement virtual id for load-balancing
    found = @nodes.find {|node| node.hash_id >= hashed }

    if found
      found.id
    else
      # when not found the appropriate node, return the first node
      @nodes.first.id
    end
  end
end

class Node
  class UnboundedIDError < StandardError; end

  ID_RANGE = (0..2**32)

  def self.build(id, hash_func)
    unless ID_RANGE.include?(id)
      raise UnboundedIDError.new("id=#{id}, range=#{ID_RANGE}")
    end

    hash_id = hash_func.call(id)
    new(id, hash_id)
  end

  # id is commonly ranged from 0 ~ 2^32
  attr_reader :id, :hash_id
  def initialize(id, hash_id)
    @id = id
    @hash_id = hash_id
  end

  def <=>(another)
    id <=> another.id
  end
end

Usage

hash_func = HashFunc.new
ring = Ring.new(hash_func)

node_ids = [
  0,
  2 ** 1,
  2 ** 8,
  2 ** 16,
  2 ** 24,
]
node_ids.each {|id| ring.add_node(id) }

pp ring

[
  "foo",
  "bar",
  "buz",
  100,
  -500,
  99999999,
].each {|data|
  puts "Node ID for #{data} ... #{ring.get(data)}"
}

Introduction to the Merkle Tree

https://en.wikipedia.org/wiki/Merkle_tree

What's the Merkle Tree?

  • a tree-like data structure
  • every leaves is labelled with the hash of a data block
  • every node is labelled with the cryptographic hash of the labels of its child nodes

Why You Need the Merkle Tree?

  • faster to check the equality between different objects
  • save more time & spaces to calculate checksums

When to Use Merkle Tree

  • P2P
  • Crypto Currency
  • Distribution Computing
  • etc.

According to the Wikipedia page:

Hash trees are also used in the IPFS, Btrfs and ZFS file systems[4] (to counter data degradation[5]); Dat protocol; Apache Wave protocol[6]; Git and Mercurial distributed revision control systems; the Tahoe-LAFS backup system; Zeronet; the Bitcoin and Ethereum peer-to-peer networks[7]; the Certificate Transparency framework; and a number of NoSQL systems such as Apache Cassandra, Riak, and Dynamo.[8] Suggestions have been made to use hash trees in trusted computing systems.[9]

PoC

Implementation

# PoC of Merkle Tree
#
# Documentation:
# https://en.wikipedia.org/wiki/Merkle_tree
#
# Usage:
# Merkle trees can be used to verify any kind of data stored,
# handled and transferred in and between computers.

require 'digest'

class MerkleNode
  include Enumerable

  attr_reader :left, :right, :data, :hashed
  def initialize(left, right, data = nil)
    @left = left
    @right = right
    @data = data
    @hashed = hash_data(data)
  end

  def each(&block)
    block.call(data)
    if left?
      left.each(&block)
    end
    if right?
      right.each(&block)
    end
  end

  def leaf?
    left.nil? && right.nil? && !data.nil?
  end

  def node?
    !leaf?
  end

  def left?
    !left.nil?
  end

  def right?
    !right.nil?
  end

  def ==(other)
    hashed == other.hashed
  end

  private

  def hash_data(data)
    if leaf?
      hash(data)
    elsif node?
      hash(map(&:hash).reduce(&:+))
    end
  end

  def hash(d)
    seed = d.to_s
    Digest::SHA256.digest(seed)
  end
end

Spec

require_relative './spec_helper'
require_relative '../lib/merkle_tree'

describe 'MerkleTree' do
  first = MerkleNode.new(
    MerkleNode.new(
      MerkleNode.new(nil, nil, 1),
      MerkleNode.new(nil, nil, 2),
    ),
    MerkleNode.new(
      MerkleNode.new(
        MerkleNode.new(nil, nil, 3),
        MerkleNode.new(nil, nil, 4),
      ),
      MerkleNode.new(nil, nil, 5),
    ),
  )

  second = MerkleNode.new(
    MerkleNode.new(
      MerkleNode.new(nil, nil, 1),
      MerkleNode.new(nil, nil, 2),
    ),
    MerkleNode.new(
      MerkleNode.new(
        MerkleNode.new(nil, nil, 3),
        MerkleNode.new(nil, nil, 4),
      ),
      MerkleNode.new(nil, nil, 5),
    ),
  )

  third = MerkleNode.new(
    MerkleNode.new(
      MerkleNode.new(nil, nil, 1),
      MerkleNode.new(nil, nil, 2),
    ),
    MerkleNode.new(
      MerkleNode.new(
        MerkleNode.new(nil, nil, 3),
        MerkleNode.new(nil, nil, 4),
      ),
      MerkleNode.new(nil, nil, 0),
    ),
  )

  describe '==' do
    it do
      expect(first  == second).to eq true
      expect(first  == third ).to eq false
      expect(second == third ).to eq false
    end
  end
end