在上一篇《
Java Cache-EHCache系列之計算實例占用的內存大小（SizeOf引擎）》中有說到：在EHCache中，可以設置maxBytesLocalHeap、maxBytesLocalOffHeap、maxBytesLocalDisk值，以控制Cache占用的內存、磁盤的大小（注：這里Off Heap是指Element中的值已被序列化，但是還沒寫入磁盤的狀態，貌似只有企業版的EHCache支持這種配置；而這里maxBytesLocalDisk是指在最大在磁盤中的數據大小，而不是磁盤文件大小，因為磁盤文中有一些數據是空閑區）。那么如何實現這個需求呢？
常規設計思路
對這個需求，我們已經有SizeOfEngine用于計算內存中以及磁盤中的實例大小了，按我的常規思路，實現起來會比較簡單，直接在Store中添加maxBytes以及currentBytes字段，用于表達當前Store可以存放的最大實例大小以及當前Store已存放的實例總大小。對MemoryStore，在添加新Element之前使用DefaultSizeOfEngine計算要添加實例占用內存的大小，然后判斷要添加的數據大小和currentBytes相加的值是否會超過maxBytes，如果是，先找出已經expired的Element，將這些Element移除，如果此時還沒能在maxBytes大小的限制中添加新的Element，則對當前Store做evict操作，evict出至少超過maxBytes大小的的數據大小；如果是更新原來已存在的Element，一種方法先查找出已存在的Element，然后計算新添加的Element和原來Element占用內存大小的Delta值，如果該值大于0并且和currentBytes相加會大于maxBytes值，則如上做expire和evict操作，另一種方法是先移除已存在的Element，然后對當前Element做新添加Element操作。對DiskStore，使用DiskSizeOfEngine計算要添加的實例大小，其他和MemoryStore類似。
在EHCache中，MemoryStore和DiskStore都是使用了Segment的設計思想（不知道是否因為ConcurrentHashMap的影響，甚至Guava Cache也采用了這種Segment的設計思想），因而我們可以將maxBytes、currentBytes抽象出一個MaxBytesGuarder類，并且將該實例賦值給每個Segment實例，作為面向對象設計的基本思路，將數據和操作放在一起它已經有了maxBytes和currentBytes數據了，我們就可以嘗試這將和它相關的操作添加到這個類中，比如實例占用內存、磁盤大小的計算，因而可以將SizeOfEngine引人該類中，另外它還可以包含一個ElementEvictor實例，它可用于evict操作，同時因為MaxBytesGuarder在每個Segment共享，因而它必須是線程安全的。對更新已存在的Element可以采用添加之前先移除的方法，這樣MaxBytesGuarder就可以設計成包含如下方法：
public interface MaxBytesGuarder {
public int getCurrentSize();
public void setMaxSize(int maxSize);
public int getMaxSize();
public int addWithEvict(Element element);
public boolean canAddWithoutEvict(Element element);
public void delete(int size);
public ElementEvictor getEvictor();
public Store getStore();
}
常規的Cache設計思路是用MemoryStore存儲內存中的Element，而將DiskStore作為MemoryStore的從屬，只有在Evict發生才將Element通過DiskStore寫入磁盤，讀取時，只有在MemoryStore中找不到對應的Element時，才從DiskStore中查找，并且將找到的Element讀回MemoryStore，對這種設計MaxBytesGuarder只需要在各自的Store中存在即可。但是在EHCache當前Store的設計中，DiskStore并沒有作為MemoryStore的從屬，它們是單獨可用的Store，EHCache使用DiskBackedMemoryStore把它們聯系起來，這個在接下來的文章中會詳細分析。在DiskBackedMemoryStore的實現中，DiskStore作為authority，對每次新添加Element，會首先添加到DiskStore中，然后才是到MemoryStore，從而對MemoryStore來說，它在做evict時，直接刪除即可，因為DiskStore已經存儲了所有的Element信息。既然DiskStore可以存儲內存中的Element以及磁盤中的Element，并且對磁盤中的Element，EHCache也會在內存中有一些紀錄信息，因而它需要同時控制內存中的Element占用內存最大值以及磁盤中能保留的Element的最大值。對這個需求，以上的MaxBytesGuarder就很難辦到了，因而EHCache做了進一步的抽象，把MaxBytesGuarder拆分成兩個接口：Pool和PoolAccessor，其中Pool用于對maxSize的抽象，它包含PoolEvictor引用，已處理需要Evict時的操作，通過Pool創建PoolAccessor，PoolAccessor和一個Store相關聯，用于處理和某個Store相關的put、remove等操作，一個Pool當前Size是通過其創建的所有PoolAccessor的size總和。
Pool和PoolAccessor設計
Pool和PoolAccessor的類結構圖如下：
從類結構圖中可以知道，Pool包含maxSize、PoolEvictor、SizeOfEngine以及PoolAccessor的List，并且Pool內部所有PoolAccessor的size和是當前Pool實例當前使用的size。Pool還可用于創建相應的PoolAccessor實例，通過Pool創建的PoolAccessor會被自動的添加到Pool中。在Cache實例初始化時，它會根據配置創建相應的onHeapPool和onDiskPool，它們可以是UnboundedPool，它的createPoolAccessor方法創建UnboundedPoolAccessor實例；可以是BoundedPool，用于創建AtomicPoolAccessor；可以是StrictlyBoundedPool，用于創建LockedPoolAccessor。其中AtomicPoolAccessor和LockedPoolAccessor的區別在于對size的鎖機制，AtomicPoolAccessor使用AtomicLong紀錄size的值而不是通過鎖，這樣會引起maxSize的限制有保證的情況，比如兩個線程同時在添加Element，但是在一個線程還沒添加完成時另一個線程已經執行了判斷語句說當前還有足夠多的空間，然而事實上在第一個線程執行完成后，當前的空間可能已經不夠了，這種方式的好處是沒有鎖，效率很高，在那些對maxSize不是很敏感的項目中可以使用（感覺一般對這個值都不會很敏感）；而LockedPoolAccessor則是采用鎖的機制來保證size值的一致性，它一般用于那些對maxSize值特別敏感的項目中。PoolAccessor由Pool創建，除了從Pool中繼承Pool自身實例、SizeOfEngine實例以外，它還和一個PoolableStore相綁定，這個綁定的PoolableStore可以通過PoolAccessor向Pool中消費一個Element大小的空間（add方法）、判斷是否可以在沒有Evict的情況下消費一個Element大小的空間（canAddWithoutEvicting方法）、移除指定大小的空間、以另一個Element大小的空間替換已存在的另一個Element空間大小（replace）等。這里的add方法，當可以成功的向這個PoolAccessor消費一個Element大小的空間時，它返回新添加的Element大小，否則返回－1，表示添加失敗；另外對add方法的container表示存放該Element的實例，比如HashEntry（只用于計算大小，因而一般都用一個空的HashEntry來替代），對onDiskPoolAccessor來說，它用于表示一個DiskMarker。
PoolEvictor
PoolableStore在調用PoolAccessor的add方法用于消費Pool中一個Element大小的空間時，會調用PoolEvictor的freeSpace將該Pool相關聯的所有PoolableStore釋放掉不夠的空間大小：
protected long add(long sizeOf, boolean force) {
long newSize = getPool().getSize() + sizeOf;
if (newSize <= getPool().getMaxSize()) {
// there is enough room => add & approve
size.addAndGet(sizeOf);
return sizeOf;
} else {
// check that the element isn't too big
if (!force && sizeOf > getPool().getMaxSize()) {
// this is too big to fit in the pool
return -1;
}
// if there is not enough room => evict
long missingSize = newSize - getPool().getMaxSize();
if (getPool().getEvictor().freeSpace(getPool().getPoolableStores(), missingSize) || force) {
size.addAndGet(sizeOf);
return sizeOf;
} else {
// cannot free enough bytes
return -1;
}
}
}
PoolEvictor接口則是對如何從多個PoolableStore中evict出指定空間大小的算法的抽象，在EHCache中默認實現了兩中算法：Balanced和FromLargest。FromLargest算法比較簡單，它只需要遍歷所有的PoolableStore，每次選擇一個沒有evict過的使用空間最大的PoolableStore，嘗試從它evict出指定大小的空間直到指定大小的空間被騰出來；Balanced算法有點復雜，它先打亂PoolableStore，然后遍歷亂序的PoolableStore，每次選取其后部分PoolableStore，對齊按一下算法排序，遍歷排序后的子PoolableStore集，對每個PoolableStore嘗試evict指定大小的空間，直到evict執行成功。
/*
* The code below is a simplified version of this:
*
* float meanEntrySize = byteSize / countSize;
* float accessRate = hitRate + missRate;
* float fillLevel = hitRate / accessRate;
* float deltaFillLevel = fillLevel / byteSize;
*
* return meanEntrySize * accessRate * deltaFillLevel * hitDistributionFunction(fillLevel);
*/
因為在PoolableStore中將從磁盤evict和從內存evict定義成兩個不同的方法，因而對每種算法的PoolEvictor都由兩個子類實現：BalancedAccessOnDiskPoolEvictor、BalancedAccessOnHeapPoolEvictor和FromLargestCacheOnDiskPoolEvictor、FromLargestCacheOnHeapPoolEvictor。這里PoolableStore接口的抽象用于在提供Evict操作時的信息，如PoolEvictor中evict方法的實現、Balanced算法中的一些統計信息的獲得等：
public interface PoolableStore extends Store {
boolean evictFromOnHeap(int count, long size);
boolean evictFromOnDisk(int count, long size);
float getApproximateDiskHitRate();
float getApproximateDiskMissRate();
long getApproximateDiskCountSize();
long getApproximateDiskByteSize();
float getApproximateHeapHitRate();
float getApproximateHeapMissRate();
long getApproximateHeapCountSize();
long getApproximateHeapByteSize();
}
PoolableStroe中evict邏輯的實現
所謂evict就是使用配置的evict算法選出部分Element實例，將它們從Store中移除。對MemoryStore，它只實現evictFromOnHeap方法，而對DiskStore只需實現evictFromOnDisk方法。
對MemoryStore，evict操作的主要流程是根據配置的EvictPolicy選取下一個expired或要被evict的Element，將這個Element移除，并出發expired或evict事件，在做evict之前先判斷該Element或當前Store處于pinned狀態，如果是，則不做evict，返回false。因而這里最主要的是要如何使用EvictPolicy選取下一個要被Evict的Element。EHCache實現了四種算法：最近最少使用算法（LRU）、先進先出算法（FIFO）、最少使用算法（LFU）、鐘算法（CLOCK）。
鐘算法實現比較簡單，它隨即的選擇一個Segment，每個Segment內部保存一個evictionIterator，每一次evict調用就是從這個Iterator中獲取下一個expired Element或unpinned Element（如果該Iterator遍歷到最后一個Element，則重新開始，即像鐘一樣不同的循環），將找到的Element從該Segment中移除。
對其他的算法，都要先從MemoryStore中選取一個Element的樣本數組，然后使用不同的Policy實現獲取樣本中的候選evict Element。樣本Element數組的最大容量是30，其選取算法是：如果當前evict是因為新添加一個Element引起，則從新添加的Element所在的Segment中選取樣本，否則隨機的選取一個Segment，在選取的Segment中隨機的選取一個HashEntry鏈，將這個鏈中所有unpinned Element加入的樣本數據中，如果一條鏈不夠，則循環的查找下一條鏈直到樣本量達到指定的要求或整個Segment所有unpinned Element都已經添加到樣本中。所有的算法都是基于這些樣本選擇下一個候選的evict Element。
FifoPolicy：樣本中Update（Create）時間最早的Element。
LfuPolicy：樣本中最少被使用的Element（Hit Count最少）。
LruPolicy：樣本中最近最少被使用的Element（LastAccessTime最小）。
對DiskStore，evict操作類似MemoryStore，先找到一個DiskSubstitute（必須是DiskMarker類型）樣本數組（算法和MemoryStore中找Element樣本數組類似，最大樣本容量也是30），對找到的樣本數組采用最少使用算法（Hit Count）或根據傳入要被evict的key作為下一個evict的候選，并嘗試將該DiskSubstitute（DiskMarker）從磁盤中移除，讀取磁盤中的數據并反序列化成Element，返回凡序列化后的Element實例。移除的步驟包括：將他從MemoryStore中移除；將DiskSubstitute對應的節點從HashEntry中刪除；釋放該Element原本在磁盤中占用的空間；釋放Disk Pool中占用的空間；釋放Heap Pool中占用的空間。
posted on 2013-11-03 00:49
DLevin 閱讀(3030)
評論(1) 編輯 收藏 所屬分類:
EHCache