LinkedHashMap, Java 1.4'te, HashMap'in O(1) ortalama arama süresi ile belirli bir yineleme sırasını (ya eklenme veya erişim sırası) sağlayan çift yönlü bağlantılı bir listeyi birleştiren bir hibrit veri yapısı olarak tanıtılmıştır. Tasarımı, alt sınıfların, harita belirli bir boyutu aştığında true döndürerek LRU (En Son Kullanılan) tahliye politikalarını uygulamasına olanak tanıyan removeEldestEntry şablon yöntemini tanıttı. Ancak, uygulanışı eşzamanlı kullanım için asla tasarlanmamıştır; HashMap'in thread-safe olmayan doğasını devralır ve tüm girişler arasında çift yönlü before ve after işaretçilerini sürdüğünü karmaşık hale getirir, bunlar ağaçlaşmış kovalar içinde bile geçerlidir.
Eşzamanlı yapı değişikliği altında —örneğin, bir iş parçacığı ekleme yaparken diğeri silme veya boyut değiştirme gerçekleştiriyorsa— bağlantılı liste işaretçileri atomik olmayan bir şekilde güncellenebilir ve girişlerin dairesel referanslar oluşturduğu veya ana zincirden yalıtıldığı bozulmuş bir grafik yapısına yol açabilir. Örneğin, Eğer İş Parçacığı A bir girişin after işaretçisini Giriş B'ye işaret edecek şekilde güncellerken, İş Parçacığı B eşzamanlı olarak Giriş B'yi çıkarır ve before işaretçisini güncellerse, liste A'nın B'ye işaret ettiği ve B'nin C'ye işaret ettiği şekilde sona erebilir, bu da A'yı atlayarak veya bir döngü yaratabilir. Bu bozulma, yineleyicilerin sonsuz döngülerde dönmesine (CPU'nun %100'ünü tüketmesine) veya geçerli girişleri sessizce atlamasına neden olur, bu da removeEldestEntry politikasını güvenilmez hale getirir çünkü "en yaşlı" işaretçisi artık listenin gerçek başını yansıtmayabilir.
LinkedHashMap'i çok iş parçacıklı ortamlarda güvenle kullanmak için, tüm işlemleri dışarıdan senkronize etmelisiniz. accessOrder=true önbellekleri için, hatta get() bile yapısal bir değişikliktir (bağlantılı listeyi yeniden sıralar), bu nedenle ReadWriteLock optimizasyonları, okuma işlemleri için geçersizdir; tüm işlemleri yazma olarak değerlendirmeli veya global bir mutex kullanmalısınız. En güvenli yaklaşım Collections.synchronizedMap'dir, ancak yinelemeler sırasında harita üzerinde manuel olarak senkronize olmalısınız. Ancak, üretim sistemleri için LinkedHashMap'in yerini alacak şekilde Caffeine veya Guava'nın CacheBuilder'ını kullanmalısınız, bu kütüphaneler, küresel çatışma olmadan kilitlerin şeritlenmiş veya tamamen eşzamanlı tahliye algoritmaları sağlar.
public class SafeLRUCache<K, V> { private final Map<K, V> map; public SafeLRUCache(int maxSize) { // LinkedHashMap thread-safe DEĞİLDİR; dışarıdan senkronize edin this.map = Collections.synchronizedMap(new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }); } // Tüm yöntemler, harita üzerinde senkronize olmalıdır public V get(K key) { synchronized (map) { return map.get(key); } } public void put(K key, V value) { synchronized (map) { map.put(key, value); } } // İterasyon, açık senkronizasyon gerektirir public void forEach(BiConsumer<K, V> action) { synchronized (map) { map.forEach(action); } } }
Bir e-ticaret platformu için bir arka uç hizmeti, veritabanı yükünü azaltmak için ürün fiyat verileri için bellek içi bir önbelleğe ihtiyaç duydu. İlk uygulama, accessOrder=true olan LinkedHashMap kullandı ve 1.000 öğelik bir sınır uygulamak için removeEldestEntry'yi geçersiz kıldı, haritanın otomatik olarak eski girişleri atacağı varsayımında bulundu. Düşük yük testlerinde, bu doğru çalıştı; ancak, 40 eşzamanlı iş parçacığın anlık satışlarla başa çıktığı bir üretim trafiği altında, hizmet ara sıra CPU zirveleri ile %100'e ulaştı ve sonunda iş parçacığı açlığı yaptı.
İş parçacığı dökümleri, birden fazla iş parçacığının LinkedHashMap yineleyicileri içinde sıkışmış olduğunu, eşzamanlı değişiklikler nedeniyle çift yönlü bağlantılı listedeki dairesel referansları geçerken ortaya çıkardığını gösterdi. Özellikle, bir iş parçacığı iç tablayı yeniden boyutlandırırken, diğeri bir girişin erişim sırasını güncellerken, bir Entry düğümünün after işaretçisi kendisine işaret edecek şekilde referans alarak, yineleme sırasında sonsuz bir döngü oluşturdu. Ayrıca, removeEldestEntry geri araması, "en yaşlı" işaretçisi eşzamanlı yeniden sıralamadan dolayı bozulduğu için yanlış girişleri kaldırmayı zaman zaman başardı ve bu da önbellek hırpalanmasına neden oldu, çünkü yeni erişilen öğeler, kalıcı olanların yerine atıldı.
Ekip ilk önce haritayı Collections.synchronizedMap ile sararak değerlendirdi. Artıları: Bu, minimal kod değişiklikleri gerektirir ve her bir işlemi synchronized yöntemlere sararak atomiklik sağlar. Eksileri: Bu, küresel bir monitör ekler ve tüm okuma ve yazmaları serileştirerek, beklenen 20.000 işlem/saniyeden çatışma altında 3.000'in altına düşmüştür. Dahası, yineleyicilerin hala açık synchronized(map) blokları gerektirmesi, geliştirme ekiplerinin zaman zaman unutmasına neden oldu ve bu da ConcurrentModificationException'a yol açtı.
Sonra, ConcurrentHashMap ile bir ConcurrentLinkedQueue kullanarak yenilik değerlendirdiler. Artıları: Bu, okuma ve yazma için yüksek eşzamanlılık sunar. Eksileri: LRU'yu düzgün bir şekilde uygulamak hata yapma olasılığı yüksektir; en yaşlı girişi kaldırmak, eklemeyle atomik değildir ve önbelleğin yüksek yük altında geçici olarak boyut limitini önemli ölçüde aşmasına neden olabilir. Ayrıca, her get() işlemi sırasında kuyruğun güncellenmesi bir yazma işlemi gerektirir ve benzer çatışma noktaları oluşturur ve kuyruk ile harita arasında tutarlılığı sağlamak karmaşıklaşır.
Son olarak, Caffeine adlı yüksek performanslı bir önbellek kütüphanesini değerlendirdiler. Artıları: Bu, kilit şeritleri ve tahliye için bir yazma arabellekleri ile birlikte BoundedLocalCache kullanır ve kilitsiz yüksek verimli okumalar ile yüksek verimli yazmalar sağlar. LRU/W-TinyLFU tahliyelerini açık senkronizasyon olmadan atomik olarak işler. Eksileri: Bu, bir dış bağımlılık ekler ve yeni bir API'yi (örn. CacheLoader) öğrenmeyi gerektirir.
Ekip, yük testi göstermiştir ki Caffeine, 80.000+ işlem/saniyeye kadar destekleyebilmekte iken, senkronize LinkedHashMap 5k ops/saniye'te darboğaza girdi ve p99 gecikmeleri 500ms'ye kadar çıkmıştır. Geçiş, haritayı Caffeine.newBuilder().maximumSize(1000).build() ile değiştirmek ve temizlik mantığı için bir kaldırma dinleyici kaydetmekle ilgiliydi.
Dağıtım sonrası izleme, CPU kullanımının istikrarlı olduğunu ve sıfır iş parçacığının takıldığını gösterdi. Ön belleğin vurulma oranı %85'ten %94'e yükseldi çünkü tahliye deterministik ve yarış koşulu olmayan hale geldi. Olay, LinkedHashMap'in, uygun API'sine rağmen, eşzamanlı LRU önbellekler için uygun olmayan tek iş parçacıklı bir veri yapısı olduğunu vurguladı.
Yüksek hash çakışmaları nedeniyle ağaçlaşmış kovalar içinde taşınan girişler için LinkedHashMap LRU sıralamasını nasıl sürdürmektedir?
LinkedHashMap, HashMap.Node'dan türeyen ve before ve after işaretçilerini içeren özel bir iç sınıf Entry kullanır. Bir kova ağaçlaşınca LinkedHashMap, hala LinkedHashMap.Entry'den ( LinkedHashMap.TreeNode üzerinden) türeyen TreeNode örnekleri oluşturmak için newTreeNode yöntemini geçersiz kılar. Sonuç olarak, even when entries are stored in a tree structure for O(log n) collision resolution, they remain nodes in the global doubly-linked list. The afterNodeAccess method updates these pointers after every access, ensuring the LRU chain traverses entries regardless of whether they reside in linked lists or trees within the hash table.
Neden get() işleminin accessOrder=true olan LinkedHashMap üzerinde yineleme sırasında çağrıldığında bir ConcurrentModificationException tetiklenirken, standart HashMap üzerinde aynı işlem tetiklenmez?
accessOrder modunda, LinkedHashMap, get() işlemini yapısal bir değişiklik olarak kabul eder çünkü erişilen girişi çift yönlü bağlantılı listenin sonuna taşır ve modCount değerini arttırır. Hata hızlı şekilde aynı sayacı kontrol eden yineleyici değişimi tespit ettiğinde hemen fırlatır. Buna karşılık, standart bir HashMap yalnızca ekleme, silme ve yeniden boyutlandırma işlemlerinde modCount değerini arttırır; get() tablo yapısına göre yalnızca okuma işlemi olarak değerlendirilir. Bu ayrım, hatta "salt okunur" mantıksal işlemlerin bile LinkedHashMap'de yineleyicileri geçersiz kılabileceği anlamına gelir ve eşzamanlı olarak yineleme yapılırken okumalar dahil tüm işlemlerin senkronizasyon gerektirmesini zorunlu kılar.
LinkedHashMap üzerinde eşzamanlı yeniden boyutlandırma (rehashing) sırasında meydana gelen belirli işaretçi bozulması, standart bir HashMap'de mümkün değildir?
Yeniden boyutlandırma sırasında, HashMap düğümleri yeni bir tablo dizisine aktarırken, eğer eşzamanlı yapılırsa kovalar içinde sonsuz döngüler riski taşır. LinkedHashMap ayrıca yardımcı bağlantılı listeyi oluşturan before ve after işaretçilerinin bozulma riski taşır. Eğer İş Parçacığı A, yeni tabloda sıralamayı korumak için girişleri yeniden bağlantılarken, İş Parçacığı B listeyi değiştirirse (örn. remove ile), İş Parçacığı A, İş Parçacığı B'nin zaten bağlantısını kestiği bir girişin ardılına giriş yapabilir. Bu da dolaylı referans veya döngü yaratır. Özellikle, başlık düğümünün after işaretçisi, başka bir iş parçacığı tarafından sıfırlanan bir girişi işaret edebilir, bu da liste invariant'ını kırar ve next() bozulmuş zincirde ilerlerken sonsuz döngüye neden olur.