いくつかのオブジェクトといくつかのタグがあります。 各オブジェクトには複数のタグを含めることができます。 いくつかのタグは非常にまれで、いくつかは一般的です。 1つのオブジェクトを1つのタグに複数回関連付けることができます。
新しいオブジェクト、タグ、およびそれらの間のリンクが継続的に追加されます。
タスクは、「タグAまたはBを持ち、タグCを持たないオブジェクトの数」などの質問にすばやく答えることです。 データの読み込みを停止せずに、このようなリクエストに10分の1秒で応答したいと思います。
今日まで彼らからデータを受け取り、4台のマシンのテストクラスターを展開し、最大のパフォーマンスを得るためにデータを正しく配布する方法と、SQLクエリの形式でタスクを正しく提示する方法について考え始めました。 その結果、彼らはリクエストが次のようになると判断しました。
SELECT COUNT(*) FROM ( SELECT object_id, (MAX(tag == A) OR MAX(tag == B)) AND MIN(tag != C) AS good FROM tags WHERE tag IN (A, B, C) GROUP BY object_id ) WHERE good == 1;
このようなリクエストを迅速に実行するために、object_idによってクラスターサーバー間でデータを分割し、各サーバー内でタグでデータを並べ替えました。 したがって、リクエストを実行するサーバーは、データを含むすべてのサーバーに変更を加えずにリクエストを送信し、その結果を単純に加算できます。 データを持つ各サーバーで、リクエストを完了するには、タグA、B、Cの行を見つけ（タグのデータがソートされているため、これは簡単な操作です）、これらの行で1つのパスでリクエストを実行するだけで十分です。 最悪のタグには数千万のオブジェクトがあります;数千万行で数千万の行を処理することが可能であるようです。
サブクエリにGROUP BY object_idが含まれていることに注意してください。 この状況でのGROUP BYはいくつかの方法で実行できます。たとえば、タグの後のデータがobject_idでソートされる場合、マージソートと同様のことができます。 ただし、この状況では、object_idデータをソートせず、オプティマイザーはGROUP BYを実行するためにハッシュテーブルを構築する必要があると合理的に判断しました。
すべてのデータをクラスターにロードし、リクエストを開始しました。 要求には25秒かかりました。
何かがおかしかった。
まず、問題が発生した場所を特定するために、GROUP BY object_idを削除しました。 要求は予想される0.3秒で終了しました。 したがって、データの読み取りは十分に高速であり、ネットワークを介してそれ以上送信されることはありません。 問題はハッシュテーブルのどこかにあります。
デバッグサーバーを展開し、さまざまな統計情報をログに書き込み始めました。 しばらくして、ハッシュテーブルでは、ハッシュ関数の一部の値が他の値よりもはるかに頻繁に表示されることが明らかになりました。 チェーンの数がテーブル内のレコードの数よりも多いという事実にもかかわらず、最も長いチェーンの長さは約32でした。したがって、ハッシュ関数を使用したものは間違っています。 実装を開いて、次のようなものを見ました：
uint64_t hash(uint64_t value) { return value * MULTIPLIER1; } uint64_t accumulateHash(uint64_t hash, uint64_t value) { hash ^= hash >> SHIFT1; hash += value; hash ^= hash >> SHIFT2; hash *= MULTIPLIER2; return hash; }
ビートゲームは非常に疑わしいようでした。 このコードを書くときに関数をもっと混乱させるのは良い考えだと誰かがはっきりと思っていましたが、やり過ぎたようです。 XORとSHIFTを使用して両方の行をコメントアウトし、クラスターを再起動しました。 リクエストは0.5秒で終了し、勝利しました。
翌朝、私はこれらの2行を最初に書いたのは誰かを調べることにしました。 gitを非難し、不運なコミットを見つけました。 興味深いことに、このコミットでは、これらの変更のうち、これらの2行のみがサーバーコードに追加されました;それ以前は、summumHash関数は合計と乗算で構成されていました。 ただし、これらの2行を追加することに加えて、コミットの作成者は、いわゆる雪崩テストも追加しました。これは、入力番号の変更（最も重要ではない場合でも）がハッシュ関数の完全にランダムな変更につながることを確認するテストです。 このテストは、科学のいくつかの候補の出版物に基づいており、合理的であると思われました。 同時に、テストはXORとSHIFTなしではパスしませんでしたが、一緒にパスしました。 つまり、コミットの作成者は混乱を招く関数を書くだけでなく、自分が何をしていたかを理解していました。 しかし、実際に関数が予測不可能に動作するのはなぜですか？
この問題に対処するために、タグの1つのデータをローカルマシンにダウンロードし、実験を開始しました。 実際、現在のハッシュ関数は衝突を引き起こしました。すべての値が同じ上位5ビットを持ちました。 ただし、他のSHIFT1およびSHIFT2を使用した同じ機能では、すでに良好な結果が得られています。 次に、ランダムな1,000万個の数字を生成し、不良ハッシュ関数を使用してハッシュテーブルを再構築しました。 今回も異常な衝突はありませんでした。 つまり、乱数では、ハッシュ関数はうまく動作し、問題はハッシュ関数とユーザーデータの交点のどこかにあります。 彼はユーザーデータのパターンを探し始めました。 パターンがあります。それらはすべて64で除算され、すべて同じ上位5ビットを持ちます。 同じ上位5ビットで64の倍数である一連の乱数を生成します。 いいえ、とにかく衝突はありません。 他に何が問題なのでしょうか？ オブジェクトの生成方法がハッシュ関数を何らかの形で平準化する可能性はありますか？
翌日、クライアントからこれらのIDを正確に生成する方法を確認することに決めたので、同僚の1人が私に尋ねたとき、私はほとんど家に帰る準備ができていました：サーバー間で壊れた？
はい、これは実際に同じ列です。 コードのバグにより、GROUP BYのパーティション分割と実行に同じハッシュ関数が使用されたことがわかりました。 4つの物理サーバーにはそれぞれ8つのパーティションがあり、合計32のパーティションがあり、ハッシュ関数の最上位ビットがパーティションの選択に使用されます。 その結果、1つのセクション内のすべての行について、object_idからのハッシュ関数値の上位5ビットは同じになります。 関数ハッシュでXORとSHIFTをコメントアウトし、クラスターを再起動したとき、データをリロードしなかったため、問題が修正されたように見えました。これは、GROUP BYに使用される関数とは異なる関数のハッシュによってデータが分割されたためです。しかし、最新のデータのダウンロードを開始した場合、最終的には問題が再び感じられたでしょう。
ハッシュ関数を雪崩テストに合格する形式に戻し、パーティション化のためにハッシュ関数を変更しました。同僚の1人が面白い話を共有しました。プログラミングの競争で、彼はJavaで2次元座標にハッシュテーブルを作成しました。 座標はそれぞれ32ビットの2つの数値であり、コードが効率的に機能するように、彼はそれらを1つの64ビットの数値に書き留めてハッシュテーブルに入れました。 残念ながら、Javaではハッシュ関数が上位32ビットと下位32ビットのXORを計算し、それによりXがYである座標に対して常に同じ値を生成するため、タスクは時間内に通過しませんでした。