在上一篇《
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 阅读(3008)
评论(1) 编辑 收藏 所属分类:
EHCache