VKontakteメッセージベースをゼロから書き直して生き残る

ユーザーは疲労を知らずにお互いにメッセージを書きます。



これはかなりたくさんあります。 すべてのユーザーのすべてのメッセージを読みたい場合、15万年以上かかります。 あなたがかなり盛り上がった読者であり、各メッセージに1秒以下しか費やさないと仮定します。



このような大量のデータでは、ストレージの論理とそれらへのアクセスを最適に構築することが重要です。 さもなければ、それほど素晴らしい瞬間ではないが、すぐにすべてがうまくいかないことが判明するかもしれません。



私たちにとって、この瞬間は1年半前に来ました。 どうやってこれに至り、最終的に何が起こったのか、順番に伝えます。

背景

最初の実装では、VKメッセージは多くのPHPバックエンドとMySQLで機能しました。 これは、小規模な学生サイトにとって完全に通常のソリューションです。 しかし、このサイトはramp延しており、それ自体のデータ構造の最適化を要求し始めました。



2009年の終わりに、最初のテキストエンジンリポジトリが作成され、2010年にメッセージが転送されました。



テキストエンジンでは、メッセージは一種の「メールボックス」であるリストに保存されていました。 このような各リストは、これらすべてのメッセージの所有者であるuidによって決定されます。 メッセージには、対話者の識別子、テキスト、添付ファイルなどの一連の属性があります。 メールボックス内のメッセージ識別子はlocal_idであり、変更されることはなく、新しいメッセージに順番に割り当てられます。 「ボックス」は独立しており、エンジン内で相互に同期しません。それらの間の接続は既にPHPレベルです。 ここからデータ構造とテキストエンジン機能を見ることができます。



これは、2人のユーザーの通信には十分でした。 次に何が起こったと思いますか？



2011年5月、VKontakteは複数の参加者（マルチチャット）と話し始めました。 彼らと協力するために、メンバーチャットとチャットメンバーという2つの新しいクラスターを作成しました。 1つ目はユーザーによるチャットに関するデータを保存し、2つ目はチャットによるユーザーに関するデータを保存します。 リスト自体に加えて、これは、たとえば、招待ユーザーとチャットへの追加時間です。



「PHP、チャットにメッセージを送信しましょう」とユーザーは言います。

「さあ、{ユーザー名}」とPHPは言います。



このスキームには短所があります。 同期は依然としてPHPに委ねられています。 大きなチャットとメッセージを同時に送信するユーザーは危険な話です。 テキストエンジンのインスタンスはuidに依存しているため、チャット参加者は時差のある同じメッセージを受信する可能性があります。 進歩が止まっている場合、これで生きることができます。 しかし、そのようになることはありません。



2015年の終わりに、コミュニティの投稿を開始し、2016年の初めに、それらのAPIを公開しました。 コミュニティに大規模なチャットボットが出現すると、負荷分散の均一性が忘れられる可能性があります。



優れたボットは1日に数百万のメッセージを生成します-最もおしゃべりなユーザーでさえ、そのようなことを自慢することはできません。 そして、これは、これらのボットが住んでいたテキストエンジンのいくつかのインスタンスが最大限になり始めたことを意味します。



2016年のメッセージエンジンは、100のチャットメンバーとメンバーチャット、およびそれぞれ8000のテキストエンジンです。 それらは、それぞれ64 GBのメモリを備えた1000台のサーバーに配置されました。 最初の緊急対策として、メモリをさらに32 GB増やしました。 予想予報。 大きな変更がなければ、これで約1年間は十分でした。 鉄を手に入れるか、データベース自体を最適化する必要があります。



アーキテクチャの特性により、複数の鉄のみを構築することは理にかなっています。 つまり、少なくとも車の数の2倍です-明らかに、これはかなり高価な方法です。 最適化します。

新しいコンセプト

新しいアプローチの中心はチャットです。 チャットには、それに関連するメッセージのリストがあります。 ユーザーにはチャットリストがあります。



最低限必要なのは、2つの新しいデータベースです。

• チャットエンジン。 これはチャットベクトルリポジトリです。 各チャットには、それに関連するメッセージのベクトルがあります。 各メッセージには、チャット内のテキストと一意のメッセージ識別子chat_local_idがあります。
• ユーザーエンジン。 これは、ユーザーベクトルのリポジトリ-ユーザーへのリンクです。 各ユーザーには、peer_idベクトル（対話者-他のユーザー、マルチチャット、またはコミュニティ）とメッセージベクトルがあります。 各peer_idには、それに関連するメッセージのベクトルがあります。 各メッセージにはchat_local_idがあり、このユーザーの一意のメッセージ識別子はuser_local_idです。

新しいクラスターは、TCPを使用して相互に通信します-これにより、要求の順序が変更されないことが保証されます。 それらのリクエストと確認はハードドライブに書き込まれます。したがって、エンジンの障害または再起動後、いつでもキューの状態を復元できます。 ユーザーエンジンとチャットエンジンはそれぞれ4千個のシャードであるため、クラスター間のリクエストキューは均等に分散されます（ただし、実際にはまったく存在せず、非常に高速に動作します）。



ほとんどの場合、データベース内のディスクの操作は、バイナリ変更ログ（binlog）、静的スナップショット、およびメモリ内の部分的なイメージの組み合わせに基づいています。 変更は日中にbinlogに書き込まれ、現在の状態のスナップショットが定期的に作成されます。 スナップショットは、目的に合わせて最適化されたデータ構造のコレクションです。 タイトル（画像のメタインデックス）と一連のメタファイルで構成されます。 ヘッダーは常にRAMに保存され、画像からデータを探す場所を示します。 各メタファイルには、近い時点で必要になる可能性が高いデータが含まれています。たとえば、1人のユーザーを参照します。 スナップショットヘッダーを使用してデータベースにクエリを実行すると、目的のメタファイルが読み取られ、スナップショットの取得後に発生したバイナリログの変更が考慮されます。 このアプローチの利点については、 こちらをご覧ください 。



同時に、ハードドライブ自体のデータは1日1回だけ変更されます。モスクワの深夜、負荷が最小のときです。 このため（ディスク上の構造は日中一定であることがわかっているため）、ベクトルを固定サイズの配列に置き換える余裕があり、それによってメモリで勝ちます。



新しいスキームでメッセージを送信すると、次のようになります。

1. PHPバックエンドは、ユーザーエンジンを呼び出してメッセージを送信します。
2. user-engineは、要求を必要なchat-engineインスタンスにプロキシします。このインスタンスは、chat_local_idをuser-engineに返します。これは、このチャット内の新しいメッセージの一意の識別子です。 Chat_engineは、すべてのチャット受信者にメッセージを送信します。
3. user-engineはchat-engineからchat_local_idを受け取り、PHPに返しますuser_local_id-このユーザーの一意のメッセージ識別子。 この識別子は、たとえば、APIを介してメッセージを処理するために使用されます。

ただし、実際にメッセージを送信することに加えて、さらにいくつかの重要なことを実装する必要があります。

• サブスクリプションは、たとえば、ダイアログのリストを開いたときに表示される最新のメッセージです。 未読メッセージ、タグ付きメッセージ（「重要」、「スパム」など）。
• チャットエンジンでメッセージを圧縮する
• ユーザーエンジンでのメッセージキャッシング
• 検索（すべてのダイアログ内および特定のダイアログ内）。
• リアルタイム更新（ロングポーリング）。
• モバイルクライアントにキャッシュを実装するための履歴を保存します。

すべてのサブリストは急速に変化する構造です。 それらを使用するには、 Splay treesを使用します 。 この選択は、ツリーの最上部にスナップショットからのメッセージのセグメント全体を時々格納するという事実によって説明されます-たとえば、夜間のインデックス再作成後、ツリーはサブリスト内のすべてのメッセージが配置される1つの頂点で構成されます。 スプレイツリーを使用すると、バランスを考慮することなく、このような頂点の中央で挿入操作を簡単に実行できます。 さらに、Splayは不要なデータを保存しないため、メモリを節約できます。



メッセージには、主にテキスト形式の大量の情報が含まれており、圧縮できると便利です。 1つのメッセージでも正確に解凍できることが重要です。 メッセージを圧縮するために、独自のヒューリスティックを備えたハフマンアルゴリズムが使用されます。たとえば、メッセージでは単語が「単語ではない」と交互になります（スペース、句読点）。



チャットよりもユーザーがはるかに少ないため、チャットエンジンでランダムアクセスディスクリクエストを保存するために、ユーザーエンジンでメッセージをキャッシュします。



メッセージ検索は、ユーザーエンジンからこのユーザーのチャットを含むすべてのチャットエンジンインスタンスへの対角リクエストとして実装されます。 結果はすでにユーザーエンジン自体に統合されています。



さて、すべての詳細が考慮されていますが、新しいスキームに切り替えるのは残ります-そして、ユーザーがこれに気付かないようにすることが望ましいです。

データ移行

そのため、ユーザーごとのメッセージを保存するテキストエンジンと、マルチチャットとユーザーに関するデータを保存する2つのチャットメンバーとメンバーチャットクラスターがあります。 これから新しいユーザーエンジンとチャットエンジンに移行する方法は？



古いスキームのメンバーチャットは、主に最適化のために使用されていました。 必要なデータをチャットメンバーにすばやく転送した後、彼は移行プロセスに参加しなくなりました。



チャットメンバーのキュー。 100個のインスタンスが含まれていますが、チャットエンジンは4000個です。 データを転送するには、それらをコンプライアンスに準拠させる必要があります。このため、チャットメンバーは同じ4千のコピーに分割され、その後チャットエンジンでチャットメンバーのバイナリログの読み取りをオンにしました。



現在、チャットエンジンはチャットメンバーからのマルチチャットを認識していますが、これまでのところ、2人の対話者との対話については何も知りません。 このようなダイアログは、ユーザーにバインドされたテキストエンジンにあります。 ここでは、「額」のデータを取得しました。各チャットエンジンインスタンスは、テキストエンジンのすべてのインスタンスに、必要なダイアログがあるかどうかを尋ねました。



すばらしい-チャットエンジンは、マルチチャットとは何か、ダイアログとは何かを知っています。

マルチチャットでメッセージを結合する必要があります-各チャットの最後にメッセージのリストを取得します。 最初に、チャットエンジンはテキストエンジンからこのチャットからのすべてのユーザーメッセージを取得します。 場合によっては非常に多く（数億まで）ありますが、例外はほとんどなく、チャットは完全にRAMに配置されます。 順序付けられていないメッセージがあり、それぞれいくつかのコピーがあります。これらはすべて、ユーザーに対応する異なるテキストエンジンインスタンスから取り出されるためです。 タスクは、メッセージをソートし、余分なスペースを占有するコピーを取り除くことです。



各メッセージには、送信された時刻とテキストを含むタイムスタンプがあります。 ソートには時間を使用します-マルチチャットの参加者の最も古いメッセージにポインターを置き、疑わしいコピーのテキストからハッシュを比較し、タイムスタンプを増やす方向に進みます。 コピーのハッシュとタイムスタンプが同じであることは論理的ですが、実際には常にそうとは限りません。 ご存知のように、古いスキームの同期はPHPによって実行されました-まれに、同じメッセージを送信する時間はユーザーごとに異なりました。 これらの場合、タイムスタンプの編集を許可しました-通常は1秒以内です。 2番目の問題は、受信者ごとにメッセージの順序が異なることです。 そのような場合、追加のコピーを作成し、ユーザーごとに異なる順序のバリエーションを作成できます。



その後、マルチチャット内のメッセージに関するデータがユーザーエンジンに送信されます。 そして、ここにインポートされたメッセージの不快な機能があります。 通常の操作モードでは、エンジンに届くメッセージはuser_local_idによって厳密に昇順で並べられます。 古いエンジンからユーザーエンジンにインポートされたメッセージは、この便利なプロパティを失いました。 同時に、テストの利便性のために、迅速にそれらに連絡し、それらの中の何かを探し、新しいものを追加できる必要があります。



特別なデータ構造を使用して、インポートされたメッセージを保存します。



サイズのベクトルです $$$n = 2 ^ {a_0} + 2 ^ {a_1} + ... + 2 ^ {a_k} n = 2 ^ {a_0} + 2 ^ {a_1} + ... + 2 ^ {a_k}$ どこでも $$$a_i$ -さまざまで、要素の特別な順序で、降順で並べられます。 インデックス付きの各セグメント $$$[0,2 ^ {a_0}）、[2 ^ {a_0}、2 ^ {a_0} + 2 ^ {a_1}）、[2 ^ {a_0} + 2 ^ {a_1}、2 ^ {a_0} + 2 ^ {a_1} + 2 ^ {a_2}）、...$ アイテムがソートされます。 このような構造の要素の検索には時間がかかります $$$O（log ^ 2n）$ を通して $$$ログ\：{n}$ バイナリ検索。 アイテムの追加は、 $$$O（log ^ 2n）$ 。



そこで、古いエンジンから新しいエンジンにデータを転送する方法を見つけました。 しかし、このプロセスには数日かかります-そして最近では、ユーザーがお互いに書く習慣を放棄することはほとんどありません。 この間にメッセージが失われないようにするために、古いクラスターと新しいクラスターの両方を含む作業スキームに切り替えます。



データはチャットメンバーとユーザーエンジンに書き込まれます（古いスキームによる通常の操作中のように、テキストエンジンには書き込まれません）。 user-engineはchat-engineへのリクエストをプロキシします-ここでの動作は、このチャットが既に開いているかどうかによって異なります。 チャットがまだ閉じられていない場合、チャットエンジンはそれ自体へのメッセージを記録せず、テキストエンジンでのみ処理されます。 チャットがすでにチャットエンジンでホストされている場合、チャットはユーザーエンジンにchat_local_idを返し、すべての受信者にメッセージを送信します。 user-engineはtext-engineのすべてのデータをプロキシします。そのため、その場合はいつでもロールバックでき、関連するすべてのデータが古いエンジンにあります。 text-engineはuser_local_idを返します。これは、ユーザーエンジンが保持し、バックエンドに返します。



その結果、移行プロセスは次のようになります。空のユーザーエンジンとチャットエンジンのクラスターを接続します。 chat-engineはchat-members binlog全体を読み取り、上記のスキームに従ってプロキシが開始されます。 古いデータを注ぐと、2つの同期されたクラスター（古いものと新しいもの）が得られます。 読み取りをテキストエンジンからユーザーエンジンに切り替え、プロキシを無効にするだけです。

結果

新しいアプローチのおかげで、エンジンパフォーマンスのすべてのメトリックが改善され、データの一貫性に関する問題が解決されました。 これで、メッセージに新しい機能をすばやく導入できます（すでにこれを開始しています-チャット参加者の最大数を増やし、転送メッセージを検索し、固定メッセージを起動し、ユーザーごとのメッセージの合計数の制限を引き上げました）。



ロジックの変更は本当に壮大です。 そして、これは常に、巨大なチームと無数のコード行による1年間の開発を意味するものではないことに注意してください。 chat-engineおよびuser-engineと、メッセージを圧縮するためのHuffman、Splay-tree、およびインポートされたメッセージの構造などのすべての追加ストーリーは、2万行未満のコードです。 そして、3人の開発者がたった10か月でそれらを作成しました（ただし、 3人の 開発者 全員 がスポーツプログラミングの世界チャンピオンであることに留意する必要があります ）。



さらに、サーバーの数を2倍にする代わりに、サーバーの数を半分に減らすようになりました。ユーザーエンジンとチャットエンジンは500台の物理マシンで動作しますが、新しいスキームには大きな負荷マージンがあります。 機器のコストを大幅に節約しました。これは、運用費用のために年間約500万ドル+ 75万ドルです。



最も複雑で大規模なタスクに最適なソリューションを見つけるよう努めています。 私たちにはそれらがたくさんあるので、データベース部門で有能な開発者を探しています。 このような問題を解決する方法を愛し、知っている場合、アルゴリズムとデータ構造を完全に知っている場合、チームに参加することをお勧めします。 詳細については、 HRにお問い合わせください。



この話はあなたに関するものではありませんが、推奨事項に感謝していることに注意してください。 友人に開発者の空き状況を伝え、彼が試用期間を無事に通過した場合、10万ルーブルのボーナスを受け取ります。