高スループット、スレッド安全のLRUキャッシュ詳細

本論文では主に高スループット、スレッドセキュリティのLRUキャッシュに関する内容を紹介します。
数年前、私はLRUキャッシュをキーワードとして、そのIDを検索するために実現しました。データ構造は非常に興味深い。要求されたスループットは、locksおよびsynchronizedキーワードの大量使用による性能問題を解消するのに十分大きいので、アプリケーションはjavaで実現される。
一連の原子参照割り当ては、ConccurrenthashMapにおいてLRU順序を保持し、開始時にはvalueをentryに包装し、entryは、双連鎖のLRUチェーンにおいてノードがあり、チェーンの末尾は最近使用されているentryであり、先頭ノードにはキャッシュが一定の大きさに達すると、クリアされるかもしれないentryが格納されている。各ノードは、検索のためのイベントを指します。

keyによって値を検索するとき、キャッシュはまずmapを検索して、このvalueが存在するかどうかを確認します。存在しない場合、キャリアに依存して、データソースからvalueをRead-throughで読み、「もし欠けたら追加する」という方法で追加されたmapに行きます。高スループットを確保するための挑戦は、LRUチェーンの維持に効果的である。このマージされたハッシュmapはセグメント化されており、スレッドのレベルは一定のレベル（mapを構築するときはマージレベルを指定することができます）である場合はあまり多くのスレッド競合を経験しません。しかし、LRUチェーンは同じ方法で分割されてはいけませんか？この問題を解決するために、補助的なキューを導入して作業をクリアします。
cacheには6つの基本的な方法があります。キャッシュヒットには、2つの基本的な操作が含まれています。getとofferは、粗さを換えるために、4つの基本的な方法get、ロード、put、offerを含みます。put方法では、空を追跡して操作する必要があるかもしれません。キャッシュに命中された場合にゲットします。私たちはLRUチェーン上で受動的に空を掃除することを浄化操作といいます。
get：lookup entry in the map by key
load：load value from a data source
put：create entry and map it to key
offer：apped a node at the tail of the LRU list that refers to a recently accessed entry
evict:remove nodes the head of the list and assited entries from the map(after the cache reaches a certain size)
purge:delete unused nodes in the LRU list--we refer to these nodes as holes，and the cleanup queue keeps track of these
クリア操作と浄化操作は大量のデータ処理です。一つ一つの操作の詳細を見てみます。
get操作は以下のように動作します。

get(K) -> V 
 
lookup entry by key k 
if cache hit, we have an entry e 
  offer entry e 
  try purge some holes 
else 
  load value v for key k 
  create entry e <- (k,v) 
  try put entry e 
end 
return value e.v 

keyが存在する場合、LRUチェーンの末尾に新しいノードを提供して、これが最近使用された値であることを示します。getとofferの実行は原子操作ではないので、このoffredノードは最近使用されているエンティティを指すとは言えませんが、同時に実行した時に得られた最近使用されているエンティティに違いないです。強制的にgetとofferをオンラインに実行する順序はありません。スループットを制限するかもしれません。offerのノードの後で、いくつかの消去とvalueに戻る操作を試みています。このオフとプッシュの操作を詳しく見てみます。
キャッシュがなくなったら、このkeyのためにブースターを呼び出して、新しいエンティティを作成して、mapに入れます。putは次のように操作します。

put(E) -> E 
 
existing entry ex <- map.putIfAbsent(e.k, e) 
if absent 
  offer entry e; 
  if size reaches evict-threshold 
    evict some entries 
  end 
  return entry e 
else, we have an existing entry ex 
  return entry ex 
end 

あなたが見ているように、二つ以上のスレッドがあります。一つのエンティティをmapに入れると競争がありますが、一つだけ成功してofferを呼び出すことができます。LRUチェーンの末尾にノードを提供した後、キャッシュが既にその欠如値の大きさに達しているかどうかを確認する必要があります。この特定のアプリケーションのシーンでは、欠けた値の設定は容量の大きさよりも小さい。クリア操作小ロットの発生は、各エンティティに加えられた時に発生するのではなく、マルチスレッドは、キャッシュの容量がその容量に達するまで、クリア操作に参加するかもしれません。鍵をかけるのは簡単ですが、スレッドは安全です。空をクリアするには、LRU鎖の先頭ノードを除去する必要があり、これは、mapにおけるマルチスレッドの除去動作を回避するために、注意深い原子動作に依存する必要がある。

このoffer動作は非常に興味深い。常にノードを作成することを試みているが、LRU中では、使用していないノードを直ちに除去し、削除することを試みていない。

offer(E) 
 
if tail node doesn't refer to entry e 
  assign current node c <- e.n 
  create a new node n(e), new node refers to entry e 
  if atomic compare-and-set node e.n, expect c, assign n 
    add node n to tail of LRU list 
    if node c not null 
      set entry c.e to null, c now has a hole 
      add node c to cleanup queue 
    end 
  end 
end 

まず、チェーンの中の尾部のノードはすでに訪問したエンティティを指していないことを確認します。これはすべてのスレッドが頻繁に同じキーのペアにアクセスしていない限り、チェーン部の尾部のエンティティに新しいノードを作成します。このエンティティが異なる場合、新しいノードを提供する前に、エンティティの比較と設定の操作を試みます。これはマルチスレッドが同じことをするのを阻止します。
成功した配信ノードのスレッドは、LRUチェーンの末尾に新しいノードを提供しています。この操作は、ConcerentlinkedQueのfindと同様に、依存アルゴリズムは以下の文章でSimple、Fast、and Practical Non-Blocking and Blocking Cont Que Algorithmsを記述しています。スレッドはその後、エンティティの前に他のノードと関連があるかどうかをチェックします。この場合、古いノードはすぐに削除されませんが、ホームとしてマークされます。

締め括りをつける
以上が、本明細書で高スループット、スレッドセキュリティのLRUキャッシュに関する詳細な内容のすべてです。興味のある方は引き続き当駅の他のテーマを参照してください。友達のサポートに感謝します。