VKontakte メッセージ データベースを最初から書き換えて生き残る

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

それはかなり多いです。 すべてのユーザーのすべてのメッセージを読み取ろうとすると、150 万年以上かかります。 ただし、あなたがかなり上級の読者であり、各メッセージに XNUMX 秒も費やさない場合に限ります。

このような大量のデータでは、データを保存およびアクセスするためのロジックを最適に構築することが重要です。 そうしないと、それほど素晴らしいとは言えない瞬間に、すぐにすべてがうまくいかなくなることが明らかになる可能性があります。

私たちにとって、この瞬間はXNUMX年半前にやって来ました。 私たちがどのようにしてこれに至ったのか、そして最終的に何が起こったのかを順番に説明します。

病歴

非常に最初の実装では、VKontakte メッセージは PHP バックエンドと MySQL の組み合わせで動作しました。 これは、小規模な学生の Web サイトではまったく通常のソリューションです。 しかし、このサイトは制御不能に成長し、サイト自体のデータ構造の最適化が必要になり始めました。

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

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

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

2011 年 XNUMX 月、VKontakte は複数の参加者との会話、つまりマルチ チャットを導入しました。 彼らと協力するために、私たちはメンバーチャットとチャットメンバーという XNUMX つの新しいクラスターを立ち上げました。 XNUMX つ目はユーザーによるチャットに関するデータを保存し、XNUMX つ目はチャットによるユーザーに関するデータを保存します。 これには、リスト自体に加えて、たとえば、招待しているユーザーとそのユーザーがチャットに追加された時間が含まれます。

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

この計画には欠点があります。 同期は依然として PHP の責任です。 大規模なチャットと、同時にメッセージを送信するユーザーは危険な話です。 テキスト エンジンのインスタンスは uid に依存するため、チャット参加者は異なる時間に同じメッセージを受信する可能性があります。 進歩が停滞しているとしても、これに耐えることはできます。 しかし、そんなことは起こらないでしょう。

2015 年末にコミュニティ メッセージを開始し、2016 年の初めにコミュニティ メッセージ用の API を開始しました。 コミュニティに大規模なチャットボットが登場したことで、均等な負荷分散を忘れてしまう可能性がありました。

優れたボットは XNUMX 日に数百万のメッセージを生成しますが、これは最もおしゃべりなユーザーでも自慢できません。 これは、そのようなボットが存在するテキスト エンジンの一部のインスタンスが最大限の被害を受け始めたことを意味します。

2016 年のメッセージ エンジンは、チャット メンバーとメンバー チャットのインスタンスが 100 個、テキスト エンジンが 8000 個です。 これらは 64 GB のメモリを搭載した 32 台のサーバーでホストされていました。 最初の緊急措置として、メモリをさらに XNUMX GB 増設しました。 予測を試算しました。 大幅な変更がなければ、これでもう XNUMX 年くらいは十分でしょう。 ハードウェアを入手するか、データベース自体を最適化する必要があります。

アーキテクチャの性質上、ハードウェアを複数台に増やすことだけが合理的です。 つまり、車の台数を少なくとも XNUMX 倍にするということです。明らかに、これはかなり費用のかかる方法です。 最適化していきます。

新しい概念

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

少なくとも XNUMX つの新しいデータベースが必要です。

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

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

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

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

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

1. PHP バックエンドは、メッセージ送信リクエストでユーザー エンジンに接続します。
2. user-engine は、要求を目的のチャット エンジン インスタンスにプロキシし、このインスタンスは user-engine chat_local_id (このチャット内の新しいメッセージの一意の識別子) に戻ります。 次に、チャット エンジンはチャット内のすべての受信者にメッセージをブロードキャストします。
3. user-engine は、チャット エンジンから chat_local_id を受け取り、このユーザーの一意のメッセージ識別子である user_local_id を PHP に返します。 この識別子は、たとえば API 経由でメッセージを操作するために使用されます。

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

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

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

メッセージには大量の情報 (ほとんどがテキスト) が含まれるため、圧縮できると便利です。 たとえ XNUMX つの個別のメッセージであっても正確にアーカイブを解除できることが重要です。 メッセージを圧縮するために使用されます ハフマンアルゴリズム 私たち独自のヒューリスティックを使用して、たとえば、メッセージでは単語がスペースや句読点などの「単語以外の文字」と交互に使用されることを知っています。また、ロシア語の記号の使用の特殊性のいくつかも覚えています。

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

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

すべての詳細が考慮されました。残っているのは、新しいスキームに切り替えることだけです。できればユーザーに気付かれずに。

データ移行

したがって、ユーザーごとにメッセージを保存するテキスト エンジンと、マルチ チャット ルームとその中のユーザーに関するデータを保存する XNUMX つのクラスター チャット メンバーとメンバー チャットがあります。 ここから新しいユーザー エンジンとチャット エンジンに移行するにはどうすればよいでしょうか?

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

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

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

素晴らしい - チャット エンジンは、どのようなマルチチャット チャットがあるのか​​、どのような対話があるのか​​を認識しています。
最終的に各チャットのメッセージのリストが得られるように、マルチチャット チャット内のメッセージを結合する必要があります。 まず、チャット エンジンは、このチャットからすべてのユーザー メッセージをテキスト エンジンから取得します。 場合によっては、非常に多くのメッセージ (最大数億) が存在しますが、非常にまれな例外を除いて、チャットは完全に RAM に収まります。 順序付けされていないメッセージがあり、それぞれが複数のコピーに分かれています。結局のところ、それらはすべて、ユーザーに対応するさまざまなテキスト エンジン インスタンスから取得されたものです。 目標は、メッセージを分類し、不必要なスペースを占めるコピーを削除することです。

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

この後、マルチチャットのメッセージに関するデータがユーザー エンジンに送信されます。 そして、インポートされたメッセージには不快な特徴があります。 通常の動作では、エンジンに送信されるメッセージは、厳密に user_local_id の昇順で並べられます。 古いエンジンからユーザー エンジンにインポートされたメッセージは、この便利な特性を失いました。 同時に、テストの便宜のために、それらに素早くアクセスし、その中で何かを探し、新しいものを追加できる必要があります。

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

サイズのベクトルを表します みんなはどこですか - は異なり、要素の特別な順序で降順に並べられます。 各セグメントにインデックスが付いている 要素がソートされます。 このような構造内の要素の検索には時間がかかります スルー 二分探索。 要素の追加は次の期間で償却されます。 .

そこで、古いエンジンから新しいエンジンにデータを転送する方法を考え出しました。 しかし、このプロセスには数日かかります。そして、その間にユーザーがお互いに手紙を書く習慣をやめる可能性は低いです。 この間にメッセージが失われないように、新旧両方のクラスターを使用する作業スキームに切り替えます。

データはチャット メンバーとユーザー エンジンに書き込まれます (古いスキームによる通常の操作とは異なり、テキスト エンジンには書き込まれません)。 user-engine はリクエストを chat-engine にプロキシします。ここでの動作は、このチャットがすでにマージされているかどうかによって異なります。 チャットがまだマージされていない場合、チャット エンジンはメッセージをそれ自体に書き込まず、その処理はテキスト エンジン内でのみ行われます。 チャットがすでにチャット エンジンにマージされている場合は、chat_local_id がユーザー エンジンに返され、メッセージがすべての受信者に送信されます。 user-engine はすべてのデータを text-engine にプロキシします。そのため、何かが起こった場合はいつでもロールバックして、現在のデータをすべて古いエンジンに保持できます。 text-engine は user_local_id を返し、user_engine はこれを保存してバックエンドに返します。

その結果、移行プロセスは次のようになります。空のユーザー エンジン クラスターとチャット エンジン クラスターを接続します。 チャット エンジンはチャット メンバーのバイナリログ全体を読み取り、上記のスキームに従ってプロキシを開始します。 古いデータを転送し、XNUMX つの同期されたクラスター (新旧) を取得します。 残っているのは、読み取りをテキスト エンジンからユーザー エンジンに切り替え、プロキシを無効にすることだけです。

結果

新しいアプローチのおかげで、エンジンのすべてのパフォーマンス指標が改善され、データの一貫性に関する問題が解決されました。 メッセージに新しい機能をすぐに実装できるようになりました (そしてすでに実装し始めています - チャット参加者の最大数を増やし、転送されたメッセージの検索を実装し、固定メッセージを開始し、ユーザーごとのメッセージの合計数の制限を引き上げました) 。

ロジックの変更は本当に膨大です。 そして、これは必ずしも、大規模なチームと無数のコード行による何年もの開発を意味するわけではないことに注意したいと思います。 チャット エンジンとユーザー エンジンに加えて、メッセージ圧縮のためのハフマン、スプレイ ツリー、インポートされたメッセージの構造などのすべての追加ストーリーを含めたコードは 20 万行未満です。 そして、これらは 3 人の開発者によってわずか 10 か月で書かれました (ただし、次のことに留意する必要があります) すべて 3 デベロッパー - 世界チャンピオン スポーツ番組で).

さらに、サーバーの数を 500 倍にする代わりに、その数を半分に減らしました。現在、ユーザー エンジンとチャット エンジンは 5 台の物理マシン上で稼動していますが、新しいスキームには負荷に対して大きな余裕があります。 設備にかかる費用を大幅に節約できました。年間約 750 万ドル + 運営費 XNUMX 万ドルを節約できました。

私たちは、最も複雑で大規模な問題に対して最適なソリューションを見つけるよう努めています。 私たちにはたくさんの人材がいます。だからこそ、データベース部門で有能な開発者を探しています。 このような問題が好きで解決方法を知っており、アルゴリズムとデータ構造に関する優れた知識をお持ちの方は、ぜひチームに参加してください。 お問い合わせください HR、 чтобы узнать подробности.

この話があなたに関するものではない場合でも、私たちは推奨事項を重視していることに注意してください。 友達に教えてください 開発者の欠員、そして彼が試用期間を無事に完了すると、100万ルーブルのボーナスを受け取ります。

出所： habr.com