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 メソッドの実装を見てみましょう。

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

• 存在しない場合は false を返します。
• 存在する場合、リンク リストはデータを削除し、リンク リストの先頭にデータを追加して、リンク リストの先頭を最近アクセスされたデータとして維持します。

2 つの主要な関数が導入されました。実装全体のコードは次のとおりです。

次に、テストケースを実行します。

容量 3 の LRUCache オブジェクトを作成し、put 関数を使用して 3 セットのキーと値を追加します。このとき、リンク リストの順序は、key:3 (先頭) -> key:2 -> key:1 (末尾) となります。

次に、get を介して key:1 の要素にアクセスすると、リンク リストの順序は key:1 (head) -> key:3 -> key:2 (tail) になります。

次に、putはkey:4要素を追加します。リンクリストのサイズがLRUCacheの定義容量を超えるため、キューの末尾の要素、つまりkey:2は削除されます。

最後に、key:2 要素にアクセスできないことがわかります。実行結果は次のとおりです。

さて、ここで LRU アルゴリズムが登場します。

私はシャオリンです。今日は昨日よりも知識が増えましたか？