JavaでLRUキャッシュを実装する方法

投稿日: 2022-10-26 2022-10-26
タグ: Algorithms

1. 概要

このチュートリアルでは、LRU cache について学習し、Javaの実装を見ていきます。

2. LRUキャッシュ

最も最近使用されていない（LRU）キャッシュは、使用順に要素を編成するキャッシュ排除アルゴリズムです。 LRUでは、名前が示すように、最も長く使用されていない要素がキャッシュから削除されます。

たとえば、3つのアイテムの容量を持つキャッシュがある場合：

最初はキャッシュが空で、要素8をキャッシュに入れます。要素9と6は以前と同じようにキャッシュされます。しかし、現在、キャッシュ容量がいっぱいであり、次の要素を配置するには、キャッシュ内で最も最近使用されていない要素を削除する必要があります。

JavaでLRUキャッシュを実装する前に、キャッシュのいくつかの側面を知っておくとよいでしょう。

すべての操作は、O（1）の順序で実行する必要があります
キャッシュのサイズには制限があります
すべてのキャッシュ操作が同時実行をサポートすることが必須です
キャッシュがいっぱいの場合、新しいアイテムを追加するとLRU戦略を呼び出す必要があります

2.1. LRUキャッシュの構造

それでは、キャッシュの設計に役立つ質問について考えてみましょう。

一定時間で要素の読み取り、並べ替え（一時的な並べ替え）、削除などの操作を実行できるデータ構造をどのように設計できますか？

この質問に対する答えを見つけるには、LRUキャッシュとその機能について何が言われているかを深く考える必要があるようです。

実際には、LRUキャッシュは一種のキューです— 要素が再アクセスされると、削除順序の最後に移動します
キャッシュのサイズには制限があるため、このキューには特定の容量があります。新しい要素が取り込まれるたびに、キューの先頭に追加されます。立ち退きが発生すると、キューの末尾から発生します。
キャッシュ内のデータのヒットは一定時間内に実行する必要がありますが、これはQueueでは不可能です。ただし、JavaのHashMapデータ構造では可能です。
最も最近使用されていない要素の削除は一定時間内に行う必要があります。つまり、 Queue の実装では、SingleLinkedListまたは配列

したがって、LRUキャッシュは、以下に示すように、DoublyLinkedListとHashMapの組み合わせに他なりません。

アイデアは、キュー内のデータにすばやくアクセスできるようにマップにキーを保持することです。

2.2. LRUアルゴリズム

LRUアルゴリズムは非常に簡単です。キーがHashMapに存在する場合、それはキャッシュヒットです。そうでなければ、それはキャッシュミスです。

キャッシュミスが発生した後、次の2つの手順を実行します。

リストの前に新しい要素を追加します。
HashMap に新しいエントリを追加し、リストの先頭を参照します。

そして、キャッシュヒット後に2つのステップを実行します。

ヒット要素を削除し、リストの前に追加します。
リストの先頭への新しい参照でHashMapを更新します。

それでは、JavaでLRUキャッシュを実装する方法を見てみましょう。

3. Javaでの実装

まず、Cacheインターフェースを定義します。

public interface Cache<K, V> {
    boolean set(K key, V value);
    Optional<V> get(K key);
    int size();
    boolean isEmpty();
    void clear();
}

次に、キャッシュを表すLRUCacheクラスを定義します。

public class LRUCache<K, V> implements Cache<K, V> {
    private int size;
    private Map<K, LinkedListNode<CacheElement<K,V>>> linkedListNodeMap;
    private DoublyLinkedList<CacheElement<K,V>> doublyLinkedList;

    public LRUCache(int size) {
        this.size = size;
        this.linkedListNodeMap = new HashMap<>(maxSize);
        this.doublyLinkedList = new DoublyLinkedList<>();
    }
   // rest of the implementation
}

LRUCacheのインスタンスを特定のサイズで作成できます。この実装では、 HashMap コレクションを使用して、LinkedInListNodeへのすべての参照を格納します。

それでは、LRUCacheの操作について説明しましょう。

3.1. プットオペレーション

1つ目は、putメソッドです。

public boolean put(K key, V value) {
    CacheElement<K, V> item = new CacheElement<K, V>(key, value);
    LinkedListNode<CacheElement<K, V>> newNode;
    if (this.linkedListNodeMap.containsKey(key)) {
        LinkedListNode<CacheElement<K, V>> node = this.linkedListNodeMap.get(key);
        newNode = doublyLinkedList.updateAndMoveToFront(node, item);
    } else {
        if (this.size() >= this.size) {
            this.evictElement();
        }
        newNode = this.doublyLinkedList.add(item);
    }
    if(newNode.isEmpty()) {
        return false;
    }
    this.linkedListNodeMap.put(key, newNode);
    return true;
 }

まず、すべてのキー/参照を格納するlinkedListNodeMapでキーを見つけます。キーが存在する場合、キャッシュヒットが発生し、DoublyLinkedListからCacheElementを取得して、前面に移動する準備ができています。

その後、linkedListNodeMap を新しい参照で更新し、リストの先頭に移動します。

public LinkedListNode<T> updateAndMoveToFront(LinkedListNode<T> node, T newValue) {
    if (node.isEmpty() || (this != (node.getListReference()))) {
        return dummyNode;
    }
    detach(node);
    add(newValue);
    return head;
}

まず、ノードが空でないことを確認します。また、ノードの参照はリストと同じである必要があります。その後、ノードをリストからデタッチし、newValueをリストに追加します。

ただし、キーが存在しない場合は、キャッシュミスが発生したため、linkedListNodeMapに新しいキーを配置する必要があります。その前に、リストのサイズを確認します。リストがいっぱいの場合は、リストから最も最近使用されていない要素をevictする必要があります。

3.2. 操作を取得

get操作を見てみましょう。

public Optional<V> get(K key) {
   LinkedListNode<CacheElement<K, V>> linkedListNode = this.linkedListNodeMap.get(key);
   if(linkedListNode != null && !linkedListNode.isEmpty()) {
       linkedListNodeMap.put(key, this.doublyLinkedList.moveToFront(linkedListNode));
       return Optional.of(linkedListNode.getElement().getValue());
   }
   return Optional.empty();
 }

上記のように、この操作は簡単です。まず、linkedListNodeMap からノードを取得し、その後、ノードがnullまたは空でないことを確認します。

残りの操作は以前と同じですが、moveToFrontメソッドに1つだけ違いがあります。

public LinkedListNode<T> moveToFront(LinkedListNode<T> node) {
    return node.isEmpty() ? dummyNode : updateAndMoveToFront(node, node.getElement());
}

次に、キャッシュが正常に機能することを確認するためのテストをいくつか作成しましょう。

@Test
public void addSomeDataToCache_WhenGetData_ThenIsEqualWithCacheElement(){
    LRUCache<String,String> lruCache = new LRUCache<>(3);
    lruCache.put("1","test1");
    lruCache.put("2","test2");
    lruCache.put("3","test3");
    assertEquals("test1",lruCache.get("1").get());
    assertEquals("test2",lruCache.get("2").get());
    assertEquals("test3",lruCache.get("3").get());
}

それでは、立ち退きポリシーをテストしましょう。

@Test
public void addDataToCacheToTheNumberOfSize_WhenAddOneMoreData_ThenLeastRecentlyDataWillEvict(){
    LRUCache<String,String> lruCache = new LRUCache<>(3);
    lruCache.put("1","test1");
    lruCache.put("2","test2");
    lruCache.put("3","test3");
    lruCache.put("4","test4");
    assertFalse(lruCache.get("1").isPresent());
 }

4. 並行性への対処

これまでのところ、キャッシュはシングルスレッド環境で使用されていると想定していました。

このコンテナをスレッドセーフにするには、すべてのパブリックメソッドを同期する必要があります。 ReentrantReadWriteLockとConcurrentHashMapを前の実装に追加しましょう。

public class LRUCache<K, V> implements Cache<K, V> {
    private int size;
    private final Map<K, LinkedListNode<CacheElement<K,V>>> linkedListNodeMap;
    private final DoublyLinkedList<CacheElement<K,V>> doublyLinkedList;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

    public LRUCache(int size) {
        this.size = size;
        this.linkedListNodeMap = new ConcurrentHashMap<>(size);
        this.doublyLinkedList = new DoublyLinkedList<>();
    }
// ...
}

メソッドをsynchronizedとして宣言するのではなく、再入可能な読み取り/書き込みロックを使用することをお勧めします。これにより、読み取りと書き込みでロックを使用するタイミングをより柔軟に決定できるようになります。

4.1. writeLock

次に、putメソッドでwriteLockの呼び出しを追加しましょう。

public boolean put(K key, V value) {
  this.lock.writeLock().lock();
   try {
       //..
   } finally {
       this.lock.writeLock().unlock();
   }
}

リソースでwriteLockを使用すると、ロックを保持しているスレッドのみがリソースへの書き込みまたはリソースからの読み取りを行うことができます。したがって、リソースに対して読み取りまたは書き込みを行おうとしている他のすべてのスレッドは、現在のロック所有者がリソースを解放するまで待機する必要があります。

これは、デッドロックを防ぐために非常に重要です。 try ブロック内の操作のいずれかが失敗した場合でも、メソッドの最後に finally ブロックを指定して関数を終了する前に、ロックを解放します。

writeLock を必要とする他の操作の1つは、putメソッドで使用したevictElementです。

private boolean evictElement() {
    this.lock.writeLock().lock();
    try {
        //...
    } finally {
        this.lock.writeLock().unlock();
    }
}

4.2. readLock

次に、readLock呼び出しをgetメソッドに追加します。

public Optional<V> get(K key) {
    this.lock.readLock().lock();
    try {
        //...
    } finally {
        this.lock.readLock().unlock();
    }
}

putメソッドで行ったこととまったく同じようです。唯一の違いは、writeLockの代わりにreadLockを使用することです。したがって、読み取りロックと書き込みロックのこの区別により、キャッシュが更新されていないときに、キャッシュを並行して読み取ることができます。

それでは、並行環境でキャッシュをテストしてみましょう。

@Test
public void runMultiThreadTask_WhenPutDataInConcurrentToCache_ThenNoDataLost() throws Exception {
    final int size = 50;
    final ExecutorService executorService = Executors.newFixedThreadPool(5);
    Cache<Integer, String> cache = new LRUCache<>(size);
    CountDownLatch countDownLatch = new CountDownLatch(size);
    try {
        IntStream.range(0, size).<Runnable>mapToObj(key -> () -> {
            cache.put(key, "value" + key);
            countDownLatch.countDown();
       }).forEach(executorService::submit);
       countDownLatch.await();
    } finally {
        executorService.shutdown();
    }
    assertEquals(cache.size(), size);
    IntStream.range(0, size).forEach(i -> assertEquals("value" + i,cache.get(i).get()));
}

5. 結論

このチュートリアルでは、最も一般的な機能のいくつかを含め、LRUキャッシュとは正確に何であるかを学びました。次に、JavaでLRUキャッシュを実装する1つの方法を確認し、最も一般的な操作のいくつかを検討しました。

最後に、ロックメカニズムを使用して実行中の並行性について説明しました。

いつものように、この記事で使用されているすべての例は、GitHubでから入手できます。

getdocs

13036