memcached proxyのハッシュアルゴリズム比較
はじめまして！hibikiです(@add_bakkers) 現在大学3年生で、最近はネットワークに興味があり勉強中です。2023年8月からインフラチームにインターンとして参加しました。 本記事ではmemcached proxyのハッシュアルゴリズム比較の結果を紹介します。
- memcached proxyのハッシュアルゴリズム比較
- We are Hiring!
1. 背景と目的
ミラティブでのmemcachedの利用
ミラティブでは、キャッシュシステムとしてmemcachedを利用しています。
memcachedは一般に、データベースの集計結果やセッション情報などをキャッシュするミドルウェアです。これを利用することで、データベースへの直接のクエリを減らして負荷を軽減し、リクエスト全体のスループットを向上させています。
具体的には、以下のようなデータのキャッシュに利用しています。
- セッションデータの保持
- ただし、memcachedのデータが消えてもMySQLにフォールバックするようにしている
- ユーザさんに見せるゲームカタログなどの内容
- 閲覧者数など、ライブ関連の情報
課題: クライアントサイドでサーバ決定をしている
memcachedを複数台で運用する際は、接続するクライアント側でサーバ選択のアルゴリズムを持たせることが多いです。
例えばgihyo.jpのmemcachedの分散アルゴリズムという記事が参考になるでしょう。
ミラティブでも現在、複数台のうちどのmemcachedサーバを利用するかは、クラスタ側に持たせるのではなく、クライアント側の責務として実装しています。
クライアント側でのサーバ選択には以下のメリットとデメリットがあります：
- メリット
- サーバ側では単一のノードとして起動できるため依存が少なくシンプルに構成できる
- サーバ決定ロジックをサーバ側で持たないためキーの対応づけなど状態を管理する必要がなくなる
- デメリット
- 全てのクライアントで正確なサーバの一覧を持たなければ適切なキーで取得できない
- ミラティブではクライアント実装が複数(PerlとGo)あるため、サーバ選択についての実装が分散してしまう
また、関連して、新しいサーバの追加や既存サーバの削除の際の挙動も課題でした。 現在は一部のクライアントの実装ではキーのハッシュ値からサーバ数のmodを取得してサーバ選択をしています。取得処理の疑似コードは以下のようなイメージです。
local server_list = fetch_current_server_list() local index = hasher(key) % len(server_list) return server_list[index]
ハッシュ値のmodの値であるので、急激な台数変更をすると当然modの値は大きく変わり、配置先のサーバが変更されます。その結果、アクセスできないキーが発生して、cacheの取り直しが起こり、それがバックエンドサーバの高負荷やフロントエンドサーバのスループット低下につながっていました。
サーバ選択ロジックを変更するにしても、クライアント側の言語が複数あって(PerlとGo)実装しているロジックを一致させて同じ挙動をさせることが難しいことが問題として挙げられます。またクライアント側に新しいもの(例えばサーバサイドSwiftなど)が出てきたり、実装言語を変更する必要が出た場合に再度同じロジックになるように修正しなければいけないのも課題でしょう。
memcached proxyの検討
これらの課題を解決するために、memcached proxyの導入を検討しています。
memcached proxyとは、memcached自体に組み込まれたproxy機能のことです。機能としてはproxyに加え、ロードバランサーとしての役割も持たせられます。 似たような製品としてtwemproxyやdynomiteなどがあります。それらと比べて、memcached proxyは、memcached の一部として使えること、staticな設定ではなくLuaで柔軟に分散ロジックを記述できること、本家に含まれることから本家の機能拡張にも追従しやすいこと、などがメリットです。 memcached proxyを導入して、サーバ選定ロジックをproxy側で一元管理できるようになれば、新しいサーバの追加や既存のサーバの削除が容易なロジックに切り替えることもやりやすくなります。
2. memcached proxyに求められるアルゴリズム
上記の理由で柔軟性がある memcached proxy が我々のニーズに合うか調査を進めることにしました。
しかし、ここまでに述べたような課題を解決するためには、要件になるべく見合ったサーバ選択アルゴリズムを選定する必要があります。私たちは以下のような観点からアルゴリズムを比較することにしました。
キーの分散
今回のmemcached proxyの分散方針は、リクエストのキーからバックエンドサーバのうち一つを割り当て、それに基づいて特定のバックエンドを選択させる方式を取ります。
memcached proxyの公式リポジトリに付いてくるサンプル設定は非常にシンプルで、キーのprefixに基づいて固定でサーバを振り分けます。
キーの分散のさせ方はアルゴリズムによって変わってきます。例えばconsistent hashingとjump consistent hashingの場合とでも分散の仕方は違うので、まずそれを把握する必要があるでしょう。
以下は、consistent hashingによって特定のキーが特定のサーバに偏った場合のイメージです。
最終的な性能要件を満たすのであれば一定の偏りは許容できるでしょうが、極端なものは負荷分散という視点から見ると少し困ることもあります。そういう場合には、consistent hashingでいうreplica（仮想的にノードを増加させる係数）の数を変えたり、keyに特定のsuffixをランダムに付けて（SET foobar を SET foobar:$RANDOM とするイメージ）散らばりを強める等の工夫もできるでしょう。
余談ですが、この「suffixをランダムに付ける」という操作も現在ミラティブではクライアント側で実装しています。こういう操作をproxy側に寄せられるというのもmemcached proxyのメリットではあるでしょう。
いずれにせよ、分散の仕方の特性を整理する必要があります。
移動率の抑制
さらに、サーバの追加・削除に伴うデータ移動率を低く保つことが重要だと考えました。
ここでいう移動率とは、サーバの追加や削除に伴って、どれだけのキーの割り当てが異なるサーバに移動するかの割合です。
例えば、 foobar:1:1 と言うキーが、サーバ追加前は 10.0.0.10 というサーバに割り当てられているとします。この時に、サーバを追加したら計算結果が変わって 10.0.0.20 というサーバに割り当たるようになってしまったら、そのキーは移動したと言えます。
キーの移動率が高くなると、今までアクセスできていたキーの内容を取得できなくなる割合が増え、キャッシュのヒット率が低くなってしまうことが想像できると思います。キャッシュヒット率の低下は、パフォーマンスに悪影響を及ぼします。
パフォーマンス
また、パフォーマンスが十分に出るかを確認するのも重要です。
memcachedはそもそも高速なミドルウェアです。memcached proxyという新しいレイヤーを導入することによって、memcachedへのリクエスト全体のスループットが下がってしまうことは避けたいと考えています。その場合に起こる事態として、例えば他にスループットが下がった分を補うために memcachedのインスタンスを追加することによるコスト増であったり、あるいはスループットの低下自体が何かしらの障害につながってしまうことなどの懸念があります。
具体的要素としては、サーバ選択にどのアルゴリズムを選んだかによってパフォーマンスに影響が出ることが考えられます。したがって、memcached proxyとハッシュアルゴリズムの組み合わせごとにRPS（request per second）を計測して比較することにします。
現在memcached単体でどれくらいのRPSが出ているかは事前にtcpdump等を用いて単一時間あたりの流量を計測して確認できているため、基本的にはそのRPSの要件を満たせば問題ありません。したがって今回の測定では、例えばシステムの性能限界を探るようなベンチは検証の対象外としています。
ただ、詳細なRPSを確認することはアルゴリズムの理解に重要なので、具体的パフォーマンスを比較できるように計測していきます。
ハッシュアルゴリズムの比較
今回検討したアルゴリズムは以下の3種類です。それぞれのアルゴリズムの概要をまずは示します。
- consistent hashing
- リング状にノードを配置し、キーがリングのどこに所属するかによってリクエスト先を決定するアルゴリズム。
- consistent hashing法の中でも、例えば古くからあるketama、重みづけが可能になるweighted consistent hashing、リング上の複数の仮想ノードを特定のノードIDと紐付けて偏りを軽減するvirtual nodeなどいくつか手法があります。今回採用したのはvirtual node法に近いものです。
- rendezvous hashing
- jump consistent hashing
3. 今回行うベンチマークの概要
先ほど述べた3つの観点から、最適なアルゴリズムをさぐるため、ベンチマークを行います。この章でその概要を説明します。
計測対象とシナリオ
分散と移動率のベンチ
まず、たくさんのキーを人工的に生成して 分散と移動率 を計測します。
具体的なシナリオとしては、まず生成した一定数のキーを仮想ノードに対してどの程度分散されるか検証します。次に仮想ノードを増減させた状態で再検証し移動率を計算します。
Lua風の疑似コードではありますが、以下のような処理をローカルで行って結果を可視化します。
-- 移動前のサーバー一覧 local servers_before = create_server_list(servers_before_num) -- 移動後のサーバー一覧 local servers_after = create_server_list(servers_after_num) -- キー全体でどのサーバに割り当てられたかのテーブル local count_table_before = create_count_table(servers_before) -- 移動前、どのサーバに割り当てられたかをキーごとに保持しておく local old_picked = {} for i = 0, 1000000 do local key = key_prefix .. tostring(i) local picked_server = hashing_logic.pick_server(servers_before, key) count_table_before[picked_server] = count_table_before[picked_server] + 1 old_picked[key] = picked_server end -- 同じく、キー全体でどのサーバに割り当てられたかのテーブル local count_table_after = create_count_table(servers_after) -- 移動前後で変わらなかったキー数のテーブル local count_table_remained = create_count_table(servers_after) -- 移動したキーの総数 local key_moved = 0 for i = 0, 1000000 do local key = key_prefix .. tostring(i) local picked_server = hashing_logic.pick_server(servers_after, key) count_table_after[picked_server] = count_table_after[picked_server] + 1 -- どのサーバに割り当てられたかを移動前と比較し、 -- 移動していたらkey_movedをカウントアップ -- していなかったらremainedをカウントアップする if old_picked[key] ~= picked_server then key_moved = key_moved + 1 else count_table_remained[picked_server] = count_table_remained[picked_server] + 1 end end -- 結果を表示 show_result(count_table_before, count_table_after, key_moved, count_table_remained)
処理性能のベンチ
また、ベンチマークプログラムを書いて、 処理性能 のパフォーマンスを計測します。
具体的なシナリオとしては、ベンチマークプログラムでは、実際に複数のmemcachedサーバを立て、memcached proxyに大量のリクエストを送信してそのパフォーマンスを評価します。具体的には、RPSとレイテンシを測定可能なようにしました。
実際のコマンドとパラメータは以下のようになります。 --count が送るリクエストの回数、 --concurrency がリクエスト並行数、 --value-size が memcachedのSet/Getリクエストのvalueの大きさ、 --request-per-sec が送ろうと試みる最大のRPSです。
docker run --rm -ti --net=host benchmark-memcached:latest \ --memcached-proxy-address 10.0.0.81:11211 \ --count 300000 \ --request-per-sec 1000000 \ --concurrency 80 \ --value-size 512
また、ベンチマーク環境の構成とスペックは以下のようになります。Google Cloud上に構築しました。
合わせて、memcached proxyを動かしているインスタンス内部で vmstat の結果を用いて CPU利用率 も観察します。
4. ベンチマークの結果と比較
移動率の計測結果
前の章で説明した移動率計算プログラムの実行結果を掲載します。
仮想ノードを6つから8つに増やした（今回の増やし方は、末尾へ2ノード追記する方式です）ときに以下のフォーマットで結果を表示します。
replica = レプリカ数（consistent hashingのみ） 仮想サーバ1のUUID : 割り当てられたキーの数 仮想サーバ2のUUID : 割り当てられたキーの数 ... 仮想サーバNのUUID : 割り当てられたキーの数 key moved : (移動したキーの数) 仮想サーバ1のUUID : 再実行した時に割り当てられたキーの数 (移動率) 仮想サーバ2のUUID : 再実行した時に割り当てられたキーの数 (移動率) ... 仮想サーバNのUUID : 再実行した時に割り当てられたキーの数 (移動率) ... 仮想サーバN+MのUUID : 再実行した時に割り当てられたキーの数 (移動率) time: 処理時間
consistent hashingの結果
0c4fa0f9-ddc1-4459-826a-a7d73689f407 : 8743 5974925a-5034-46c0-8b35-52c02dfbcb3a : 375226 666ead68-31ed-4282-b008-1a442afacfd7 : 173316 945a164a-a820-4e25-a144-2a0f6702e861 : 253825 9e42424e-5360-480f-b5c4-c6ed1508d548 : 51773 c412ec3c-f0be-4075-8cd9-cf44f15175d4 : 137118 key moved : 11.1125% 0c4fa0f9-ddc1-4459-826a-a7d73689f407 : 8743(0.00 % moved) 5974925a-5034-46c0-8b35-52c02dfbcb3a : 375226(0.00 % moved) 666ead68-31ed-4282-b008-1a442afacfd7 : 62191(64.12 % moved) 945a164a-a820-4e25-a144-2a0f6702e861 : 253825(0.00 % moved) 9e42424e-5360-480f-b5c4-c6ed1508d548 : 51773(0.00 % moved) c412ec3c-f0be-4075-8cd9-cf44f15175d4 : 137118(0.00 % moved) dfb750bb-0594-456e-b484-e778d08cae0c : 61642 eef83d63-39e2-42f5-894d-2a5d5acb7b4d : 49483 time: 7.615109 seconds
rendezvous hashingの結果
0c4fa0f9-ddc1-4459-826a-a7d73689f407 : 170519 5974925a-5034-46c0-8b35-52c02dfbcb3a : 165663 666ead68-31ed-4282-b008-1a442afacfd7 : 165436 945a164a-a820-4e25-a144-2a0f6702e861 : 166351 9e42424e-5360-480f-b5c4-c6ed1508d548 : 163404 c412ec3c-f0be-4075-8cd9-cf44f15175d4 : 168628 key moved : 24.4289% 0c4fa0f9-ddc1-4459-826a-a7d73689f407 : 129070(24.31 % moved) 5974925a-5034-46c0-8b35-52c02dfbcb3a : 125692(24.13 % moved) 666ead68-31ed-4282-b008-1a442afacfd7 : 123075(25.61 % moved) 945a164a-a820-4e25-a144-2a0f6702e861 : 126491(23.96 % moved) 9e42424e-5360-480f-b5c4-c6ed1508d548 : 123867(24.20 % moved) c412ec3c-f0be-4075-8cd9-cf44f15175d4 : 127517(24.38 % moved) dfb750bb-0594-456e-b484-e778d08cae0c : 125366 eef83d63-39e2-42f5-894d-2a5d5acb7b4d : 118923 time: 73.869666 seconds
jump consistent hashingの結果
0c4fa0f9-ddc1-4459-826a-a7d73689f407 : 166653 5974925a-5034-46c0-8b35-52c02dfbcb3a : 166605 666ead68-31ed-4282-b008-1a442afacfd7 : 166700 945a164a-a820-4e25-a144-2a0f6702e861 : 166912 9e42424e-5360-480f-b5c4-c6ed1508d548 : 166572 c412ec3c-f0be-4075-8cd9-cf44f15175d4 : 166559 key moved : 24.9288% 0c4fa0f9-ddc1-4459-826a-a7d73689f407 : 125042(24.97 % moved) 5974925a-5034-46c0-8b35-52c02dfbcb3a : 125073(24.93 % moved) 666ead68-31ed-4282-b008-1a442afacfd7 : 124892(25.08 % moved) 945a164a-a820-4e25-a144-2a0f6702e861 : 125067(25.07 % moved) 9e42424e-5360-480f-b5c4-c6ed1508d548 : 124989(24.96 % moved) c412ec3c-f0be-4075-8cd9-cf44f15175d4 : 125650(24.56 % moved) dfb750bb-0594-456e-b484-e778d08cae0c : 123606 eef83d63-39e2-42f5-894d-2a5d5acb7b4d : 125682 time: 7.542191 seconds
考察
まず、結果から考察した3アルゴリズムの特徴を表形式で一覧します。
| アルゴリズム | 分散の特徴 | 移動の特徴 | ハッシュ計算のみの速度 |
|---|---|---|---|
| consistent hashing | 偏りが大きく出やすい | 移動率が小さく見える | 高速 |
| rendezvous hashing | データの分散はほぼ均等 | 一定割合の移動 | 低速 |
| jump consistent hashing | データの分散はほぼ均等 | 一定割合の移動 | 高速 |
少し補足すると、ここでいう「一定割合の移動」とは、移動したノードは (移動後 - 移動前) / 移動後 * 100 % 程度に収まっているということを意味しています。したがって今回は6つのノードを8つに増加したため、 (8 - 6) / 8 * 100 = 25%程度の移動をします。これは増加後のノード数から考えると一定割合に収まる移動率としています。
また、Consistent Hashingはより移動率が小さく見えるのですが、具体的に言うと新しいノードに割り当てられるキーが少なく偏ったためそう見えています。この偏りは、replicaというパラメータを指定して仮想的なノード数を増やすことである程度解消できます。
例えばreplicaが3つの場合、実際のノードが8つであれば 8 * 3 = 24 仮想ノードをリング上に配置し、そのうち3つを1つの実ノードに対応づけるという方法を取ることになります。仮想的に数を多くしてからグループ化することでばらつきを緩和する意図があります。
上記検証ではreplica = 1の結果を示していますが、replica = 3にすると以下のようになります。
0c4fa0f9-ddc1-4459-826a-a7d73689f407 : 168080 5974925a-5034-46c0-8b35-52c02dfbcb3a : 176217 666ead68-31ed-4282-b008-1a442afacfd7 : 91810 945a164a-a820-4e25-a144-2a0f6702e861 : 331645 9e42424e-5360-480f-b5c4-c6ed1508d548 : 87690 c412ec3c-f0be-4075-8cd9-cf44f15175d4 : 144559 key moved : 18.6317% 0c4fa0f9-ddc1-4459-826a-a7d73689f407 : 168080(0.00 % moved) 5974925a-5034-46c0-8b35-52c02dfbcb3a : 104022(40.97 % moved) 666ead68-31ed-4282-b008-1a442afacfd7 : 88813(3.26 % moved) 945a164a-a820-4e25-a144-2a0f6702e861 : 220520(33.51 % moved) 9e42424e-5360-480f-b5c4-c6ed1508d548 : 87690(0.00 % moved) c412ec3c-f0be-4075-8cd9-cf44f15175d4 : 144559(0.00 % moved) dfb750bb-0594-456e-b484-e778d08cae0c : 106961 eef83d63-39e2-42f5-894d-2a5d5acb7b4d : 79356 time: 8.734455 seconds
ただしその分ノード探索に時間がかかるようになり、速度的デメリットがあります。
ここまでの結果では、consistent hashingではある程度の偏りがありつつも移動率が小さくなる傾向があり、また分散の度合い・移動・速度面のバランスがいいのはjump consistent hashingと言えそうです。
処理性能の前提: 利用するハッシュについて
続いて処理性能の計測結果を掲載しますが、前提として、ハッシュ計算にはFNVハッシュ関数というものを利用しています。
FNVハッシュ関数とは
FNVハッシュ関数は、非常に高速で簡単なハッシュ関数の一つです。以下のような特徴を持っています：
- 高速性：計算が非常に簡単であるため、高速にハッシュ値を生成することができます。
- 低衝突率：異なるデータが同じハッシュ値を持つ可能性（衝突）が低くなるように設計されています。
今回はFNVハッシュを少し改変したFNV1aというハッシュ関数を採用しました。上記の特徴に加え、以下の特徴があります：
- 分散性：データのわずかな変更でもハッシュ値が大きく変わるため、データが均等に分散されやすくなります。
アルゴリズム上元の値の逆算が可能なため暗号としては利用できないハッシュ関数ですが、今回は暗号論的安全性は必要ないため利用しています。アルゴリズムの詳細は、IETFで Informational RFC としてドキュメント化が進んでいるので参照できます。また、Go言語では標準ライブラリで実装を持っていますのでそのドキュメントも参考になるかと思います（FNVとFNV1a両方の説明があります）。
ところでこのFNVの実装ですが、実はLuaで実装したものとC言語で実装し直したものとで性能に差が出ました。具体的なベンチマークの結果を掲載して比較します。
ベンチマークの結果では、以下のものを示します。
- ベンチ全体の所要時間（SET操作/GET操作別に。以下同じ）
- RPS
- リクエストのレイテンシの各種統計値
- リクエスト失敗またはmissの割合
なお、パフォーマンス計測時については、consistent hashingの計測時の設定はreplica = 3としています。実環境に導入する時には若干でも偏りを軽減した設定を選びたくなるはずなので、移動率の検証で見たようにreplica = 1の時よりも偏りが小さくなっているreplica = 3を採用しています
consistent hashing + Lua版FNVの結果
-----SET RESULT----- 300000 request sent. total time (s) | 14.740 RPS | 20349.429 mean (ms) | 3.768 median (ms) | 3.475 percentile50 (ms) | 3.475 percentile90 (ms) | 5.336 percentile95 (ms) | 6.124 percentile99 (ms) | 8.262 stddev (ms) | 1.321 failureRate | 0.00% -----GET RESULT----- 300000 request sent. total time (s) | 13.275 RPS | 22736.077 mean (ms) | 3.352 median (ms) | 3.039 percentile50 (ms) | 3.039 percentile90 (ms) | 5.128 percentile95 (ms) | 6.058 percentile99 (ms) | 8.560 stddev (ms) | 1.465 failureRate | 0.00%
consistent hashing + C版FNVの結果
-----SET RESULT----- 300000 request sent. total time (s) | 13.663 RPS | 22027.231 mean (ms) | 3.524 median (ms) | 3.143 percentile50 (ms) | 3.143 percentile90 (ms) | 5.406 percentile95 (ms) | 6.494 percentile99 (ms) | 9.174 stddev (ms) | 1.590 failureRate | 0.00% -----GET RESULT----- 300000 request sent. total time (s) | 12.825 RPS | 23397.917 mean (ms) | 3.300 median (ms) | 2.580 percentile50 (ms) | 2.580 percentile90 (ms) | 6.235 percentile95 (ms) | 8.143 percentile99 (ms) | 12.438 stddev (ms) | 2.410 failureRate | 0.00%
C言語実装の方が10%程度パフォーマンスが上がるため、今回は、基本的にC言語でのFNV実装を採用して測定しました。
C版FNV を利用した上で、上掲の3アルゴリズムを比較した結果が以下です。
consistent hashingの結果（C版FNV を利用）
-----SET RESULT----- 300000 request sent. total time (s) | 13.663 RPS | 22027.231 mean (ms) | 3.524 median (ms) | 3.143 percentile50 (ms) | 3.143 percentile90 (ms) | 5.406 percentile95 (ms) | 6.494 percentile99 (ms) | 9.174 stddev (ms) | 1.590 failureRate | 0.00% -----GET RESULT----- 300000 request sent. total time (s) | 12.825 RPS | 23397.917 mean (ms) | 3.300 median (ms) | 2.580 percentile50 (ms) | 2.580 percentile90 (ms) | 6.235 percentile95 (ms) | 8.143 percentile99 (ms) | 12.438 stddev (ms) | 2.410 failureRate | 0.00%
rendezvous hashの結果（C版FNV を利用）
-----SET RESULT----- 300000 request sent. total time (s) | 17.670 rps | 16975.235 mean (ms) | 4.555 median (ms) | 4.141 percentile50 (ms) | 4.141 percentile90 (ms) | 6.908 percentile95 (ms) | 8.223 percentile99 (ms) | 11.611 stddev (ms) | 1.990 failureRate | 0.00% -----GET RESULT----- 300000 request sent. total time (s) | 16.360 rps | 18327.250 mean (ms) | 4.225 median (ms) | 3.569 percentile50 (ms) | 3.569 percentile90 (ms) | 7.737 percentile95 (ms) | 9.662 percentile99 (ms) | 13.984 stddev (ms) | 2.779 failureRate | 0.00%
jump consistent hashingの結果（C版FNV を利用）
-----SET RESULT----- 300000 request sent. total time (s) | 13.728 RPS | 21890.077 mean (ms) | 3.519 median (ms) | 3.274 percentile50 (ms) | 3.274 percentile90 (ms) | 4.720 percentile95 (ms) | 5.449 percentile99 (ms) | 8.144 stddev (ms) | 1.168 failureRate | 0.00% -----GET RESULT----- 300000 request sent. total time (s) | 12.132 RPS | 24746.000 mean (ms) | 3.046 median (ms) | 2.769 percentile50 (ms) | 2.769 percentile90 (ms) | 4.566 percentile95 (ms) | 5.312 percentile99 (ms) | 7.635 stddev (ms) | 1.314 failureRate | 0.00%
ここまでの比較では、RPSを見る限りjump consistent hashingとconsistent hashingがほぼ同等です。RPSとレイテンシの主要な統計値をグラフで表したものが以下です。
なお、consistent hashingとrendezvous hashingは偏りの改善のためreplicaを増やしたり、あるいは選択対象のサーバが増えたりするとノード探索が徐々に遅くなる傾向が見えました。一方、jump consistent hashingには選択対象のサーバが増えた時の性能劣化は、十数台の範囲では目立ちませんでした。
対象サーバが増えた時の比較を、サーバ数 3, 9, 18 で取得しています。結果をグラフにて掲載します。
とはいえ、jump consistent hashingでも1000台/10000台のオーダーでは性能劣化が目立つようになります。それを克服して定数時間でハッシュを計算できるpower consistent hashingというものも存在しますが、その検証は今後の課題と考えています。
CPU利用状況の比較
合わせて、CPU利用状況についても比較考察の結果を掲載します。今回は、一番RPSが低く出たrendezvous hashingの場合と高めに出たjump consistent hashingの場合を比較するにとどめます。
vmstatの結果は普通のコマンドではなく、vmstatを実行し続けるデーモンのログから抽出しています。今回は一部を抜粋しています。ログの見方は以下の通りです。
procs -----------memory---------- -system----- ------cpu----- r b swpd free buff cache in cs us sy id wa st 5 0 0 2342532 245900 4789880 33590 9054 19 41 40 0 0 5 0 0 2326208 245900 4789884 55178 12791 29 69 2 0 0 ...
rendezvous hashのvmstat結果
procs -----------memory---------- -system----- ------cpu----- r b swpd free buff cache in cs us sy id wa st 5 0 0 2638388 238184 4476332 35186 9122 33 42 26 0 0 4 0 0 2635916 238184 4476332 47568 15371 41 58 1 0 0 4 0 0 2637256 238184 4476352 46294 13411 41 57 1 0 0 4 0 0 2638276 238184 4476352 49491 19929 39 60 1 0 0 6 0 0 2640220 238184 4476352 46235 13693 41 57 1 0 0 5 0 0 2640148 238184 4476356 47249 15330 43 57 0 0 0 5 0 0 2640584 238184 4476356 47973 13426 41 58 1 0 0 4 0 0 2637584 238184 4476364 45204 14943 43 55 2 0 0 5 0 0 2630988 238184 4476368 46662 18943 43 56 2 0 0 5 0 0 2630904 238184 4476368 49034 21440 40 59 1 0 0 6 0 0 2629400 238184 4476384 48333 16665 41 58 1 0 0 8 0 0 2633360 238184 4476372 48194 15739 41 58 1 0 0 7 0 0 2632460 238184 4476364 49084 22143 39 60 1 0 0 3 0 0 2627712 238184 4476368 50823 23356 39 60 1 0 0 5 0 0 2629504 238184 4476372 48252 17716 40 59 1 0 0 3 0 0 2634096 238184 4476372 46442 15021 41 58 1 0 0 5 0 0 2628088 238184 4476388 48658 20483 41 59 1 0 0 5 0 0 2632900 238184 4476392 45111 13690 44 55 1 0 0 4 0 0 2631112 238184 4476376 30647 10382 27 39 35 0 0 4 0 0 2632208 238184 4476392 45268 13472 45 54 1 0 0 5 0 0 2631188 238184 4476380 45734 15330 43 57 1 0 0 5 0 0 2630088 238184 4476380 45462 15705 42 58 1 0 0 5 0 0 2637088 238184 4476380 43837 12965 43 57 0 0 0 5 0 0 2631480 238184 4476384 42548 12978 44 55 1 0 0 5 0 0 2630564 238184 4476384 41691 10992 46 53 1 0 0 6 0 0 2634676 238184 4476388 44094 14468 44 55 1 0 0 5 0 0 2641540 238184 4476388 43642 13312 44 56 0 0 0 5 0 0 2631412 238184 4476388 44153 15008 44 56 1 0 0 5 0 0 2635704 238184 4476408 42819 12400 43 57 1 0 0 6 0 0 2643180 238184 4476408 44194 14606 44 55 1 0 0 5 0 0 2645084 238184 4476408 44652 12620 44 56 1 0 0 4 0 0 2636256 238184 4476412 43647 14261 44 56 0 0 0 3 0 0 2643492 238184 4476412 44212 13872 44 56 1 0 0 4 0 0 2638956 238184 4476412 44940 15560 44 56 1 0 0 1 0 0 2638104 238184 4476400 31014 10201 32 39 29 0 0
jump consistent hashingのvmstat結果
procs -----------memory---------- -system----- ------cpu----- r b swpd free buff cache in cs us sy id wa st 1 0 0 2214228 247448 4893224 11049 4768 6 14 80 0 0 4 0 0 2213356 247448 4893224 55072 30652 32 66 3 0 0 5 0 0 2216744 247448 4893216 54300 23834 30 67 3 0 0 5 0 0 2215948 247448 4893220 55453 27006 32 66 2 0 0 4 0 0 2216944 247448 4893220 55261 26538 29 68 3 0 0 4 0 0 2215608 247448 4893220 54357 31982 30 68 2 0 0 6 0 0 2214988 247448 4893224 55220 27595 29 69 3 0 0 4 0 0 2213848 247448 4893228 53601 19200 30 68 2 0 0 5 0 0 2213892 247448 4893228 54913 25475 31 67 3 0 0 5 0 0 2212080 247448 4893232 53587 25892 34 63 3 0 0 4 0 0 2212312 247448 4893232 51356 24155 29 68 3 0 0 5 0 0 2213940 247448 4893232 55247 27366 30 67 3 0 0 4 0 0 2214084 247448 4893236 55200 27374 31 67 2 0 0 5 0 0 2213744 247448 4893236 55192 27037 32 66 3 1 0 4 0 0 2213672 247448 4893236 34859 14666 20 42 38 0 0 6 0 0 2214168 247448 4893240 52523 30662 33 66 2 0 0 4 0 0 2219988 247448 4893240 54468 18143 32 66 2 0 0 5 0 0 2219044 247448 4893244 53077 20445 31 66 2 0 0 5 0 0 2218680 247448 4893248 52265 19611 31 68 2 0 0 3 0 0 2218284 247448 4893248 52195 19176 33 66 1 0 0 5 0 0 2218256 247448 4893248 52814 17274 34 64 2 0 0 4 0 0 2218660 247448 4893252 54004 17179 30 68 2 0 0 5 0 0 2217912 247448 4893252 53798 17626 32 67 1 0 0 5 0 0 2217680 247448 4893252 54448 17532 33 66 1 0 0 5 0 0 2215968 247448 4893424 51175 14929 32 65 3 0 0 3 0 0 2215056 247448 4893408 52167 18176 33 66 1 0 0 0 0 0 2215272 247448 4893408 47066 15949 29 58 13 0 0
ご覧の通り、rendezvous hashingはusr CPU利用率が40%〜45%まで上昇しているのに、jump consistent hashingでは30%前半まで抑えられています。
これはシンプルに、memcached proxy上のアルゴリズムの効率が悪いとusr CPUを使い過ぎてパフォーマンスが出ず、改善されるとusr CPUを使わなくなると判断できます。
その結果、jump consistent hashingの方がsystem CPU利用率が上昇していることもうかがえます（ちなみに割り込みやコンテキストスイッチも少し上がっていますが、これもネットワーク系の処理に時間を使えるようになった影響と思われます）。これは、usrで頭打ちになっていたCPUをその分パケットの処理に使えるようになったためで、アルゴリズムの効率が改善するほど単位時間でのパケットもたくさん処理でき、全体のスループットが向上したと言えそうです。
一方で、リクエストが一定以上になるとsystem CPU利用率で頭打ちしてパケットの処理限界が来てしまうことも推測できます。最初に掲示した通り、今回はその限界を探るところまではしていません。
検証結果のまとめ
分散度合いでは、jump consistent hashing とrendezvous hashingが同程度の結果となりました。
どちらも、キーが均等に分散し、ノードの追加や削除が行われた際にもキーの移動が全体に対し一定に抑えられるアルゴリズムだと考えられます。
この特徴は特定のサーバに負荷が集中することを避けられる点でメリットがあります。
逆にconsistent hashingは均等には分散しづらいのですが、その分移動率も小さくなることがあるとわかりました。
また、スループットの観点ではconsistent hashingやjump consistent hashingが有力で、特にjump consistent hashingは十数台の範囲では効率的なアルゴリズムと言えそうです。
5. jump consistent hashingの課題
この結果だけを見ると、単にRPSという観点で言えばjump consistent hashingを選択するモチベーションが高まるかもしれません。一方で、jump consistent hashingにはアルゴリズムの性質上、あるいは運用上難しいポイントもいくつか存在しますので、その点も整理します。
jump consistent hashing の課題(1) - 順番への依存
jump consistent hashing の課題の一つは、ノードが必ず順番を保持していなければならず、かつ順序が崩れるような追加、削除をすると影響が大きくなってしまう点です。
以下の例は、先頭ノードの削除時の影響を可視化したものです。先頭の 41e453ab-b48c-4fc1-b6f5-2195b232c2ec と言う名前のノードが削除されたときに再計算すると、キーの位置が大きく移動してしまうことがわかります。
41e453ab-b48c-4fc1-b6f5-2195b232c2ec : 125042 44de4d29-7d64-4cda-b3c3-2833195d88cf : 125073 52c97967-828c-4719-88f3-71fcee03ada0 : 124892 6f95302f-d344-4e7d-895e-3e260de331e9 : 125067 81d74170-721f-4ffd-a4f7-0ce124d7be7a : 124989 9a519c85-fa22-4fcd-bef6-ce14f731e91f : 125650 9f0cd303-aa56-4481-af4d-4967e6df104c : 123606 eb7465be-56bf-4784-9a3d-546fc8759295 : 125682 key moved : 98.1469% 44de4d29-7d64-4cda-b3c3-2833195d88cf : 142785(100.00 % moved) 52c97967-828c-4719-88f3-71fcee03ada0 : 142885(100.00 % moved) 6f95302f-d344-4e7d-895e-3e260de331e9 : 142586(100.00 % moved) 81d74170-721f-4ffd-a4f7-0ce124d7be7a : 142991(100.00 % moved) 9a519c85-fa22-4fcd-bef6-ce14f731e91f : 143091(100.00 % moved) 9f0cd303-aa56-4481-af4d-4967e6df104c : 143525(100.00 % moved) eb7465be-56bf-4784-9a3d-546fc8759295 : 142138(85.25 % moved) time: 7.177101 seconds
open jump consistent hashing というアイデア
キーの位置の移動の問題について、最小限に抑えるため「open jump consistent hashing」というアイデアを考案しましたので紹介します。
このアイデアでは、削除されたノードの位置を「tombstone（墓石という意味）」として保持し順番を崩さないようにし、再配置時にtombstoneを考慮することでノード削除の影響を最小限に抑える方法を採用します。サーバ選択時には、削除されたノードをtombstoneとして設定ファイルで管理し、再配置時にこのtombstoneをスキップする処理を導入します。具体的には選択後のインデックスがtombstoneであればジャンプを再開し、次のインデックスを探す（一種のオープンアドレス法を実行する）ことで、ノードの削除による再配置を回避しつつ、削除されたノードを選択結果から除外します。
削除ノードをtombstoneとして残すことで、ノードの順序が崩れることなく、再配置で問題を起こしにくくすることが可能になります。
具体的な実装コード例は以下の通りです。
function jump_consistent_hashing.pick_num(key, num_list, max) -- LCG（線形合同法）のパラメータ local a = 2862933555777941757 local c = 12345 local m = 1 << 62 local b = 1 local j = 0 local key_num = fnv32(key) while true do if j >= max then if contains(num_list, b+1) ~= true then break end j = b end -- LCG Hash key_num = (a * key_num + c) % m rand = ((key_num >> 31) + 1) / (1 << 31) b = j j = math.floor((b + 1) / rand) end return b + 1 end
以下に示すのは、8仮想ノード中の4番めを削除した実験です。
41e453ab-b48c-4fc1-b6f5-2195b232c2ec : 125042 44de4d29-7d64-4cda-b3c3-2833195d88cf : 125073 52c97967-828c-4719-88f3-71fcee03ada0 : 124892 6f95302f-d344-4e7d-895e-3e260de331e9 : 125067 81d74170-721f-4ffd-a4f7-0ce124d7be7a : 124989 9a519c85-fa22-4fcd-bef6-ce14f731e91f : 125650 9f0cd303-aa56-4481-af4d-4967e6df104c : 123606 eb7465be-56bf-4784-9a3d-546fc8759295 : 125682 key moved : 12.5067% 41e453ab-b48c-4fc1-b6f5-2195b232c2ec : 125042(0.00 % moved) 44de4d29-7d64-4cda-b3c3-2833195d88cf : 125073(0.00 % moved) 52c97967-828c-4719-88f3-71fcee03ada0 : 124892(0.00 % moved) 6f95302f-d344-4e7d-895e-3e260de331e9 : 0(100.00 % moved) 81d74170-721f-4ffd-a4f7-0ce124d7be7a : 155110(0.00 % moved) 9a519c85-fa22-4fcd-bef6-ce14f731e91f : 157454(0.00 % moved) 9f0cd303-aa56-4481-af4d-4967e6df104c : 155348(0.00 % moved) eb7465be-56bf-4784-9a3d-546fc8759295 : 157082(0.00 % moved) time: 7.627247 seconds
この表示の通り、結果から4番めのノードは除外され、移動も起こらなくなりました。
ただし新たな問題が生じました。削除された分のキーは、前半の3つには移動していなくて結果として偏りが生じるようになってしまいました。
そこで、さらに、ノード削除の影響を軽減するためにインデックス空間を広げる対応も検討しました。
新しい方法では、計算後に決定されたインデックスがtombstoneだった場合、ジャンプの範囲を広げて再配置を行います。なおかつ、インデックスは (拡張後に決定したインデックス mod 元のバケット数) を計算して決定し、元のバケットの数の範囲に収めます。
こうすることで、tombstoneのインデックス（zと置きます）に対して、最終的にzより大きいものに決まる確率と、zより小さいものに決まる確率が近づくはずです。
このアプローチにより、インデックスの決定がよりランダムになり、tombstoneの影響を薄めて均等に分散させることが可能です。言葉だけの説明では分かりにくい面もありますので、以下に、具体的な実装コードとその結果を示します。
function jump_consistent_hashing.pick_num_2(key, num_list, upstream_num) -- LCGのパラメータ local a = 2862933555777941757 local c = 12345 local m = 1 << 62 local b = 1 local j = 0 local extended_index_num = upstream_num * 32 -- e.g. 32 local cap = upstream_num local key_num = fnv32(key) while true do if j >= cap then if contains(num_list, (b % upstream_num) + 1) ~= true then break end -- 結果がtombstoneであれば拡大して -- ジャンプ先を広げる -- 広げた先のmodの値なので、概ね均等に 1 ~ upstream_num に定まる cap = extended_index_num if extended_index_num <= b + upstream_num then return 1 end j = b end -- LCG Hash key_num = (a * key_num + c) % m rand = ((key_num >> 31) + 1) / (1 << 31) b = j j = math.floor((b + 1) / rand) end return (b % upstream_num) + 1 end
同様に実験をしたところ以下のような結果になりました。偏りは十分に解消しています。
41e453ab-b48c-4fc1-b6f5-2195b232c2ec : 125042 44de4d29-7d64-4cda-b3c3-2833195d88cf : 125073 52c97967-828c-4719-88f3-71fcee03ada0 : 124892 6f95302f-d344-4e7d-895e-3e260de331e9 : 125067 81d74170-721f-4ffd-a4f7-0ce124d7be7a : 124989 9a519c85-fa22-4fcd-bef6-ce14f731e91f : 125650 9f0cd303-aa56-4481-af4d-4967e6df104c : 123606 eb7465be-56bf-4784-9a3d-546fc8759295 : 125682 key moved : 12.5067% 41e453ab-b48c-4fc1-b6f5-2195b232c2ec : 142775(0.00 % moved) 44de4d29-7d64-4cda-b3c3-2833195d88cf : 142739(0.00 % moved) 52c97967-828c-4719-88f3-71fcee03ada0 : 141880(0.00 % moved) 6f95302f-d344-4e7d-895e-3e260de331e9 : 0(100.00 % moved) 81d74170-721f-4ffd-a4f7-0ce124d7be7a : 142525(0.00 % moved) 9a519c85-fa22-4fcd-bef6-ce14f731e91f : 142928(0.00 % moved) 9f0cd303-aa56-4481-af4d-4967e6df104c : 142555(0.00 % moved) eb7465be-56bf-4784-9a3d-546fc8759295 : 144599(0.00 % moved) time: 7.672456 seconds
以下に他のアルゴリズムの計測と同様の条件でのベンチ結果を掲示します。
まず、選択対象サーバが3台、tombstoneがない状態では以下の結果になります。
-----SET RESULT----- 300000 request sent. total time (s) | 11.632 RPS | 25842.545 mean (ms) | 2.958 median (ms) | 2.743 percentile50 (ms) | 2.743 percentile90 (ms) | 4.227 percentile95 (ms) | 4.893 percentile99 (ms) | 7.261 stddev (ms) | 1.198 failureRate | 0.00% -----GET RESULT----- 300000 request sent. total time (s) | 11.279 RPS | 26630.455 mean (ms) | 2.853 median (ms) | 2.674 percentile50 (ms) | 2.674 percentile90 (ms) | 4.159 percentile95 (ms) | 4.747 percentile99 (ms) | 6.635 stddev (ms) | 1.124 failureRate | 0.00%
選択対象サーバが4台ですが、うちtombstoneが1台分ある状態でのベンチも示します。若干の劣化はありますが許容範囲かと考えます。
-----SET RESULT----- 300000 request sent. total time (s) | 12.640 RPS | 23784.500 mean (ms) | 3.234 median (ms) | 3.017 percentile50 (ms) | 3.017 percentile90 (ms) | 4.726 percentile95 (ms) | 5.458 percentile99 (ms) | 7.463 stddev (ms) | 1.260 failureRate | 0.00% -----GET RESULT----- 300000 request sent. total time (s) | 11.781 RPS | 25578.000 mean (ms) | 2.987 median (ms) | 2.756 percentile50 (ms) | 2.756 percentile90 (ms) | 4.443 percentile95 (ms) | 5.147 percentile99 (ms) | 7.265 stddev (ms) | 1.259 failureRate | 0.00%
アルゴリズムの改善についてのまとめと今後
jump consistent hashingには順番変更に弱いという問題がありましたが、アルゴリズムの工夫で克服する方法を一つ見つけることができました。jump consistent hashingと一種のオープンアドレス法を組み合わせることで、ノードが削除されても順番を崩さずに維持することができそうです。具体的工夫として、削除ノードをtombstoneとして残すアプローチやインデックス空間を広げる対応を紹介し、移動の結果を示しました。
このアプローチを実際の運用環境に適用するために、実リクエストのキーを使った追加実験なども考えています。また、tombstoneに対応した設定を生成するためのデーモンなど追加の実装が必要になるでしょう。
さらに、今回検討したアプローチがベストであるとは限らないため、これ以外にも、他の効果的な方法もいくつか検討したいと考えています。例えば、別のアルゴリズムの検討候補として、Multi-probe consistent hashingなども挙げられます。このアルゴリズムも複数のノード候補からジャンプを繰り返して最終的なノードを決定するアルゴリズムで、工夫してみると似たようなことができる可能性があります。
jump consistent hashingの弱点(2) - ノード追加時の問題
もう一点、ここまで述べてきた内容ではありますが、jump consistent hashingの特徴として、キーの移動率が全体から見て追加したノードの割合に対し、ほぼ固定になることが挙げられます。例えば、6台に対し2台追加する場合、 2 / (6 + 2) = 25% が移動することになります。
これは、キーの移動が予測しやすいという観点ではメリットですが、必ず一定の割合の移動を避けられないという点ではデメリットとなります。先ほどの例では移動率は25%ですが、全体のノードが少ない時のことを考えてみましょう。例えば3台に対し2台追加したい場合、移動率は 2 / (3 + 2) = 40% です。1台だけにしても移動率は 25% となり、これより低い割合に抑えることはできません。一般に、ノード数が少ない時の操作で影響が大きくなりがちと言えます。
このような台数が少ない時の変化は、他のアルゴリズムであればいくつか回避策を検討できます。
- consistent hashing(virtual node)の場合、新しく追加するnodeのreplica数を徐々に増やしていけば、キーの移動を徐々に行うことが可能になります。
- 例えば、replicaが5として、3台に対し1台追加するならば、最初はその1台だけreplica = 1 とすれば全体としては
1 / (3*5 + 1)= 2.17% 程度のキーしか影響を受けないはずです。このreplica数を、一定の期間を置きつつ徐々に1つずつ増やして5にすれば、急激なキーの移動を抑えられるはずです。 - 削除の場合も、同様にreplica数を1つずつ減らすことで対応できそうです。
- 例えば、replicaが5として、3台に対し1台追加するならば、最初はその1台だけreplica = 1 とすれば全体としては
- rendezvous hashingの場合、例えば「N台のうちから2台を選ぶ」として、その2台のうちどちらかにキーが存在すればhitという実装を取れば移動の影響を軽減できます。
- あるキーに対し、ノードのスコアが
{a, b, c}と並んで、その先頭の2台を取得するとしましょう。この時、ノードdが追加されたら{_ a _ b _ c _}のどこかに挿入されるでしょうが、どこに挿入しても、先頭の2台を取得した場合aかbのどちらかは残っています。したがって、一方はhitさせることが可能だとわかります。
- あるキーに対し、ノードのスコアが
あるいは、jump consistent hashingの使い方を工夫することでも軽減できる可能性があります。アイデアは色々と出てくるでしょう。いずれにせよ深掘りして検討する必要がありそうです。
6. まとめ
サーバ選択アルゴリズムについてのまとめ
今回のインターン課題を通じて、memcached proxyで使うためのいくつかのハッシュアルゴリズムの特性やその適用可能性について理解を深めることができました。その結果、RPSの面ではjump consistent hashingが有利そうな一方、サーバ追加の場合の挙動など実運用面ではconsistent hashingなどにもメリットがあることが分かりました。 ただ、アルゴリズムの特徴は見えましたが、実運用に向けては次に紹介するキーの冗長化の課題などが残されています。
さらに、これらのアルゴリズムを検証環境や、ごく一部本番環境のリクエストを流すことでテストし、そのパフォーマンスを詳細に評価することも重要だと考えています。今回のインターンの期間ではそこまでの検証ができず悔しい限りですが、引き続きインフラチームの皆さんで進めてもらえることと思います。
今後の更なる課題
また、今回のインターンの課題ではサーバ選択時のハッシュテーブルアルゴリズムにテーマを絞っていましたが、memcached proxyで検証したい内容は他にも存在します。
重要なテーマの一つとしては、キーの冗長書き込みがあります。
memcachedにおけるキーの冗長書き込みについて具体例を示します。
まず、例えば foo:bar というキーがあった時、以下のような実装を行い、最終的に読み取り先の分散をさせるパターンが挙げられます。
- 書き込み時は 1 ~ 8までのsuffixを付与し、
foo:bar:1foo:bar:2foo:bar:3、...foo:bar:8を同時に書き込む- これに伴いハッシュ値が変わるので、書き込む先のサーバが分散する
- 読み取り時は、 1 ~ 8までのsuffixをランダムに一つ付与して
foo:bar:$RANDOMとして取得- その結果読み取る先のサーバを毎回変えられて、分散できる
他にも、Availability Zoneを意識した冗長書き込みも考えられます。
パブリッククラウドにはAvailability Zoneという機能があります。同じAvailability Zoneのインスタンスは物理的に同一または近いホストサーバを持っています。現代的なクラウドの上でミドルウェアを運用するにあたっては、可用性やパフォーマンスを考えてAvailability Zoneをまたいだクラスタの設計をすることが重要です。
memcachedの場合も複数のAvailability Zoneに同じキーを同時に書き込み、さらに読み取るときはクライアントがあるサーバと同じAvailability Zoneから読み取らせることで、ネットワーク的な距離が短いサーバを利用でき、ゾーン障害などの影響も抑えられやすくなります
他にも、上記のような冗長書き込みの実装を行うことで、キー移動時やeviction（memcachedが書き込みきれない時に強制的に古いキーを削除する挙動）の際のキャッシュミスの可能性を軽減することも期待できます。
そしてキーの冗長書き込みも、クライアント側で実装するパターンと、memcached proxyで吸収させるパターンが考えられます。それぞれの場合のメリット・デメリットや具体的な実装の例を検証することも今後の課題としたいと思います。
hibiki個人としての感想
今回のインターン課題を通じて、ハッシュアルゴリズムの奥深さとその応用の広さを実感しました。特に、jump consistent hashingのようなシンプルかつ強力なアルゴリズムのメリットを活かしつつ、その弱点を克服するための新たなアプローチを考える過程はとても楽しかったです。パフォーマンスを監視する際に結果となるRPSだけでなくvmstatなど多角的な要素を見てボトルネックを探し出すことで調整と最適化ができることを学べました。この経験を通してこれからの学習に繋げていきたいと思います。
ミラティブでのインターンを通じて、少人数でありながらも多くの内製技術を持ち、高いパフォーマンスを追い求めているエンジニアチームに驚きました。 非常にパワフルなエンジニアの集団の中で働くことで、自分の力不足を感じることもありましたが、それ以上に身につけたい知識やアーキテクチャの理解が増えました。この環境で学んだことは、今後の成長に大いに役立つと思います。
今回のタスクでインフラチームの方々にはたくさんの助けをいただきました。hataさんには様々なアルゴリズムについてのヒントをいただきました。kondoさんには実装が詰まったときや今回のブログに関してもたくさんの手助けをいただきました。ありがとうございました。
We are Hiring!
ミラティブでは、アルゴリズムを実運用に応用することに興味があるメンバーや、粘り強い検証が得意なメンバーを募集しています！
ご興味が出た方は上記資料をご覧ください。
