CubeDB：多次元キーを備えた最小限のカウンターストア

こんにちは、Habr！ 私の名前はディマ・スタンコです。ロンドン事務所のBadoo BIチームで働いています。 当社では、ユーザーアクティビティのできるだけ多くの測定を実行しようと試みました。 これは多くの専門家にとって必要です：開発者はコードの作業能力をテストし、製品チームの同僚はアイデアの天才を確信しています。

レーキを踏んで他の人に話さないのは良くないと考えているので、これについて何度も書きました。

モバイル分析

数年前、Badooはモバイルアプリケーションでのユーザーアクションを分析する必要がありました。 誰かがボタンをクリックし、画面をロードし、アプリケーションを開き、メッセージを書くたびに、私たちはこのことに関する通知を受け取り、喜んでいました。 1日に数億回。

間もなく、ユーザーを画面の最後までスクロールしたり、別のユーザーのプロファイルを表示したり、ギフトを送信したりするなど、より特殊なケースで喜ぶ必要がありました。 しかし、これは製品チームの同僚にとっては十分ではありませんでした。 そこで、モバイルアプリケーションを追跡するシステムであるHotpanelを取得し、今日では1日あたり合計120億回で約320種類の通知を受け取ります。 このような美しさを隠すことは単なる罪であるため、私たちは間違いなくこれについて書きます。

Hotpanelインターフェースの主要コンポーネントの1つは、さまざまな内訳の時間別および日別のチャートです。 写真で説明できるものを千の言葉で説明してください、それは意味をなさないので、ここに：

フィールドの任意の組み合わせでフィルタリングできます：

背景

私が唯一の開発者であり、メッセージがほとんどなかったこのプロジェクトの夜明けに、ディスプレイの問題を非常に迅速に、安価に、怒って解決しましたが、 残念ながら 、あまり効率的ではありませんでした。 Redisでは、各タイプのメッセージと各時間単位に独自のHASHMAPがあり、そのキーはフィールドとその値であり、値はそのようなフィールドの組み合わせを持つメッセージが私たちに届いた回数です。

例：

• HASHMAP: hourly:view_screen:2016-09-17名HASHMAP: hourly:view_screen:2016-09-17
• 内部のキーは次のようになりました*： screen_name=view_photo,previous_screen=welcome,platform=android,app_version=1.2.3,gender=male
• 合計値：1,500,000

これは、2016年9月17日にAndroidデバイスの男性ユーザーがアプリケーションバージョン1.2.3を開き、写真を検討するために急いだことを意味しました。

同じ日にAndroidデバイスの別の男性ユーザーがアプリケーションバージョン1.2.3を開き、写真を見るために急いだ場合 、 HINCRBYがあり、値は1500001になり、Androidの写真を担当するプロダクトマネージャーに大きな喜びをもたらしましたバージョン1.2.3。

Redisの近くにPythonとFlaskサービスがあり、Redisに接続されていました。HGETALLはすべての辞書をhourly:view_screen:2016-07-17 by hourly:view_screen:2016-10-17つの素晴らしいJSON構造を作成してマージしましたこれはすべてdc.jsのクライアント用です。 もちろん、多くの最適化がありましたが、それらについてはお話ししません。これらはすべて、**が過ぎ去った日々の出来事だからです。

すべてが驚くべきものでしたが、組み合わせはわずかでした。 速度は驚くべきものでした（ dc.jsの基礎となるCrossfilterはd3パッケージの作成者によって作成され、応答時間は30ミリ秒未満です）。 一般的に、成功でした。 長くない。

この成功は私たちを台無しにしました。 メッセージの種類の数の増加、新しいフィールドと値の出現により、組み合わせの数は日単位ではなく時間単位で増加しました。 インターフェイスを使用すると、拷問になった。 たとえば、 受信したJSONオブジェクトの最大サイズを制限するなど、エキゾチックな天井にぶつかりました。 しかし、私たちはこの「上からのサイン」を無視し、JSONを断片に分割してクライアントに接着する、トリッキーな（私たちに思えた）ソリューションを思い付きました。 別の拷問は、Web開発部門の同僚の質問でした。「あなたのページは2分で1.5ギガバイトのRAMを食べ、Chromeを殺しました、おめでとうございます！ どうやってやったの？ そして、なぜあなたはまだ私たちのために働いていますか？！」

この恥と恥に、北極圏から来た白くふわふわした客が夜にRedisと激怒し始めました。 メモリ消費量が増加し、192 GBでもそれほど多くないことが判明しました。 午前3時の監視担当者からの電話はまったく不適切でした（私の1歳半の息子でさえ、それをしませんでした！）。

一般的に、まさに下層階級は「下層階級は古い道を望んでおらず、上層階級は古い道を望めない 」 という好機です。 行動する時です。

システム要件

バックエンドにハングアップし、以下を実行できる奇跡の迷路を見つけるか、または見つける必要がありました。

1. カウンターデータを120日間保存します（これは約1億の異なる組み合わせです。非圧縮形式では約27 GBのデータです）。
2. フィールドの任意の組み合わせおよび日付範囲でフィルタリングします。 形式はfield1 in ('val11', 'val12' ... ) AND field2 in ('val21', 'val22', ...) .... AND dt between x and yインデックスが明らかであることがわかります残念ながら、私たちは助けられません。

3. 結果をファセットとして提示します。 メッセージに8つのフィールドがある場合、フィールドごとに8つの辞書を発行する必要があります。 各辞書には、可能なフィールド値ごとにカウンターが含まれている必要があります。 非常につまらないものであれば、SQLでは次のようになります。

   
   

    select 'G1' as name, G1, SUM(M) from T WHERE D2 in (DQ2) and D3 in (DQ3) ... -- skip all filters related to G1 and p between PFrom and PTo group by name, G1 UNION ALL select 'G2' as name, G2, SUM(M1) from T WHERE D1 in (DQ1) and D3 in (DQ3) ... -- skip all filters related to G2 and p between PFrom and PTo group by name, G2 UNION ALL ... UNION ALL select 'GN' as name, GN, SUM(M1) from T WHERE D1 in (DQ1) ... and D(N-1) in (DQ(N-1)) ... -- skip all filters related to GN and p between PFrom and PTo group by name, GN UNION ALL select 'p' as name, p, SUM(M1) from T WHERE D1 in (DQ1) ... and Dn in (DQn) ... group by 'name', p 

   
   
4. 新しいフィールドと新しいフィールド値が追加されても、負担をかけないでください。
5. 新しいタイプのメッセージが表示されても負担をかけないでください。
6. 結果をほぼ即座に表示します。つまり、ネットワークを含めて平均で100ミリ秒、最悪の場合-2秒間（この場合、ページにスピニングホイールをねじ込みます）。
7. 最大1分間で300万の新しい組み合わせを挿入できます。
8. 過去数日間のデータをすばやく削除できます。
9. これはすべて、既存のインフラストラクチャ、つまり、1台のマシン（192 GBのメモリ、48頭の牛）、Hadoopクラスター、または指先にあるExasolクラスターで動作するはずです。
10. これはすべてサポートが容易で、自分を監視できるようにする必要があり、なぞなぞを使って痛みを引き起こしたり話したりしないように放棄する必要があります。

状況の緩和：

1. 真の永続性は、各変更の直後にデータを保存するために必要ありませんでした。 新しいユニットは1時間に1回追加されたため、ロード後すぐにすべてをディスクに保存する必要がありました。 ただし、保存によってブロックされることはありません。
2. 各フィールドの値の数は1000以下です。
3. フィールドの数は100以下です（それらはすべてString型です）。
4. ACLなし（まだ）。
5. トランザクションなどはありません。当然、カウンターはアトミックに更新する必要があります。

中間結論：

1. 100ミリ秒で27 GBを処理できるのは、cな圧縮またはcなインデックス作成およびすべてのCPUの使用の場合のみです。
2. Key-Valueストアは役に立ちません。 RedisとTarantoolのLuaで利用できるさまざまなスクリプト機能が役立ちますが、それらはまだシングルスレッドであり、時間通りに多くのデータを処理することはできません。
3. 要件の条項4および5により、リレーショナルデータベースも機能しません。
4. Presto、Impala、およびそれらのような他の企業は、もちろんよくできていますが、100ミリ秒で何もできません。 はい、そして彼らのために100mの記録-それはスズメで銃を撃つようなものです。 HadoopとMapReduceについては、途切れることもありません。
5. DruidやInfluxDBのようなトリッキーで興味深いことはおそらくこの問題を解決するでしょうが、それらは複雑すぎます。 このために個別のクラスターをセットアップする方法はありませんでした。 私のより有能で怠zyな同僚はすでにこれについて書いています。
6. あなたはおそらくこれがすべて時系列のように聞こえることに気づいたでしょう。 はい、実際には、正面だけでなく横顔でもあります。 実際、私たちが持っているすべてのチャートは、1つの時系列ではなく、数百万の組み合わせの合計です。 そのため、時系列ストアも削除しました。

固有の有害性とすべての可能性をテストする時間の不足を考慮して、インタビューでこの問題を解決するためのツールを見つけるというタスクを単純なものにするのが好きでした。 しかし、優秀な候補者でさえ、私に励みになることは何も言えませんでした。 そのため、最後の希望であるElasticsearchは、かつてはファセット検索を目的としたものでしたが、「原子の砕氷船」には遅すぎました。

その時までに、同僚からの絶え間ない屈辱、Redisの毎晩の戦いによる通常の睡眠不足、準備ができて自由な何かを見つけることへの絶望的な希望、そしてエキサイティングな問題を解決することに正直に純粋にオタクの興味が感じられました：私の目は血でいっぱいでした、私の心が混乱し、自分で解決策を作成することにしました。

私は家で書きました、そして、すでに言及された1歳半の息子は私をカバーしました。 私たちは、彼が夕方7時に安らかに眠っている間、私は彼の保育園に座って、父親の徹夜を装ってコードを書いていることに同意しました。 その数週間は、まだ父の間に幸せであると記憶されています。

数年前、 新しい分析データベースを選択していたとき、メモリのみで動作するこれらのソリューションの速度に驚かされました。 おそらく、O（N）時間で結果を生成するデータ構造を作成するというアイデアは、インタビューでは非常に失敗しますが、実際にはこれはそれほど悲しいことではありません（これらのN個の要素がすべてメモリに共存している場合）。

中にネオンがあります

実際のところ、データの挿入方法と抽出方法の2つの問題がありました。

カウンターの取得

データストレージ用にエレガントな構造が考案されました。 特定のタイプのメッセージのすべての集計は、個別のオブジェクトに格納するよう提案されました（キューブと呼びましょう）。 最高レベルでは、これらのキューブのマップがあり、その名前がマップキーになっています。

各キューブは、時間（この場合は日と時間）でパーティション分割されます。 各パーティションには、ユニットが直列に格納されます。 新しいフィールドの追加は、これらのフィールドのマップに新しい要素を簡単に追加することで解決されます。

各フィールドの可能な値の最大数は小さいことがわかっているため、数字でエンコードできます。この場合は10ビットで十分です（ただし、タスクと予約を簡素化するために、16ビットにしました）。 これにより、メモリを節約できるだけでなく、文字列全体ではなく16ビットのみを比較する必要があるため、より高速に検索できます。 この場合、2つのタイプの列があります。値の検索に使用される列は16ビットで、カウンター自体は64ビットです。

したがって、すでにおなじみのキーscreen_name=view_photo,prev_screen=welcome,platform=android,app_version=1.2.3,gender=maleの値は1500000で、次のデータになります。1：1：1：1：1 1500000現在、5x2 + 8 = 18バイトを占めています。 節約は明らかです。

検索は、各行で、対応するフィールド値のカウンター値がカウンターフィールドの値だけ増加する単純なフルスキャンによって解決されます。

速度も良いです。 Javaの現在の実装では、Macの単一のプロセッサで1秒あたり2000万の値を簡単にコーミングできます。 ファセット検索が必要なため、フィルター値を持つフィールドだけでなく、すべてのフィールドの値を読み取る必要があります。したがって、5つのフィールドの場合、1秒あたり400万個のカウンターを取得できます。

挿入

残念ながら、このようなエレガントなデータ構造は、挿入にまったく対応していません。 各要素を挿入するためにすべてのメモリをコームする必要がある場合（たとえば100ミリ秒かかります）、300万レコード（つまり、1時間ごとに蓄積する非常に多くの組み合わせ）の挿入には約83時間かかりますが、これはどのゲートにも入りません。 無駄なCPUサイクルにとっても残念です。

一方、データは最後の数時間または数日間だけ挿入されることがわかっています。 また、何かを挿入すると、すべてのフィールドがあることもわかります。 したがって、キーがフィールドのデジタル値（1：1：1：1：1）であり、値がこの組み合わせが配置されている行番号である逆インデックスの作成を妨げるものは何もありません。 このような構造は一瞬で作成され、キー検索時間は通常ミリ秒の何分の1かです。

この場合、1秒あたり約150,000レコードの速度を達成することができました。 もちろん、これは内部呼び出しの対象となり、REST要求とネットワークのデシリアライズの時間を考慮していません。 このような逆インデックスはキャッシュ内に存在し、パーティションごとに作成されます。 数日間アクセスされていない場合は削除され、メモリが解放されます。
データのほとんどは、送信されたのと同じ（または前の）日に挿入されるため、実際には既存のリバースインデックスを持つパーティションはほとんどありません。

先ほど言ったように、検索は簡単であるため、簡単に並列化できます。 したがって、パーティションは別々のストリームで並列にコーミングされます。 サーバー上の平均8つのフィールドと48のプロセッサで、1秒あたり1億2000万行のスキャン速度を達成できます。 つまり、異なる組み合わせの数が1200万を超えない場合、設定した100ミリ秒の期間に収まります。 もちろん、これは理想的な世界ですが、私たちはほとんどそこにいます。

ディスクに保存

ディスクにデータを書き込むことは、このようなコンパクトな形式ですぐに意味があります。 辞書はファイルの先頭に書き込まれ、データ列は行ではなく数字で書き込まれます。 そして、この経済もすべて縮小しています。 奇妙なことに、Javaの場合、プロセッサ（およびgzip圧縮）が最も遅いコンポーネントであることが判明しました。 Snappyに切り替えると、ストレージ時間が60秒から8秒に短縮されました。

「すべての消防士のために」将来のシステムの互換性が失われた場合にデータを手動で再アップロードできるように、JSON形式で保存することも想定されています。

世界とのコミュニケーション

インターフェース全体はRESTを介して行われます。 これはおそらくすべてのソフトウェアの中で最も退屈な部分なので、おそらくそれについて何も書かないでしょう。 PUTによる挿入、GETによる要求、DELETEによる削除など。

Java

前述したように、私はすべてをJava言語で作成しました。 いわゆる高速言語の中で、私はその中でしかプログラミングできません。 しかし、Cではこれがさらに高速になると非常に強い疑念があります。 SIMDのような軽食は、システムを大幅に高速化すると思います。 人生の夢は、Rustでこれをすべて書き換えることです。 しかし、この段階ではパフォーマンスが私たちに合っており、息子は成長し、夕方7時に寝ることに同意しなくなったため、これを少し待つ必要があります***。

一般的に、Javaは私を幸せにし、同時に動揺させました。 フルスキャンに関しては、非常に優れたパフォーマンスがありますが、私はそれを期待していませんでした。 ガベージコレクターは、たくさんの吊り下げがあり、何も解放されていないときに絶えずパニックに陥り、私を怒らせました。 したがって、allocateDirectとunsafeを使用して、これらのデータ構造をすべてオフヒープ用に作成する必要がありました。 もちろん、これらはすべて非常にクールですが、印象は、JavaではなくCでコーディングしているということです。 ユニバースがJava言語を作成したときに、イベントのまさにそのようなバリエーションを想定していたかどうかはわかりません。

ファセット用にこれらの同じカウンタを作成する必要があったとき、ガベージコレクタはさらに私を混乱させました。 48個のプロセッサが数千の要素に対してHashMapを同時に作成すると、コレクターは人生で初めてのように動作します。 その結果、数百万行のフルスキャンは、数値から行への結果の変換と、その後のすべてのパーティションからのデータの統合よりも時間がかかりません。

プレゼント

現在、唯一のコピーには約600個のキューブが含まれており、約5億個のレコードで構成されています。 これにはすべて、約80 GBの常駐メモリと、圧縮形式（Snappy）のバックアップ（ディスク上に約5 GB）が必要です。 ディスクへの保存操作には約30秒かかります。
システムは非常に安定して動作し、 , MIN_VALUE修正した後、 , MIN_VALUE度も落ちませんでした。

未来

将来についての議論は私のお気に入りです。何でも言うことができますが、数字を示す必要はないからです。

そのため、世界を改善するいくつかのオプションがあります。

1. まず、既に述べたように、高速でマルチスレッドのデータ処理など、ガベージコレクターが全員と自分の存在を混同しないようなものにより適した言語でソリューションを書き直します。
2. 第二に、CubeDBに独自の種類と通信し、クラスター全体に成長することを教えるのは素晴らしいことです。
3. 第三に、すべてが非常に高速でメモリ内にあるため、いくつかのトリッキーなアルゴリズムをデータの近くにドラッグすることは理にかなっています。 たとえば、 Facebook Gorillaで行ったような、ある種の異常検出です。

私は明らかに時間よりも多くのアイデアを持っているので、ソリューションをパブリックドメインに置きました。 そして、あなたはこの場所を読んでいるので、おそらく疑問に思っているでしょう。 来て、見て、遊んで、使ってください。 アイデアは非常にシンプルですが、興味深いと思います。改善できることはまだたくさんあります。 がんばれ！

視覚化のないPS Dataは、音楽のないディスコのようなものです。これは、CubeDB APIを操作するためのフロントエンドコンポーネントのセットを同時にリリースし、その可能性を示すためにシンプルなページを眩惑させたためです。 ただし、デモは1コアのマシンのクラウドで実行されており、実際の処理速度を評価することは困難です。内部システムでは、実際の鉄と48コアで、速度が劇的に異なります。

*実際はそうではありません-私たちはそこにJSONですべてを保存しましたが、これは一般にひどく非効率的です。
**実際はそうではありませんでした。 取り壊すのを忘れた-使用を中止しました。 私はそれをオフにしました-すぐに監視部門の人が私に電話しました。 よくやった！
***試してみませんか？