昨日、AmplitudeがSetデータ型の利用という文脈で、分析処理のスケーリングに関する記事を公開しました。ブログ記事はこちらです: https://amplitude.com/blog/2015/08/25/scaling-analytics-at-amplitude/

Hacker Newsでは、なぜ代わりにRedisを使わないのかという声が上がっていました: https://news.ycombinator.com/item?id=10118413

Amplitudeの開発者たちがRedisを使わないのにはそれなりの理由があるでしょうし、そもそも非常に特化した問題を抱え、それを可能な限り最適な形でスケールさせたいのであれば、垂直統合的な自前ソリューションを実装するのは理にかなっています。私は車輪の再発明に否定的ではありません。汎用的なシステムでは提供できない、まさに自分たちにぴったり合った車輪が必要なこともあるからです。さらに、自前で作ることで自分たちが作ったものへのコントロールが得られ、創造性や開発者としての自信も高まりますし、将来どんなバグが発生しても外部の助けなしでデバッグできるようになります。

一方で、もちろんシステムソフトウェアをゼロから作るのは非常に複雑なことです。積極的に開発を続けたいのであれば継続的な開発が必要ですし、専任のチームがいなければ、開発が停滞し進化しないコードを抱えることになります。非常に垂直的で特化したものであれば、新しいシステムはアプリケーション全体の問題のごく一部しか扱えない可能性が高いにもかかわらず、それでも追加のコンポーネントとして管理しなければなりません。さらに、もしそれが主に一人か少数のプログラマーによって作られ、その人たちが後に会社を去ってしまった場合、修正や改善は非常に大きな問題になります。規模のある外部コミュニティもいなければ、オリジナルの開発者もいないわけですから。

基本的に、内製するかどうか自体に良いも悪いもなく、ケースバイケースです。もちろん、ゼロから実装する価値があるときとそうでないときを見極めるのはセンスの問題です。優れた開発者ならそれが分かっています。

私の視点からすれば、Amplitudeの開発者が最終的にどのようなソリューションに至ったかにかかわらず、そのプロセスやなぜRedisを使わなかったのかを読むのは興味深いことです。彼らが指摘した懸念の一つは、RedisのSetデータ型のオーバーヘッドでした。彼らがそう懸念するのはもっともだと思います。RedisのSetはもっとメモリ効率を高められるはずですし、Amplitudeの記事を読む数週間前から、私はすでにSetのメモリ効率を改善する方法を模索し始めていました。今日はその計画を皆さんと共有したいと思います。

データ型の二重表現

当初は、良くも悪くもアルゴリズムの教科書通りの素朴なデータ構造でした。データ構造の各ノードを動的に確保して実装するものです。アロケーションのオーバーヘッド、肥大化したポインタ、キャッシュ局所性の低さが、この基本的な手法の大きな制約でした。

後にPieter Noordhuisと私は、Redisの抽象データ型について、非常にメモリ効率の良い専用の実装を導入しました。1回の確保で数十から数百の要素をまとめて保持し、空間をより有効に使うためにアドホックなエンコーディングを用いることもあります。そうしたデータ構造は、特定の操作で時間計算量がO(N)になったり、要素が特定の形式（数値）やサイズに限定されたりすることもあります。

たとえばHashを作成すると、最初は少量の要素に適したメモリ効率の良い方法で表現されます。その後、要素数が一定のしきい値に達すると、本物のハッシュテーブルに変換されます。つまり、Redisのデータ型のメモリ効率は、格納する要素数に大きく依存するということです。

次のステップ：Redisのリスト

あるとき、Twitterの開発者たちは、リストの要素を単一のアロケーションによる配列で表現している状態から、はるかにメモリ効率の悪い実際の連結リストへ移行する理由はないことに気づきました。その中間にあたるものがあります。少数の要素を表す配列の連結リストです。彼らの実装では、途中の要素を削除した際のデフラグを扱っていませんでした。Pieterと私は以前、この手法に価値があるかどうかを検討しましたが、デフラグにかかるコストは節約できる容量に見合わないのではないかという感触があり、デフラグを行わない実装は汎用的なRedisのリスト実装としては脆すぎました。中間の要素をいくつか削除しただけで、メモリ使用量が劇的に変わってしまうからです。

幸い、Matt Stancliffがデフラグの部分も含めてこのアイデアを素晴らしい形で実装し、いくつかの実験を経て、新しい実装はパフォーマンスの観点からはRedisの現行実装と少なくとも同等であり、メモリ使用量の観点でははるかに優れていることを示しました。さらに、リストのメモリ効率はもはやリストのサイズに依存しなくなり、扱うべき表現も一つに統一されました。

リストはやや特殊です。小さな配列の連結リストというのは本当に最適な表現ですが、他のデータ型にそのまま当てはめられるとは限りません。Setや他のデータ型でも同じようなことは可能でしょうか？

RedisのSet

Setのメモリ使用量は少し特殊です。他のすべてのRedisデータ構造のように、文字列で構成された集合のための専用表現を持っていません。そのため、非常に小さなSetでも多くのメモリを消費してしまいます。実際に優れた専用表現は存在するのですが、Setが数値だけで構成され、かつ小さい場合にしか機能しません。その場合、Setは「intset」と呼ばれる特別なエンコーディングで表現されます。これはソートされた整数の線形配列で、メンバーの存在確認に二分探索を使えるようになっています。配列は、集合内の最大の要素に応じて各要素のサイズを自動的に変えるため、たとえば文字列の「1」「20」「30」「15」からなる集合を表現する場合、文字列は数値として表現でき、8ビットの範囲に収まるので、要素あたりわずか1バイトと多少のオーバーヘッドで済みます。しかし、そこに「a」を1つ追加するだけで、完全なハッシュテーブルに変換されてしまいます。

127.0.0.1:6379> sadd myset 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding myset
"intset"
127.0.0.1:6379> sadd myset a
(integer) 1
127.0.0.1:6379> object encoding myset
"hashtable"

整数のSetはRedisで非常によく使われるデータ型なので、この仕組みは実際とても有用です。では、なぜ他のデータ型のように、非数値の文字列からなる小さな集合のための専用表現がないのでしょうか？ それは、1つのデータ型に*3つ*の表現を持たせることは、Redisの内部構造の観点から良いことではないと考えたからです。t_zset.cやt_set.cを見れば、複数の表現を扱うにはそれなりの注意が必要なことが分かります。N個の表現を抽象化して隠蔽しようとすればするほど、特定の最適化ができなくなります。さらに、リストの事例が示したように、すべての利点を備えた単一の表現を持つことは可能です。N個の要素を含む小さな塊を走査することで失うものは、キャッシュの局所性が向上することで取り戻せるため、一見すると深刻な時間と空間のトレードオフに見えることでも、実際にはそうではないものについて実験することが可能なのです。

Redisハッシュテーブルの特化

大きなハッシュ、非数値（あるいは大きな）セット、そして大きなソート済みセットは、現在ハッシュテーブルで表現されています。実装はdict.cファイル内のものです。これは衝突解決にチェイン法を用いた、かなり素朴な実装のハッシュテーブルです。このハッシュテーブル実装の特別な点は2つだけです。リハッシュのためにブロックすることが決してなく、リハッシュの過程がインクリメンタルに処理されることです。これはVMwareのスポンサーシップを受け始めて最初の数ヶ月に私が実装したもので、もちろんレイテンシの面で大きな成果でした。dict.cはさらに、Pieter Noordhuisが考案した「scanning」と呼ばれる特別なプリミティブも実装しています。これはオーバーヘッドも状態も持たないカーソルベースのイテレータですが、妥当な保証を備えています。それ以外では、Redisのハッシュテーブルはキーと値が何かへのポインタであることを想定し、キーを比較・解放したり、値を解放したりするためのメソッドを備えています。

これが汎用ハッシュテーブルとして望まれる設計です。至るところで値の扱いにポインタとメソッド（関数ポインタ）を用いるのです。しかし、Redisのデータ構造には興味深い特性があります。複合データ構造内のすべての要素は、意味的には常に文字列なのです。ハッシュは文字列フィールドと文字列値の間のマップであり、Setは文字列の順序なし集合であり、といった具合です。

では、文字列のキーと文字列の値だけを格納するように設計されたハッシュテーブルを実装したらどうなるでしょうか。そうすると、そのようなハッシュテーブルを非常にメモリ効率良くするシンプルな方法があるように思えます。ロードファクターを1より大きい値、たとえば10に設定するのです。そうすれば、ハッシュテーブルに5つのバケットがあれば、各バケットには平均して10個の要素が格納されることになります。

各バケットは、現在小さなデータ型で使っているエンコーディングと非常によく似た形で、長さを前に付けたキーと値のアイテムの線形配列のようなものになります。例えば次のようなものです。

0: <3>foo<3>bar<5>hello<6>world!<0>
1: <8>user:103<3>811 … <0>
2: … <0>

といった具合です。エンコーディングは専用のものにしても、MessagePackのような既存のものを使っても構いません。ここでの各バケットにおける余分な処理は、得られる局所性の向上によって相殺されることが期待できます。

このデータ構造の上にscanningやインクリメンタルなリハッシュを実装することも可能です。初期的な分析は行いましたが、dict.cの実装をそのままコピーすることはできないものの、同じ効果を得るための別の方法を見つけることは可能です。

なお、技術的に言えば、このようなハッシュテーブルにポインタを格納することも可能です。ハッシュテーブルの実装から見れば、それらは単なる文字列として扱われ、ハッシュテーブルの型の中で、それらが特別な扱いを必要とするポインタであること（例えば、値を解放する関数ポインタなど）を示すこともできます。ただし、それがやる価値があるかどうかはテストしてみなければ分かりません。

ただし、これをSet以外にも使うためには、あるいは少なくとも現在ある小さな表現を廃止して*単一の*表現だけを使うためには、解決すべき問題があります。例えば、現在の小さな表現には非常に興味深い特性があります。それ自体がすでにシリアライズされた形になっており、余計な処理を必要としないのです。私たちはこれをRDBファイルへのデータ保存や、Redis Clusterでのノード間でのデータ転送などに利用しています。特化したハッシュテーブルも、できれば同じ特性を持つべきですし、少なくとも各バケット単体が、後処理を必要とせずにすでにシリアライズされた形式になっているべきです。もしそうでない場合でも、この新しい辞書を、拡張後の汎用ハッシュテーブルの代わりに使うだけでも、すでに大きな成果となります。

結論

これはまだ初期段階のアイデアであり、設計を改善し、後に実装によって検証し、特定の正当なワークロードで大きなリグレッションがないことを保証するために徹底的な負荷テストを行うには、ある程度の時間が必要です。すべてがうまくいけば、これまでよりもはるかにメモリ効率の良いRedisサーバーが実現するかもしれません。このようなハッシュテーブルは、メインのRedis辞書を格納するためにも使え、各キーのオーバーヘッドを大幅に小さくできる可能性があります。