Maglev Hashing with Python
今更ながら，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で実装してみた．
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らの手法*2やRendezvousと比べ，各エントリに均等に分散されることが示されている．また，テーブルサイズ m が十分に大きければ，エントリの追加・削除によって影響を受ける割合も小さくなることも示されている．ただし，mの値を大きくすることは計算量の増大に繋がるため，考慮が必要である．
留意点
論文中では実装の詳細が割愛されている．上記実装のうち，下記の点については注意が必要である:
