コーディングベストプラクティス(4)--LinkedHashMapのget()メソッドに注意

詳細
これは実際のプロジェクトからの例であり,この例ではjdkにおけるLinkedHashMapに基づいてLRUCacheを設計した同僚がおり,性能向上のためにReentrantReadWriteLock読み書きロック:書き込みロック対応put()メソッドを用い,読み取りロック対応get()メソッドは,読み書きロックによる同時get()の実現を期待している.
コードは次のように実装されます.

private ReentrantReadWriteLock  lock = new ReentrantReadWriteLock ();
lruMap = new LinkedHashMap(initialCapacity, loadFactor, true) 

public V get(K key) {
        lock.readLock().lock();
        try {
                return lruMap.get(key);
        } finally {
                lock.readLock().unlock();
        }
}

public int entries() {
        lock.readLock().lock();
        try {
                return lruMap.size();
        } finally {
                lock.readLock().unlock();
        }
}


public void put(K key, V value) {
        ...
        lock.writeLock().lock();
        try {
        ...
                lruMap.put(key, value);
        ...
        } finally {
                lock.writeLock().unlock();
        }
}

テストで問題が見つかり、数時間走るとシステムがhung upし、httpリクエストを受信できません.スレッドスタックを印刷してチェックすると、httpのスレッドの多くがリードロックを待っていることがわかります.runnableのスレッドが書き込みロックをかけていたがLinkedHashMapに止まっていた.Transferメソッドにあります.スレッドスタック情報は次のとおりです.
"http-0.0.0.0-8081-178"daemon prio=3 tid=0x0000000004673000 nid=0x135 waiting on condition [0xfffffd7f5759c000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0xfffffd7f7cc86928> (a java.util.concurrent.locks.ReentrantReadWriteLock$NonfairSync)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:156)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:811)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.doAcquireShared(AbstractQueuedSynchronizer.java:941)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireShared(AbstractQueuedSynchronizer.java:1261)
        at java.util.concurrent.locks.ReentrantReadWriteLock$ReadLock.lock(ReentrantReadWriteLock.java:594)
        ......
"http-0.0.0.0-8081-210"daemon prio=3 tid=0x0000000001422800 nid=0x155 runnable [0xfffffd7f5557c000]
   java.lang.Thread.State: RUNNABLE
        at java.util.LinkedHashMap.transfer(LinkedHashMap.java:234)
        at java.util.HashMap.resize(HashMap.java:463)
        at java.util.LinkedHashMap.addEntry(LinkedHashMap.java:414)
        at java.util.HashMap.put(HashMap.java:385)
        ......
HashMapはスレッドが安全ではないことはよく知られているので,HashMapがマルチスレッド同時では反発ロックが必要であり,put()がロックをかけなければ内部チェーンテーブルを破壊しやすくget()デッドサイクルをもたらし,hungが住みつく.ここに宝を洗う例があり、この現象の詳細な分析があります.https://gist.github.com/1081908
しかしMSDPのこの例では,ReentrantReadWriteLock読み書きロックの存在により,put()とget()メソッドは反発し合い,上記読み書き競合の問題はない.
Googleは、LinkedHashMapのget()メソッドがデータチェーンテーブルを変更することに根ざしている問題であることを発見しました.LinkedHashMapの実装コードを見てみましょう.

public V get(Object key) {
        Entry e = (Entry)getEntry(key);
        if (e == null)
                return null;
        e.recordAccess(this);
        return e.value;
}

void recordAccess(HashMap m) {
        LinkedHashMap lm = (LinkedHashMap)m;
        if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
        }
}

void transfer(HashMap.Entry[] newTable) {
        int newCapacity = newTable.length;
        for (Entry e = header.after; e != header; e = e.after) {
                int index = indexFor(e.hash, newCapacity);
                e.next = newTable[index];
                newTable[index] = e;
        }
}    

前のLRUCacheのコードでは、LinkedHashMapをこのように初期化しています.

lruMap = new LinkedHashMap(initialCapacity, loadFactor, true) 

LinkedHashMapコンストラクション関数のパラメータtrueは、LinkedHashMapがアクセス順にソートされることを示します.ここでアクセス順にソートするということは、LinkedHashMapのget(key)またはput(key,value)を呼び出すと、keyがmapに含まれている場合、LinkedHashMapはkeyオブジェクトのentryを線形構造の最後に置くことを意味する.LinkedHashMapはアクセス順にソートする機能を提供するため、HashMapのget(key)メソッド(HashMapはソートを必要としない)とHashMapを書き換える必要がある.EntryのrecordAccess(HashMap)メソッド.addBefore(lm.header)はこのentryをheader線形テーブルの最後に置くことに注意してください.(参考LinkedHashMap.Entry extends HashMap.EntryはHashMap.Entryよりbefore,afterの2つのドメインが多く、双方向です)
上記のLRUCacheでは,パフォーマンスを提供するためにReentrantReadWriteLockを用いた読み書きロックにより同時get()を実現し,結果として同時問題を招いた.問題を解決する方法は簡単で、読み書きロックを外し、put()/get()に普通の反発ロックを使えばいいです.もちろん,get()メソッドでは同時読み取りが実現できず,性能に影響を及ぼす.
まとめて、LinkedHashMapを使用する場合は、LinkedHashMapのget()メソッドに注意してください.