About Redis Sets memory efficiency

2015-08-28

Redis Setsのメモリ効率について

昨日、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 Setsは、メモリ効率を大幅に高められる可能性があります。Amplitudeの記事を読む数週間前には、私もすでにSetsのメモリ効率を改善する方法を探り始めていました。今日は、その計画を皆さんと共有したいと思います。

データ型の二重表現

原理的には、かつては単純なデータ構造がありました。アルゴリズムの教科書が示す方法に近い形で実装され、データ構造の各ノードを動的にメモリ確保していました。メモリ確保のオーバーヘッド、サイズの大きいポインタ、キャッシュ局所性の低さが、この基本的な解決策の大きな限界です。

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

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

次の段階：Redisのリスト

ある時点で、Twitterの開発者たちは、Listの各アイテムを表す、1回のメモリ確保で済む要素配列から、メモリ効率がはるかに低い実際のリンクリストへ移行する理由はないと気づきました。その中間にあたるものがあります。少数のアイテムを表す配列のリンクリストです。彼らの実装は、途中の要素を削除したときのデフラグメンテーションに対応していません。過去にPieterと私は、この方法に価値があるかどうかを検討しました。しかし、デフラグメンテーションにかかるコストが、節約できる空間で埋め合わせられないのではないかという感触がありました。また、このアイデアをデフラグメンテーションなしで実装すると、Redisの汎用的なリスト実装としては脆すぎます。途中の要素をいくつか削除するだけで、メモリ使用量が劇的に変わってしまうからです。

幸い、Matt Stancliffがデフラグメンテーション部分も含め、このアイデアを素晴らしい形で実装してくれました。いくつか実験した結果、彼は新しい実装が、性能の観点ではRedisの現行実装と少なくとも同等であり、メモリ使用量の点でははるかに優れていることを示しました。さらに、リストのメモリ効率はリストのサイズに左右されなくなり、扱う表現も一つで済みました。

少数の配列をリンクしたリストは本当に最適な表現であり、他のデータ型にそのまま当てはめるのは難しいかもしれないため、リストは少し特殊です。Setsや他のデータ型でも、同じようなことは可能でしょうか？

Redis Sets

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

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で非常によく使われるデータ型なので、この機能があるのは実際にとても有用です。しかし、他のすべてのデータ型にあるように、数値ではない文字列で構成された小さなSet向けの専用表現がないのはなぜでしょうか？それは、*3つ*の表現を持つデータ型は、Redisの内部実装の観点からは良くないだろうと考えたからです。t_zset.cやt_set.cを確認すれば、複数の表現を扱うには相応の注意が必要だと分かるでしょう。N個の表現を扱う処理を抽象化しようとすればするほど、特定の最適化にアクセスできなくなります。さらに、Listの経緯から、すべての利点を備えた単一の表現が可能だと分かりました。N個の要素を含む小さな集合を走査する際に失うものは、キャッシュ局所性が向上することで取り戻せます。そのため、時間と空間のトレードオフが悲惨に見えるものでも、実際にはそうではない方法を試すことが可能です。

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

大きなHash、数値ではない（または大きな）Set、大きなソート済みSetは、現在ハッシュテーブルで表現されています。実装はdict.cファイル内にあります。衝突の解決にはチェイニングを使う、かなり単純なハッシュテーブルです。このハッシュテーブル実装の特殊な点は、たった二つです。リハッシュのために処理をブロックすることがなく、リハッシュ処理を段階的に行うこと。そして、VMwareのスポンサーシップを受け始めた最初の数か月に私が実装したもので、もちろんレイテンシの面で大きな成果がありました。dict.cには、Pieter Noordhuisが発案した「scanning」という特殊なプリミティブも実装されています。これはオーバーヘッドも状態もない、カーソルベースのイテレータですが、妥当な保証を備えています。それ以外では、Redisのハッシュテーブルは、キーと値が何らかのものへのポインタであり、キーの比較・解放と値の解放を行うメソッドを持つことを前提にしています。

汎用ハッシュテーブルは、このように設計するものです。どこでも値を扱えるように、ポインタとメソッド（関数ポインタ）を用意します。しかしRedisのデータ構造には、興味深い性質があります。複雑なデータ構造に含まれるすべての要素は、意味上は常に文字列なのです。Hashは文字列のフィールドと文字列の値の対応関係です。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辞書を格納するためにも使えます。そうすれば、各キーのオーバーヘッドを大幅に小さくできます。