Faceboook の 2016年の論文、Social Hash: an Assignment Framework for Optimizing Distributed Systems Operations on Social Networks を読みました。
どんなもの?
Social Hash という名前だけをみると MurmurHash のようなハッシュ関数の仲間のようですが、実際には「分散システムにおけるリソースを割り当てを、2段階にすると良いですよ」という手法の提案です。
論文では、リクエストのルーティングに適用してキャッシュのミスヒットを減らす、ストレージシステムに適用してレイテンシを減らす、という二つの応用が取り上げられています。
技術や手法のキモはどこ?
Social Hash では、ソーシャルグラフのような比較的安定した入力をもとにした、重い (計算に時間のかかる) 計算を前処理として行っておき、そこにホストの生死や忙しさのようなリアルタイムに移りかわる入力を組み合わせることで、最適なリソース割り当てを実現しています。
前者はそこまで頻繁に変わらないため、論文中では "Static Assignment" (静的な割り当て), 後者は頻繁にかわるため、論文中では "Dynamic Assignment" (動的な割り当て) と呼ばれています。
どうやって有効だと検証した?
前述の通り、
- リクエストのルーティングに適用してキャッシュのミスヒットを減らす
- ストレージシステムに適用してレイテンシを減らす
という二つの応用でもって、その有効性を検証しています。
次に読むべき論文は?
そもそも Facebook はどうやってグラフを保存しているのか、という話を取り扱ったものに TAO: Facebook’s Distributed Data Store for the Social Graph が、Social Hash で提案している手法のうち、グラフを分割だけを掘り下げたものに Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner
があります。