Kawababa

始まり

5/11になりました。後一週間ありません。気合を入れていきます。

今日やったこと

• Consistent Hashingの気持ちを理解した
• この一週間の予定を決めた。

今日が一週間で一番授業が多い日なので、あまり色々やることはできませんでしたが、Consistent Hashingの意図を掴めた気がしています。

Consistent Hashing

Consistent Hashingの実装方法として、Maglev Hashingについて論文とかを参照しながら、疑似コードなどを実際に実装するなどして、理解しました。
実装したコードはこちらです。

ここからは、Maglev Hashingの大体の手順について説明します。
どこかで、この手順について真面目に解説するスライドを作成してみたいなぁ。

手順

1. バックエンドごとに、十分な長さを持つ優先順位テーブルpermutationを作成します。論文ではこれをpermutation tableと呼んでいます。
permutationは、二次元配列で、行がそれぞれのバックエンドの優先順位を示している。

2. permutationを使って、実際に使用するルックアップテーブルtableを作成する。tableは、サーバの配列になっています。

ここからは作成した後の話です。

3. キャッシュキーとしてKを生成する。

4. H = K mod Mとする。table[H]で、サーバを取得することができる。

5. 取得したサーバの情報を使って、パケットを転送したりする。

この一週間にすることを決めた

最後の一週間なので、とりあえず予定を決めた。
最後の土日は課題自体の仕上げにする予定なので、あと4日しかない！！がんばります。

今決めている絶対にやることリスト

• TTLの実装
• Consistent Hashing (Maglev Hashing)の実装
• CacheNodeの上位層の追加
• CacheControlヘッダーの実装

それぞれにまた細かくタスクが出てくると思うので、とりあえずこれぐらいにしておきます。

終わり

Consistent Hashingの実装の方針を掴むことができた。
最初は、LRUCacheのすごいやつとかいう理解ではじめたけれど、そもそも二つの目的が全く違った（笑）
Consistent Hashingはどうやってコンテンツとサーバを紐付けるかという問題を解決するためのもので、LRUCacheはキャッシュをどうやって管理するかという問題を解決するためのものだった。これだから何も知らない状態で、適当に予定を立てたりするのは危険ですね。予定の数倍時間がかかっている（笑）でも楽しいからOK!
あと実質四日しかない（土曜日はアルバイト）なので、気合を入れて残りも頑張ります。