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
の値を大きくすることは計算量の増大に繋がるため,考慮が必要である.
留意点
論文中では実装の詳細が割愛されている.上記実装のうち,下記の点については注意が必要である: