Xiaolin が LRU アルゴリズムを破壊!

[[411501]]

この記事はWeChatの公開アカウント「Xiao Lin Coding」から転載したもので、著者はXiao Lin Codingです。この記事を転載する場合は、Xiaolin Codingの公式アカウントまでご連絡ください。

みなさんこんにちは、シャオリンです。

数日前、私はコンピューターの基礎の素晴らしさについて記事を書きました。私はこれを 1 年間続けています。

ハートビートサービスのダウンタイム判定アルゴリズムを紹介します。当時は理論的な分析のみを行い、手動でコードを分解することなく、LRU アルゴリズムを使用して実装しました。

今日は、LRU アルゴリズムを分解する方法を紹介します。まずケースを確認し、次にコードについて説明します。

ダウンタイム判定アルゴリズムの設計

ハートビートサービスは主に次の 2 つのことを行います。

倒れたホストを見つけます。
オンラインホストを見つけてください。

このハートビートサービスの最も重要な部分は、ダウンタイムを決定するアルゴリズムです。

タイムアウトしたホストを見つけるために、すべてのホストを総当たりで調べる場合、ホストが数百台しかないときは問題ありません。しかし、ホストの数が増えると、アルゴリズムの複雑さが増し、プログラムのパフォーマンスが急激に低下します。

そのため、超大規模クラスターサイズに対応できるダウンタイム判定アルゴリズムを設計する必要があります。

まず、ハートビートパケットを管理するためにどのようなデータ構造を使用すべきかを考えてみましょう。

ハートビートパケットの内容には、ホストによって報告された時間情報が含まれており、時間関係があることを意味します。したがって、「双方向リンクリスト」を使用して先入れ先出しキューを形成し、ハートビートパケットのタイミング関係を保持できます。

使用されるデータ構造は二重リンクリストであるため、キューの末尾に挿入し、キューの先頭で削除する時間の計算量は O(1) です。

新しいハートビートパケットがある場合は、双方向リンクリストの末尾に挿入され、最も古いハートビートパケットが双方向リンクリストの先頭に配置されます。このように、ダウンしたホストを探すときは、双方向リンクリストの先頭にある最も古いハートビートパケットを調べて、現在から 5 秒以上経過しているかどうかを確認します。5 秒以上経過している場合は、ホストがダウンしていると見なされ、双方向リンクリストから削除されます。

注意深い学生なら、ホストのハートビートパケットがすでにキューにある場合、次回ホストのハートビートパケットをどのように処理すればよいかという問題を発見したはずです。

キュー内のハートビートパケットをホストによって報告された最新のものとして維持するには、まずホストの古いハートビートパケットを見つけて削除し、次に新しいハートビートパケットを双方向リンクリストの末尾に挿入する必要があります。

問題は、キュー内のホストの古いハートビートパケットが見つかった場合、データ構造が二重リンクリストであるため、このクエリプロセスの時間計算量は O(N) であり、キュー内の要素数が増えると、プログラムのパフォーマンスがさらに影響を受けるということです。これを最適化する必要があります。

クエリ効率が最も高いデータ構造は「ハッシュテーブル」であり、時間の計算量は O(1) のみであるため、このデータ構造を追加して最適化することができます。

ハッシュテーブルのキーはホストの IP アドレスであり、値には二重リンクリスト内のホストのノードが含まれているため、ハッシュテーブルを通じて二重リンクリスト内のホストの位置を簡単に見つけることができます。

このように、ハートビートパケットが受信されるたびに、まずそれがハッシュテーブル内にあるかどうかが判断されます。

ハッシュテーブルに存在しない場合は、新しいホストがオンラインになっていることを意味します。まず、双方向リンクリストの末尾に挿入し、次にホストの IP をキーとして、双方向リンクリスト内のホストのノードを値として使用して、ハッシュテーブルに挿入します。
ハッシュテーブルに存在する場合、ホストがオンラインになったことを意味します。まず、ハッシュテーブルを照会して、双方向リンクリスト内のホストの古いハートビートパケットのノードを見つけ、そのノードを介して双方向リンクリストから削除します。最後に、新しいハートビートパケットを双方向リンクリストの末尾に挿入し、同時にハッシュテーブルを更新します。

ご覧のとおり、上記の操作はすべて O(1) です。クラスターがどれだけ大きくなっても、時間の計算量は増加しませんが、より多くのメモリが占有されるという代償があります。これは、スペースと時間をトレードする方法です。

詳細な質問があります。気づいているかどうかわかりませんが、キューのデータ構造ではなぜ一方向リンクリストではなく双方向リンクリストが使用されるのでしょうか。

双方向リンクリストには、単方向リンクリストと比較して追加のプレポインタがあるため、それを使用して前のノードを見つけることができます。したがって、中間のノードを削除する場合は、直接削除できます。単方向リンクリストの場合、中間のノードを削除するときは、削除操作を完了する前に、削除するノードの前のノードを見つけるためにトラバースする必要があります。途中で追加のトラバーサル操作があります。

ハッシュテーブルが導入されたので、ホストがクラッシュしたと判断した場合 (二重リンクリストの先頭にあるホストがタイムアウトしたかどうかを確認)、二重リンクリストから削除するだけでなく、ハッシュテーブルからも削除する必要があります。

ハッシュテーブルからホストを削除するには、まずホストの IP アドレスを知る必要があります。これがハッシュテーブルのキーです。

双方向リンクリストに保存されるコンテンツには、ホストの IP 情報が含まれている必要があります。ホストの IP をより迅速に照会するために、双方向リンクリストに保存されるコンテンツは、キーがホストの IP で、値がホストの情報であるキーと値のペア (キーと値) にすることができます。

このように、双方向リンクリストの先頭ノードがタイムアウトしたことが判明した場合、ノードの内容はキーと値のペアであるため、ノードからホストの IP アドレスをすばやく取得できます。ホストの IP アドレス情報がわかれば、ハッシュテーブル内のホスト情報を削除できます。

これまでに、ハッシュテーブル + 双方向リンクリストというデータ構造を主に使用した高性能のダウンタイム判定アルゴリズムが設計されています。この組み合わせにより、クエリ + 削除 + 挿入操作の時間計算量は O(1) になります。スペースを時間と交換するというアイデアは、データ構造とアルゴリズムの美しさです。

アルゴリズムに精通している学生であれば、上記のアルゴリズムが LRU のようなアルゴリズムであり、最近使用された要素を削除するために使用されるものであることがわかるはずです。このアルゴリズムは幅広い用途があり、オペレーティングシステム、Redis、および MySQL で使用されています。

手動LRUアルゴリズム

多くの大企業での面接では、LRU アルゴリズムが問われることが多く、手書きで記述するよう求められる場合もあります。私の友人は、テンセントでの面接で、LRU アルゴリズムを手書きで記述するよう求められました。

今日は、C++ を使用して LRU アルゴリズムを実装する方法を紹介します。アルゴリズムを実装するには、上で説明した 2 つのデータ構造、「ハッシュテーブル + 双方向リンクリスト」を使用します。

LRU アルゴリズムを実装するには、リンクリストの先頭に最近アクセスされたデータまたは新しく追加されたデータを保持し、リンクリストの末尾に最も長い未アクセスデータを保持する必要があります。このようにすると、最も長い未アクセスデータを簡単に削除でき、その後ハッシュテーブルを使用してノードをすばやく見つけることができます。

双方向リンクリストにはキーと値のペアが格納されます。

 typedef std::pair< int  キー、std::string 値> ペア;
 typedef std::list<Pair> リスト;

ハッシュテーブルにはリンクリストノードが格納されます。

 typedef std::map< int  キー、型名List::iterator> Map;

データ構造がわかったら、データを追加するための put とユーザーがデータを取得するための get という 2 つの関数を実装できます。

ここでは、次のように LRUCache テンプレートクラスを定義しました。

次に、データを保存するための put メソッドの実装を見てみましょう。

putメソッドの実装アイデアについてお話ししましょう。

まず、ハッシュテーブルにキーが存在するかどうかを確認します。

存在する場合は、古いデータがあることを意味します。そのため、まずリンクリストとハッシュテーブルから古いデータを削除し、新しいデータをリンクリストの先頭に追加する必要があります。同時に、リンクリストノードはハッシュテーブルに保存されるため、リンクリスト内のキーデータは最もホットなものとして維持されます。
キーがハッシュテーブルに存在しない場合は、新しいデータとみなされ、リンクリストの先頭に直接追加され、ハッシュテーブル内のリンクリストノードが更新されます。

次に、リンクリストの要素サイズが LRU 容量を超えているかどうかを確認します。超えている場合は、リンクリストの末尾の要素を削除し、ハッシュテーブルからノードを削除します。

次に、get メソッドの実装を見てみましょう。

まず、ハッシュテーブルにキーが存在するかどうかを確認します。