読者です 読者をやめる 読者になる 読者になる

Maglev Hashing with Python

Python Programming Network

今更ながら,GoogleのMaglev論文で提案されているMaglev Hashingを手元で実装してみた.

Maglev: A Fast and Reliable Software Network Load Balancer

Maglev Hashingとは

所謂Consitent Hashの一種.Maglevロードバランサにおけるリアルサーバ選択に使用されている.

上記論文のSection 3.4で詳細が説明されている.NSDI'16での発表スライドも併せて眺めると分かりやすい.

Maglev: A Fast and Reliable Software Network Load Balancer | USENIX

Slide: https://www.usenix.org/sites/default/files/conference/protected-files/nsdi16_slides_eisenbud.pdf

実装

Golang実装を参考にしつつ,Pythonで実装してみた.

gist.github.com

Example

256エントリを追加した状態で,更に1エントリの追加・削除を行っている.

テーブルサイズを65537としたとき*1,1エントリの追加・削除で影響を受ける割合が 772 / 65537 = 1.2%程度に抑えられていることが分かる.

>>> h = MaglevHash(m=65537)
>>> for i in range(256):
...     h.add("172.16.1.{}".format(i))
...
>>> h.populate()
65537
>>> h.add("192.168.1.1")
>>> h.populate()
772
>>> h.lookup("10.0.0.1")
'172.16.1.111'
>>> h.remove("172.16.1.111")
>>> h.populate()
700
>>> h.lookup("10.0.0.1")
'172.16.1.68'

なお,Maglev Hashingの評価は論文のSection 5.3で示されている.

Kargerらの手法*2Rendezvousと比べ,各エントリに均等に分散されることが示されている.また,テーブルサイズ m が十分に大きければ,エントリの追加・削除によって影響を受ける割合も小さくなることも示されている.ただし,mの値を大きくすることは計算量の増大に繋がるため,考慮が必要である.

留意点

論文中では実装の詳細が割愛されている.上記実装のうち,下記の点については注意が必要である:

  • offsetskip の値を決定するために使用するハッシュ関数は,論文では与えられていない.上記実装では簡単のためsha256を使用している.実用上は,短い入力に対しても高速かつ良い結果が得られるハッシュ関数*3を使用するのが望ましいと考えられる.
  • lookup() で使用するハッシュ関数についても同様に論文では与えられていない.上記実装ではoffset/skip同様にsha256を使用している.実用上何を使うべきかはアプリケーションの仕様やトラフィック特性に依存する部分があるので,ケースバイケースだと考えられる.

*1:エントリ数に対して十分に大きい素数を与える

*2:元祖Consistent Hash

*3:例えばSipHash