Bagaimana Anda menerapkan cache LRU di Jawa?

Tolong jangan katakan EHCache atau OSCache, dll. Asumsikan untuk keperluan pertanyaan ini bahwa saya ingin menerapkan sendiri menggunakan hanya SDK (belajar sambil melakukan). Mengingat bahwa cache akan digunakan dalam lingkungan multithreaded, struktur data apa yang akan Anda gunakan? Saya sudah menerapkan satu menggunakan LinkedHashMap dan Koleksi # sinkronisasi , tapi saya ingin tahu apakah ada salah satu koleksi bersamaan akan menjadi kandidat yang lebih baik.

UPDATE: Saya baru saja membaca Yegge terbaru ketika saya menemukan nugget ini:

Jika Anda membutuhkan akses waktu konstan dan ingin mempertahankan urutan penyisipan, Anda tidak dapat melakukan lebih baik daripada LinkedHashMap, struktur data yang benar-benar luar biasa. Satu-satunya cara itu mungkin bisa lebih indah adalah jika ada versi bersamaan. Tapi sayang sekali.

Saya memikirkan hal yang persis sama sebelum saya pergi dengan implementasi LinkedHashMap+ yang Collections#synchronizedMapsaya sebutkan di atas. Senang mengetahui bahwa saya tidak hanya mengabaikan sesuatu.

Berdasarkan jawaban sejauh ini, sepertinya taruhan terbaik saya untuk LRU yang sangat konkuren adalah dengan memperpanjang ConcurrentHashMap menggunakan beberapa logika yang sama yang LinkedHashMapdigunakan.

Saya suka banyak saran ini, tetapi untuk sekarang saya pikir saya akan tetap dengan LinkedHashMap+ Collections.synchronizedMap. Jika saya mengunjungi kembali ini di masa depan, saya mungkin akan berusaha memperluas ConcurrentHashMapdengan cara yang sama LinkedHashMapmeluas HashMap.

MEMPERBARUI:

Berdasarkan permintaan, inilah inti dari implementasi saya saat ini.

private class LruCache<A, B> extends LinkedHashMap<A, B> {
    private final int maxEntries;

    public LruCache(final int maxEntries) {
        super(maxEntries + 1, 1.0f, true);
        this.maxEntries = maxEntries;
    }

    /**
     * Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
     * created.
     *
     * <p>
     * This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
     * <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
     * <code>LinkedHashMap</code>.
     * </p>
     *
     * @param eldest
     *            the <code>Entry</code> in question; this implementation doesn't care what it is, since the
     *            implementation is only dependent on the size of the cache
     * @return <tt>true</tt> if the oldest
     * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return super.size() > maxEntries;
    }
}

Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));

Jika saya melakukan ini lagi dari awal hari ini, saya akan menggunakan Guava CacheBuilder.

Ini babak dua.

Babak pertama adalah apa yang saya hasilkan kemudian saya membaca kembali komentar dengan domain yang sedikit lebih tertanam di kepala saya.

Jadi di sini adalah versi paling sederhana dengan tes unit yang menunjukkan itu berfungsi berdasarkan beberapa versi lainnya.

Pertama versi non-konkuren:

import java.util.LinkedHashMap;
import java.util.Map;

public class LruSimpleCache<K, V> implements LruCache <K, V>{

    Map<K, V> map = new LinkedHashMap (  );


    public LruSimpleCache (final int limit) {
           map = new LinkedHashMap <K, V> (16, 0.75f, true) {
               @Override
               protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
                   return super.size() > limit;
               }
           };
    }
    @Override
    public void put ( K key, V value ) {
        map.put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map.get(key);
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        V value =  map.get ( key );
        if (value!=null) {
            map.remove ( key );
            map.put(key, value);
        }
        return value;
    }

    @Override
    public void remove ( K key ) {
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }


}

Bendera yang sebenarnya akan melacak akses dari mendapat dan menempatkan. Lihat JavaDocs. RemoveEdelstEntry tanpa flag yang sebenarnya ke konstruktor hanya akan mengimplementasikan cache FIFO (lihat catatan di bawah tentang FIFO dan removeEldestEntry).

Berikut adalah tes yang membuktikannya berfungsi sebagai cache LRU:

public class LruSimpleTest {

    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleCache<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        if ( !ok ) die ();

    }

Sekarang untuk versi bersamaan ...

paket org.boon.cache;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LruSimpleConcurrentCache<K, V> implements LruCache<K, V> {

    final CacheMap<K, V>[] cacheRegions;


    private static class CacheMap<K, V> extends LinkedHashMap<K, V> {
        private final ReadWriteLock readWriteLock;
        private final int limit;

        CacheMap ( final int limit, boolean fair ) {
            super ( 16, 0.75f, true );
            this.limit = limit;
            readWriteLock = new ReentrantReadWriteLock ( fair );

        }

        protected boolean removeEldestEntry ( final Map.Entry<K, V> eldest ) {
            return super.size () > limit;
        }


        @Override
        public V put ( K key, V value ) {
            readWriteLock.writeLock ().lock ();

            V old;
            try {

                old = super.put ( key, value );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return old;

        }


        @Override
        public V get ( Object key ) {
            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.get ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;
        }

        @Override
        public V remove ( Object key ) {

            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.remove ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public V getSilent ( K key ) {
            readWriteLock.writeLock ().lock ();

            V value;

            try {

                value = this.get ( key );
                if ( value != null ) {
                    this.remove ( key );
                    this.put ( key, value );
                }
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public int size () {
            readWriteLock.readLock ().lock ();
            int size = -1;
            try {
                size = super.size ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return size;
        }

        public String toString () {
            readWriteLock.readLock ().lock ();
            String str;
            try {
                str = super.toString ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return str;
        }


    }

    public LruSimpleConcurrentCache ( final int limit, boolean fair ) {
        int cores = Runtime.getRuntime ().availableProcessors ();
        int stripeSize = cores < 2 ? 4 : cores * 2;
        cacheRegions = new CacheMap[ stripeSize ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) {

        cacheRegions = new CacheMap[ concurrency ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    private int stripeIndex ( K key ) {
        int hashCode = key.hashCode () * 31;
        return hashCode % ( cacheRegions.length );
    }

    private CacheMap<K, V> map ( K key ) {
        return cacheRegions[ stripeIndex ( key ) ];
    }

    @Override
    public void put ( K key, V value ) {

        map ( key ).put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map ( key ).get ( key );
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        return map ( key ).getSilent ( key );

    }

    @Override
    public void remove ( K key ) {
        map ( key ).remove ( key );
    }

    @Override
    public int size () {
        int size = 0;
        for ( CacheMap<K, V> cache : cacheRegions ) {
            size += cache.size ();
        }
        return size;
    }

    public String toString () {

        StringBuilder builder = new StringBuilder ();
        for ( CacheMap<K, V> cache : cacheRegions ) {
            builder.append ( cache.toString () ).append ( '\n' );
        }

        return builder.toString ();
    }


}

Anda dapat melihat mengapa saya membahas versi non-konkuren terlebih dahulu. Upaya di atas untuk membuat beberapa garis untuk mengurangi pertikaian kunci. Jadi kita hash kunci dan kemudian mencari hash untuk menemukan cache yang sebenarnya. Ini membuat ukuran batas lebih dari saran / tebakan kasar dalam jumlah kesalahan yang wajar tergantung pada seberapa baik penyebaran algoritma hash kunci Anda.

Berikut adalah tes untuk menunjukkan bahwa versi bersamaan mungkin berfungsi. :) (Tes di bawah api akan menjadi cara nyata).

public class SimpleConcurrentLRUCache {


    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 1, 4, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );

        puts (cache);
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();

        cache.put ( 8, 8 );
        cache.put ( 9, 9 );

        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        puts (cache);


        if ( !ok ) die ();

    }


    @Test
    public void test2 () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 400, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        for (int index =0 ; index < 5_000; index++) {
            cache.get(0);
            cache.get ( 1 );
            cache.put ( 2, index  );
            cache.put ( 3, index );
            cache.put(index, index);
        }

        boolean ok = cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 1 ) == 1 || die ();
        ok |= cache.getSilent ( 2 ) != null || die ();
        ok |= cache.getSilent ( 3 ) != null || die ();

        ok |= cache.size () < 600 || die();
        if ( !ok ) die ();



    }

}

Ini adalah posting terakhir .. Posting pertama yang saya hapus karena itu adalah LFU bukan cache LRU.

Saya pikir saya akan mencoba ini lagi. Saya mencoba untuk membuat versi paling sederhana dari cache LRU menggunakan standar JDK tanpa implementasi terlalu banyak.

Inilah yang saya pikirkan. Upaya pertama saya adalah sedikit bencana ketika saya menerapkan LFU dan bukannya LRU, dan kemudian saya menambahkan FIFO, dan dukungan LRU untuk itu ... dan kemudian saya menyadari itu menjadi monster. Kemudian saya mulai berbicara dengan teman saya John yang hampir tidak tertarik, dan kemudian saya jelaskan panjang lebar bagaimana saya menerapkan LFU, LRU dan FIFO dan bagaimana Anda bisa mengubahnya dengan arg ENUM sederhana, dan kemudian saya menyadari bahwa semua yang saya inginkan adalah LRU sederhana. Jadi abaikan pos sebelumnya dari saya, dan beri tahu saya jika Anda ingin melihat cache LRU / LFU / FIFO yang dapat dialihkan melalui enum ... tidak? Ok .. ini dia.

LRU yang paling sederhana dengan JDK. Saya menerapkan versi bersamaan dan versi tidak bersamaan.

Saya membuat antarmuka umum (ini minimalis sehingga kemungkinan kehilangan beberapa fitur yang Anda inginkan tetapi berfungsi untuk kasus penggunaan saya, tetapi biarkan jika Anda ingin melihat fitur XYZ beri tahu saya ... Saya hidup untuk menulis kode.) .

public interface LruCache<KEY, VALUE> {
    void put ( KEY key, VALUE value );

    VALUE get ( KEY key );

    VALUE getSilent ( KEY key );

    void remove ( KEY key );

    int size ();
}

Anda mungkin bertanya-tanya apa itu getSilent . Saya menggunakan ini untuk pengujian. getSilent tidak mengubah skor LRU dari suatu item.

Pertama yang tidak bersamaan ....

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LruCacheNormal<KEY, VALUE> implements LruCache<KEY,VALUE> {

    Map<KEY, VALUE> map = new HashMap<> ();
    Deque<KEY> queue = new LinkedList<> ();
    final int limit;


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );

        /*If there was already an object under this key,
         then remove it before adding to queue
         Frequently used keys will be at the top so the search could be fast.
         */
        if ( oldValue != null ) {
            queue.removeFirstOccurrence ( key );
        }
        queue.addFirst ( key );

        if ( map.size () > limit ) {
            final KEY removedKey = queue.removeLast ();
            map.remove ( removedKey );
        }

    }


    public VALUE get ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        queue.addFirst ( key );
        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

The queue.removeFirstOccurrence adalah operasi berpotensi mahal jika Anda memiliki cache yang besar. Orang bisa mengambil LinkedList sebagai contoh dan menambahkan peta hash reverse lookup dari elemen ke node untuk membuat operasi penghapusan BANYAK LEBIH CEPAT dan lebih konsisten. Saya mulai juga, tetapi kemudian menyadari bahwa saya tidak membutuhkannya. Tapi mungkin...

Ketika put dipanggil, kunci akan ditambahkan ke antrian. Ketika mendapatkan disebut, kunci akan dihapus dan kembali ditambahkan ke bagian atas dari antrian.

Jika cache Anda kecil dan membuat item mahal maka ini harus menjadi cache yang baik. Jika cache Anda benar-benar besar, maka pencarian linier bisa menjadi leher botol terutama jika Anda tidak memiliki area cache yang panas. Semakin banyak hot spot, semakin cepat pencarian linier karena item panas selalu berada di bagian atas pencarian linear. Ngomong-ngomong ... apa yang diperlukan agar ini berjalan lebih cepat adalah menulis LinkedList lain yang memiliki operasi hapus yang memiliki elemen terbalik ke pencarian simpul untuk dihapus, kemudian menghapusnya akan secepat menghapus kunci dari peta hash.

Jika Anda memiliki cache di bawah 1.000 item, ini akan bekerja dengan baik.

Berikut ini adalah tes sederhana untuk menunjukkan operasinya dalam tindakan.

public class LruCacheTest {

    @Test
    public void test () {
        LruCache<Integer, Integer> cache = new LruCacheNormal<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == null || die ();
        ok |= cache.getSilent ( 1 ) == null || die ();
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();

        if ( !ok ) die ();

    }
}

Cache LRU terakhir adalah utas tunggal, dan tolong jangan membungkusnya dengan sinkronisasi apa pun ....

Ini adalah tikaman pada versi bersamaan.

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentLruCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    private final ReentrantLock lock = new ReentrantLock ();


    private final Map<KEY, VALUE> map = new ConcurrentHashMap<> ();
    private final Deque<KEY> queue = new LinkedList<> ();
    private final int limit;


    public ConcurrentLruCache ( int limit ) {
        this.limit = limit;
    }

    @Override
    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );
        if ( oldValue != null ) {
            removeThenAddKey ( key );
        } else {
            addKey ( key );
        }
        if (map.size () > limit) {
            map.remove ( removeLast() );
        }
    }


    @Override
    public VALUE get ( KEY key ) {
        removeThenAddKey ( key );
        return map.get ( key );
    }


    private void addKey(KEY key) {
        lock.lock ();
        try {
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }


    }

    private KEY removeLast( ) {
        lock.lock ();
        try {
            final KEY removedKey = queue.removeLast ();
            return removedKey;
        } finally {
            lock.unlock ();
        }
    }

    private void removeThenAddKey(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }

    }

    private void removeFirstOccurrence(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
        } finally {
            lock.unlock ();
        }

    }


    @Override
    public VALUE getSilent ( KEY key ) {
        return map.get ( key );
    }

    @Override
    public void remove ( KEY key ) {
        removeFirstOccurrence ( key );
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString () {
        return map.toString ();
    }
}

Perbedaan utama adalah penggunaan ConcurrentHashMap, bukan HashMap, dan penggunaan Lock (saya bisa lolos dengan disinkronkan, tapi ...).

Saya belum mengujinya di bawah api, tetapi sepertinya cache LRU sederhana yang mungkin berhasil di 80% kasus penggunaan di mana Anda memerlukan peta LRU sederhana.

Saya menyambut umpan balik, kecuali mengapa Anda tidak menggunakan perpustakaan a, b, atau c. Alasan saya tidak selalu menggunakan perpustakaan adalah karena saya tidak selalu ingin setiap file perang menjadi 80MB, dan saya menulis perpustakaan jadi saya cenderung membuat lib plug-mampu dengan solusi yang cukup bagus di tempat dan seseorang dapat memasang -di penyedia cache lain jika mereka suka. :) Saya tidak pernah tahu kapan seseorang mungkin membutuhkan Guava atau ehcache atau sesuatu yang lain yang saya tidak ingin sertakan, tetapi jika saya membuat caching plug-mampu, saya tidak akan mengecualikan mereka juga.

Pengurangan ketergantungan memiliki imbalannya sendiri. Saya suka mendapatkan umpan balik tentang cara menjadikan ini lebih sederhana atau lebih cepat atau keduanya.

Juga jika ada yang tahu siap untuk pergi ....

Ok .. Saya tahu apa yang Anda pikirkan ... Mengapa dia tidak hanya menggunakan entri removeEldest dari LinkedHashMap, dan saya harus tetapi .... tapi .. tapi .. Itu akan menjadi FIFO bukan LRU dan kami mencoba menerapkan LRU.

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };

Tes ini gagal untuk kode di atas ...

        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();

Jadi di sini adalah cache FIFO yang cepat dan kotor menggunakan removeEldestEntry.

import java.util.*;

public class FifoCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    final int limit;

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
         map.put ( key, value );


    }


    public VALUE get ( KEY key ) {

        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

FIFO cepat. Tidak mencari-cari. Anda dapat mem-depan FIFO di depan LRU dan itu akan menangani sebagian besar entri panas dengan cukup baik. LRU yang lebih baik akan membutuhkan elemen pembalik untuk fitur Node.

Ngomong-ngomong ... sekarang saya menulis beberapa kode, biarkan saya memeriksa jawaban lain dan melihat apa yang saya lewatkan ... pertama kali saya memindai mereka.

LinkedHashMapadalah O (1), tetapi membutuhkan sinkronisasi. Tidak perlu menemukan kembali roda di sana.

2 opsi untuk meningkatkan konkurensi:

1. Buat beberapa LinkedHashMap, dan hash ke mereka: Contoh: LinkedHashMap[4], index 0, 1, 2, 3. Pada tombol do key%4 (atau binary ORon [key, 3]) untuk memilih peta mana yang akan dilakukan put / get / remove.

2. Anda dapat melakukan 'hampir' LRU dengan memperluas ConcurrentHashMap, dan memiliki struktur peta hash yang terhubung di setiap wilayah di dalamnya. Penguncian akan terjadi lebih rinci daripada LinkedHashMapyang disinkronkan. Dibutuhkan satu putatau putIfAbsenthanya kunci di kepala dan ekor daftar (per wilayah). Pada menghapus atau mendapatkan seluruh wilayah harus dikunci. Saya ingin tahu apakah daftar yang ditautkan dari Atom dapat membantu di sini - mungkin demikian bagi kepala daftar. Mungkin lebih.

Struktur tidak akan menyimpan pesanan total, tetapi hanya pesanan per wilayah. Selama jumlah entri jauh lebih besar dari jumlah wilayah, ini cukup baik untuk sebagian besar cache. Setiap daerah harus memiliki jumlah entri sendiri, ini akan digunakan daripada jumlah global untuk pemicu penggusuran. Jumlah standar wilayah dalam a ConcurrentHashMapadalah 16, yang banyak untuk sebagian besar server saat ini.

1. akan lebih mudah untuk menulis dan lebih cepat di bawah konkurensi moderat.

2. akan lebih sulit untuk menulis tetapi skalanya jauh lebih baik pada konkurensi yang sangat tinggi. Akan lebih lambat untuk akses normal (sama seperti ConcurrentHashMaplebih lambat daripada di HashMapmana tidak ada konkurensi)

Ada dua implementasi open source.

Apache Solr memiliki ConcurrentLRUCache: https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

Ada proyek sumber terbuka untuk ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/

Saya akan mempertimbangkan menggunakan java.util.concurrent.PriorityBlockingQueue , dengan prioritas ditentukan oleh penghitung "numberOfUses" di setiap elemen. Saya akan sangat, sangat berhati - hati untuk mendapatkan semua sinkronisasi saya yang benar, karena penghitung "numberOfUses" menyiratkan bahwa elemen tidak dapat berubah.

Objek elemen akan menjadi pembungkus untuk objek dalam cache:

class CacheElement {
    private final Object obj;
    private int numberOfUsers = 0;

    CacheElement(Object obj) {
        this.obj = obj;
    }

    ... etc.
}

Semoga ini membantu .

import java.util.*;
public class Lru {

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {

        private static final long serialVersionUID = -3588047435434569014L;

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    };
 }
 public static void main(String[] args ) {
    Map<Object, Object> lru = Lru.lruCache(2);      
    lru.put("1", "1");
    lru.put("2", "2");
    lru.put("3", "3");
    System.out.println(lru);
}
}

LRU Cache dapat diimplementasikan menggunakan ConcurrentLinkedQueue dan ConcurrentHashMap yang dapat digunakan dalam skenario multithreading juga. Kepala antrian adalah elemen yang telah lama berada di antrian. Ekor antrian adalah elemen yang telah berada di antrian dalam waktu singkat. Saat ada elemen di Peta, kita bisa menghapusnya dari LinkedQueue dan memasukkannya di bagian ekor.

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

public class LRUCache<K,V> {
  private ConcurrentHashMap<K,V> map;
  private ConcurrentLinkedQueue<K> queue;
  private final int size; 

  public LRUCache(int size) {
    this.size = size;
    map = new ConcurrentHashMap<K,V>(size);
    queue = new ConcurrentLinkedQueue<K>();
  }

  public V get(K key) {
    //Recently accessed, hence move it to the tail
    queue.remove(key);
    queue.add(key);
    return map.get(key);
  }

  public void put(K key, V value) {
    //ConcurrentHashMap doesn't allow null key or values
    if(key == null || value == null) throw new NullPointerException();
    if(map.containsKey(key) {
      queue.remove(key);
    }
    if(queue.size() >= size) {
      K lruKey = queue.poll();
      if(lruKey != null) {
        map.remove(lruKey);
      }
    }
    queue.add(key);
    map.put(key,value);
  }

}

Inilah implementasi saya untuk LRU. Saya telah menggunakan PriorityQueue, yang pada dasarnya berfungsi sebagai FIFO dan bukan threadsafe. Comparator Bekas berdasarkan pembuatan waktu halaman dan berdasarkan pada melakukan urutan halaman untuk waktu yang terakhir digunakan.

Halaman untuk dipertimbangkan: 2, 1, 0, 2, 8, 2, 4

Halaman yang ditambahkan ke dalam cache adalah: 2
Halaman yang ditambahkan ke dalam cache adalah: 1
Halaman yang ditambahkan ke dalam cache adalah: 0
Halaman: 2 sudah ada dalam cache. Waktu diakses terakhir yang diperbarui
Page Fault, HALAMAN: 1, Diganti dengan HALAMAN: 8
Halaman yang ditambahkan ke dalam cache adalah: 8
Halaman: 2 sudah ada dalam cache. Waktu diakses terakhir yang diperbarui
Page Fault, HALAMAN: 0, Diganti dengan HALAMAN: 4
Halaman yang ditambahkan ke dalam cache adalah: 4

KELUARAN

Halaman LRUCache
-------------
PageName: 8, PageCreationTime: 1365957019974
PageName: 2, PageCreationTime: 1365957020074
PageName: 4, PageCreationTime: 1365957020174

masukkan kode di sini

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;


public class LRUForCache {
    private PriorityQueue<LRUPage> priorityQueue = new PriorityQueue<LRUPage>(3, new LRUPageComparator());
    public static void main(String[] args) throws InterruptedException {

        System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4");
        System.out.println("----------------------------------------------\n");

        LRUForCache cache = new LRUForCache();
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("1"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("0"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("8"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("4"));
        Thread.sleep(100);

        System.out.println("\nLRUCache Pages");
        System.out.println("-------------");
        cache.displayPriorityQueue();
    }


    public synchronized void  addPageToQueue(LRUPage page){
        boolean pageExists = false;
        if(priorityQueue.size() == 3){
            Iterator<LRUPage> iterator = priorityQueue.iterator();

            while(iterator.hasNext()){
                LRUPage next = iterator.next();
                if(next.getPageName().equals(page.getPageName())){
                    /* wanted to just change the time, so that no need to poll and add again.
                       but elements ordering does not happen, it happens only at the time of adding
                       to the queue

                       In case somebody finds it, plz let me know.
                     */
                    //next.setPageCreationTime(page.getPageCreationTime()); 

                    priorityQueue.remove(next);
                    System.out.println("Page: " + page.getPageName() + " already exisit in cache. Last accessed time updated");
                    pageExists = true;
                    break;
                }
            }
            if(!pageExists){
                // enable it for printing the queue elemnts
                //System.out.println(priorityQueue);
                LRUPage poll = priorityQueue.poll();
                System.out.println("Page Fault, PAGE: " + poll.getPageName()+", Replaced with PAGE: "+page.getPageName());

            }
        }
        if(!pageExists){
            System.out.println("Page added into cache is : " + page.getPageName());
        }
        priorityQueue.add(page);

    }

    public void displayPriorityQueue(){
        Iterator<LRUPage> iterator = priorityQueue.iterator();
        while(iterator.hasNext()){
            LRUPage next = iterator.next();
            System.out.println(next);
        }
    }
}

class LRUPage{
    private String pageName;
    private long pageCreationTime;
    public LRUPage(String pagename){
        this.pageName = pagename;
        this.pageCreationTime = System.currentTimeMillis();
    }

    public String getPageName() {
        return pageName;
    }

    public long getPageCreationTime() {
        return pageCreationTime;
    }

    public void setPageCreationTime(long pageCreationTime) {
        this.pageCreationTime = pageCreationTime;
    }

    @Override
    public boolean equals(Object obj) {
        LRUPage page = (LRUPage)obj; 
        if(pageCreationTime == page.pageCreationTime){
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return (int) (31 * pageCreationTime);
    }

    @Override
    public String toString() {
        return "PageName: " + pageName +", PageCreationTime: "+pageCreationTime;
    }
}


class LRUPageComparator implements Comparator<LRUPage>{

    @Override
    public int compare(LRUPage o1, LRUPage o2) {
        if(o1.getPageCreationTime() > o2.getPageCreationTime()){
            return 1;
        }
        if(o1.getPageCreationTime() < o2.getPageCreationTime()){
            return -1;
        }
        return 0;
    }
}

Berikut ini adalah implementasi cache LRU bersamaan yang terbukti paling berhasil tanpa blok yang disinkronkan:

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

/**
 * @param key - may not be null!
 * @param value - may not be null!
 */
public void put(final Key key, final Value value) {
    if (map.containsKey(key)) {
        queue.remove(key); // remove the key from the FIFO queue
    }

    while (queue.size() >= maxSize) {
        Key oldestKey = queue.poll();
        if (null != oldestKey) {
            map.remove(oldestKey);
        }
    }
    queue.add(key);
    map.put(key, value);
}

/**
 * @param key - may not be null!
 * @return the value associated to the given key or null
 */
public Value get(final Key key) {
    return map.get(key);
}

}

Ini adalah cache LRU yang saya gunakan, yang merangkum LinkedHashMap dan menangani konkurensi dengan kunci sinkronisasi sederhana yang menjaga tempat-tempat menarik. Itu "menyentuh" ​​elemen seperti yang digunakan sehingga mereka menjadi elemen "segar" lagi, sehingga itu sebenarnya LRU. Saya juga memiliki persyaratan elemen saya memiliki umur minimum, yang Anda juga bisa anggap sebagai "waktu idle maksimum" diizinkan, maka Anda siap untuk penggusuran.

Namun, saya setuju dengan kesimpulan Hank dan menerima jawaban - jika saya memulai ini lagi hari ini, saya akan mengecek Guava CacheBuilder.

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;


public class MaxIdleLRUCache<KK, VV> {

    final static private int IDEAL_MAX_CACHE_ENTRIES = 128;

    public interface DeadElementCallback<KK, VV> {
        public void notify(KK key, VV element);
    }

    private Object lock = new Object();
    private long minAge;
    private HashMap<KK, Item<VV>> cache;


    public MaxIdleLRUCache(long minAgeMilliseconds) {
        this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) {
        this(minAgeMilliseconds, idealMaxCacheEntries, null);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback<KK, VV> callback) {
        this.minAge = minAgeMilliseconds;
        this.cache = new LinkedHashMap<KK, Item<VV>>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) {
            private static final long serialVersionUID = 1L;

            // This method is called just after a new entry has been added
            public boolean removeEldestEntry(Map.Entry<KK, Item<VV>> eldest) {
                // let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size.
                long age = System.currentTimeMillis() - eldest.getValue().birth;
                if (age > MaxIdleLRUCache.this.minAge) {
                    if ( callback != null ) {
                        callback.notify(eldest.getKey(), eldest.getValue().payload);
                    }
                    return true; // remove it
                }
                return false; // don't remove this element
            }
        };

    }

    public void put(KK key, VV value) {
        synchronized ( lock ) {
//          System.out.println("put->"+key+","+value);
            cache.put(key, new Item<VV>(value));
        }
    }

    public VV get(KK key) {
        synchronized ( lock ) {
//          System.out.println("get->"+key);
            Item<VV> item = getItem(key);
            return item == null ? null : item.payload;
        }
    }

    public VV remove(String key) {
        synchronized ( lock ) {
//          System.out.println("remove->"+key);
            Item<VV> item =  cache.remove(key);
            if ( item != null ) {
                return item.payload;
            } else {
                return null;
            }
        }
    }

    public int size() {
        synchronized ( lock ) {
            return cache.size();
        }
    }

    private Item<VV> getItem(KK key) {
        Item<VV> item = cache.get(key);
        if (item == null) {
            return null;
        }
        item.touch(); // idle the item to reset the timeout threshold
        return item;
    }

    private static class Item<T> {
        long birth;
        T payload;

        Item(T payload) {
            this.birth = System.currentTimeMillis();
            this.payload = payload;
        }

        public void touch() {
            this.birth = System.currentTimeMillis();
        }
    }

}

Nah untuk cache, Anda biasanya akan mencari beberapa bagian data melalui objek proxy, (URL, String ....) jadi dari segi antarmuka Anda akan menginginkan peta. tetapi untuk menendang keluar Anda ingin struktur seperti antrian. Secara internal saya akan mempertahankan dua struktur data, Prioritas-Antrian dan HashMap. Inilah implementasi yang harus dapat melakukan segalanya dalam waktu O (1).

Inilah kelas yang saya ikuti dengan cepat:

import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
    int maxSize;
    int currentSize = 0;

    Map<K, ValueHolder<K, V>> map;
    LinkedList<K> queue;

    public LRUCache(int maxSize)
    {
        this.maxSize = maxSize;
        map = new HashMap<K, ValueHolder<K, V>>();
        queue = new LinkedList<K>();
    }

    private void freeSpace()
    {
        K k = queue.remove();
        map.remove(k);
        currentSize--;
    }

    public void put(K key, V val)
    {
        while(currentSize >= maxSize)
        {
            freeSpace();
        }
        if(map.containsKey(key))
        {//just heat up that item
            get(key);
            return;
        }
        ListNode<K> ln = queue.add(key);
        ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
        map.put(key, rv);       
        currentSize++;
    }

    public V get(K key)
    {
        ValueHolder<K, V> rv = map.get(key);
        if(rv == null) return null;
        queue.remove(rv.queueLocation);
        rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue
        return rv.value;
    }
}

class ListNode<K>
{
    ListNode<K> prev;
    ListNode<K> next;
    K value;
    public ListNode(K v)
    {
        value = v;
        prev = null;
        next = null;
    }
}

class ValueHolder<K,V>
{
    V value;
    ListNode<K> queueLocation;
    public ValueHolder(V value, ListNode<K> ql)
    {
        this.value = value;
        this.queueLocation = ql;
    }
}

class LinkedList<K>
{
    ListNode<K> head = null;
    ListNode<K> tail = null;

    public ListNode<K> add(K v)
    {
        if(head == null)
        {
            assert(tail == null);
            head = tail = new ListNode<K>(v);
        }
        else
        {
            tail.next = new ListNode<K>(v);
            tail.next.prev = tail;
            tail = tail.next;
            if(tail.prev == null)
            {
                tail.prev = head;
                head.next = tail;
            }
        }
        return tail;
    }

    public K remove()
    {
        if(head == null)
            return null;
        K val = head.value;
        if(head.next == null)
        {
            head = null;
            tail = null;
        }
        else
        {
            head = head.next;
            head.prev = null;
        }
        return val;
    }

    public void remove(ListNode<K> ln)
    {
        ListNode<K> prev = ln.prev;
        ListNode<K> next = ln.next;
        if(prev == null)
        {
            head = next;
        }
        else
        {
            prev.next = next;
        }
        if(next == null)
        {
            tail = prev;
        }
        else
        {
            next.prev = prev;
        }       
    }
}

Begini cara kerjanya. Kunci disimpan dalam daftar tertaut dengan kunci terlama di bagian depan daftar (kunci baru pergi ke belakang) sehingga ketika Anda perlu 'mengeluarkan' sesuatu, Anda cukup mengeluarkannya dari depan antrian dan kemudian gunakan tombol untuk hapus nilai dari peta. Ketika sebuah item direferensikan, Anda mengambil ValueHolder dari peta dan kemudian menggunakan variabel queuelocation untuk menghapus kunci dari lokasi saat ini dalam antrian dan kemudian meletakkannya di bagian belakang antrian (sekarang yang paling baru digunakan). Menambahkan banyak hal hampir sama.

Saya yakin ada banyak kesalahan di sini dan saya belum menerapkan sinkronisasi apa pun. tetapi kelas ini akan memberikan O (1) menambah cache, O (1) menghapus item lama, dan O (1) mengambil item cache. Bahkan sinkronisasi sepele (hanya menyinkronkan setiap metode publik) masih akan memiliki sedikit pertikaian kunci karena waktu berjalan. Jika ada yang punya trik sinkronisasi pintar saya akan sangat tertarik. Selain itu, saya yakin ada beberapa optimasi tambahan yang bisa Anda terapkan menggunakan variabel maksimum sehubungan dengan peta.

Lihatlah ConcurrentSkipListMap . Seharusnya memberi Anda log (n) waktu untuk menguji dan menghapus elemen jika sudah ada dalam cache, dan waktu yang konstan untuk menambahkannya kembali.

Anda hanya perlu beberapa counter dll dan elemen pembungkus untuk memaksa memesan pesanan LRU dan memastikan barang-barang terbaru dibuang ketika cache penuh.

Inilah implementasi singkat saya, mohon kritik atau perbaiki!

package util.collection;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Limited size concurrent cache map implementation.<br/>
 * LRU: Least Recently Used.<br/>
 * If you add a new key-value pair to this cache after the maximum size has been exceeded,
 * the oldest key-value pair will be removed before adding.
 */

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;
private int currentSize = 0;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

private synchronized void freeSpace() {
    Key key = queue.poll();
    if (null != key) {
        map.remove(key);
        currentSize = map.size();
    }
}

public void put(Key key, Value val) {
    if (map.containsKey(key)) {// just heat up that item
        put(key, val);
        return;
    }
    while (currentSize >= maxSize) {
        freeSpace();
    }
    synchronized(this) {
        queue.add(key);
        map.put(key, val);
        currentSize++;
    }
}

public Value get(Key key) {
    return map.get(key);
}
}

Inilah implementasi saya sendiri untuk masalah ini

simplelrucache menyediakan caching LRU non-didistribusikan threadsafe, sangat sederhana, dengan dukungan TTL. Ini menyediakan dua implementasi:

• Bersamaan berdasarkan ConcurrentLinkedHashMap
• Disinkronkan berdasarkan LinkedHashMap

Anda dapat menemukannya di sini: http://code.google.com/p/simplelrucache/

Cara terbaik untuk mencapainya adalah dengan menggunakan LinkedHashMap yang mempertahankan urutan elemen. Berikut ini adalah contoh kode:

public class Solution {

Map<Integer,Integer> cache;
int capacity;
public Solution(int capacity) {
    this.cache = new LinkedHashMap<Integer,Integer>(capacity); 
    this.capacity = capacity;

}

// This function returns false if key is not 
// present in cache. Else it moves the key to 
// front by first removing it and then adding 
// it, and returns true. 

public int get(int key) {
if (!cache.containsKey(key)) 
        return -1; 
    int value = cache.get(key);
    cache.remove(key); 
    cache.put(key,value); 
    return cache.get(key); 

}

public void set(int key, int value) {

    // If already present, then  
    // remove it first we are going to add later 
       if(cache.containsKey(key)){
        cache.remove(key);
    }
     // If cache size is full, remove the least 
    // recently used. 
    else if (cache.size() == capacity) { 
        Iterator<Integer> iterator = cache.keySet().iterator();
        cache.remove(iterator.next()); 
    }
        cache.put(key,value);
}

}

Saya mencari cache LRU yang lebih baik menggunakan kode Java. Apakah mungkin bagi Anda untuk membagikan kode cache Java LRU Anda menggunakan LinkedHashMapdan Collections#synchronizedMap? Saat ini saya menggunakan LRUMap implements Mapdan kode berfungsi dengan baik, tapi saya sedang melakukan ArrayIndexOutofBoundExceptionpengujian beban menggunakan 500 pengguna pada metode di bawah ini. Metode ini memindahkan objek terbaru ke depan antrian.

private void moveToFront(int index) {
        if (listHead != index) {
            int thisNext = nextElement[index];
            int thisPrev = prevElement[index];
            nextElement[thisPrev] = thisNext;
            if (thisNext >= 0) {
                prevElement[thisNext] = thisPrev;
            } else {
                listTail = thisPrev;
            }
            //old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1
            // prev[0 old head] = new head right ; next[new head] = old head
            prevElement[index] = -1;
            nextElement[index] = listHead;
            prevElement[listHead] = index;
            listHead = index;
        }
    }