并发读写缓存实现机制:高并发下数据写入与过期

  • 时间:
  • 浏览:0

一般来说并发的读取和写入是一对矛盾体,而缓存的过期移除和持久化则是另一对矛盾体。你你这种 节,大伙儿着重来了解下高并发情况汇报下缓存的写入、过期控制及符近相关功能。系列文章目录:并发读写缓存实现机制(零):缓存操作指南并发读写缓存实现机制(一):缘何ConcurrentHashMap时需那末快?并发读写缓存实现机制(二):高并发下数据写入与过期并发读写缓存实现机制(三):API封装和复杂化

1.高效的数据写入(put)    在研究写入机制日后,大伙儿先来回顾下上一节的内容。ConcurrentHashMap之不多有读取调快,很大一每段意味归功于它的数据分割设计,就像是把书的内容划分为啥都有有章,章下面又分了许多小节。同样的原理,写入过程也时需按你你这种 规则把数据分为啥都有有独立的块,也却说前一节提到的Segment。许多人面为了解决并发问题报告 ,加锁是有另1个不错的选泽。再回头看看Segment类图(清单1),Segment真是是继承了ReentrantLock,许多人四种 却说有另1个锁。清单1:Segment类图愿意最大限度的支持并发,却说读写操作都是加锁,JDK8 就实现了无锁的并发HashMap,传输速率更高的一并复杂化度也更大;而在锁机制中,有另1个很好的辦法 却说读操作不加锁,写操作加锁,对于竞争资源来说就时需定义为volatile类型的。volatile类型都都都可不上能保证happens-before法则,不多有volatile都都都可不上能近似保证正确性的情况汇报下最大程度的降低加锁带来的影响,一并还与写操作的锁不产生冲突。“锁分离” 技术    在竞争激烈的情况汇报下,意味写入时对缓存中所有数据都加锁,传输速率必然低下,HashTable的传输速率不高只意味你你这种 意味。为此ConcurrentHashMap默认把数据分为16个Segment,每个Segment却说一把锁,也却说有另1个独立的数据块,那末多程序读写不同Segment的数据时就完会存在锁竞争,从而时需有效的提高读写传输速率,这却说“锁分离”技术。缓存中几乎所有的操作都是基于独立的segment数据块,且在修改时时需对segment加锁。    缓存的put()操作与get()操作累似 ,得到元素修改就行了,更多的参考源码,这里有几点要注意:    a.意味对数据做了新增或移除,时需修改count的数值,你你这种 要放上去整个操作的最后,缘何?前面说过count是volatile类型,而读取操作那末加锁,不多有只有把元素真正写回Segment中的日后都都可不上能修改count值,不多有你你这种 时需要放上去整个操作的最后。    b.意味HashEntry的next属性是final的,所日后加入的元素都是再加链表的头部    c.缘何在put操作中首先建立有另1个临时变量tab指向Segment的table,而都是直接使用table?这意味table变量是volatile类型,多次读取volatile类型的开销要比非volatile开销要大,愿意编译器也无法优化,多次读写tab的传输速率要比volatile类型的table要高,JVM也都都都可不上能对此进行优化。2.巧妙的数据移除(remove)    上一节中,大伙儿也提到,为了解决在遍历HashEntry的日后被破坏,HashEntry中除了value之外许多属性都是final常量,愿意不可解决的会得到ConcurrentModificationException,这就意味,只有把节点再加到链表的后面 和尾部,却说能在链表的后面 和尾部删除节点,只有在头部再加节点。你你这种 内外部时需保证:在访问某个节点时,你你这种 节点日后的链表完会被改变。那我时需大大降低解决链表时的复杂化性。既然只有改变链表,缓存到底是何如移除对象的呢?大伙儿首先来看下面两幅图:清单2. 执行删除日后的原链表1:清单3. 执行删除日后的新链表2假设现在有一元素C时需删除,根据上一节所讲,C必然存在某一链表1中,假设你你这种 链表内外部为A->B->C->D->E,那现在该何如从链表1中删除C元素?    根据上一节的内容,大伙儿没能经过2次hash定位,即大伙儿没能定位到C所在的Segment,愿意再定位到Segment中table的下标(C所在的链表)。愿意遍历链表找到C元素,找到日后就把C的next节点D作为临时头节点构成链表2,愿意从现有头节点A日后结束了了向后迭代加入到链表2的头部,时不时到时需删除的C节点日后结束了了,即A、B依次都作为临时头节点加入链表2,最后的情况汇报却说A加入到D前面,B又加入到A前面,那我就构发明者来有另1个新的链表B->A->D->E,愿意将此链表的最新头节点B设置到Segment的table中。那我就完成了元素C的删除操作。时需说明的是,尽管就的链表仍然存在(A->B->C->D->E),愿意意味那末引用指向此链表,不多有此链表中无引用的(A->B->C)最终会被GC回收掉。那我做的有另1个好处是,意味某个读操作在删除时意味定位到了旧的链表上,那末此操作仍然将能读到数据,只不过读取到的是旧数据而已,这在多程序后面 是那末问题报告 的。    从后面 的流程时需看出,缓存的数据移除都是通过更改节点的next属性,却说通过重新构造根小新的链表来实现的,那我即保证了链条的完整篇 性,一并也保证了并发读取的正确性。源码如下: 清单4:缓存数据的移除123456789101112131415161718192021222324252627282950313233343536void removeEntry(HashEntry entry, int hash) {int c = count - 1;    AtomicReferenceArray<HashEntry> tab = table;int index = hash & (tab.length() - 1);    HashEntry first = tab.get(index);for (HashEntry e = first; e != null; e = e.next) {if (e == entry) {            ++modCount;// 从链表1中删除元素entry,且返回链表2的头节点            HashEntry newFirst = removeEntryFromChain(first, entry);// 将链表2的新的头节点设置到segment的table中            tab.set(index, newFirst);            count = c; // write-volatile,segment内的元素个数-1return;        }    }}HashEntry removeEntryFromChain(HashEntry first, HashEntry entry) {    HashEntry newFirst = entry.next;// 从链条1的头节点first日后结束了了迭代到时需删除的节点entryfor (HashEntry e = first; e != entry; e = e.next) {// 拷贝e的属性,并作为链条2的临时头节点        newFirst = copyEntry(e, newFirst);    }accessQueue.remove(entry);return newFirst;}HashEntry copyEntry(HashEntry original, HashEntry newNext) {// 属性拷贝    HashEntry newEntry = new HashEntry(original.getKey(), original.getHash(), newNext, original.value);    copyAccessEntry(original, newEntry);return newEntry;}3.按需扩容机制(rehash)    缓存中构造函数有五个参数与容量相关:initialCapacity代表缓存的初始容量、loadFactor代表负载因子、concurrencyLevel字面上的意思是并发等级,真是却说segment的数量(内内外部会转变为2的n次方)。既然有初始容量,则自然有容量缺陷的情况汇报,你你这种 情况汇报就时需对系统扩容,随之而来的却说有另1个问题报告 :何时能 扩容以及何如扩容?    第有另1个问题报告 :何时能 扩容,缓存就使用到了loadFactor负载因子,在插入元素完会先判断Segment里的HashEntry数组是与否超过阈值threshold = (int) (newTable.length() * loadFactor),意味超过阀值,则调用rehash辦法 进行扩容。     那何如扩容呢?扩容的日后首先会创建有另1个两倍于原容量的数组,愿意将原数组里的元素进行再hash后插入到新的数组里。为了传输速率缓存完会对整个容器进行扩容,而只对某个segment进行扩容。那我对于许多segment的读写都是影响。扩容的本质却说把数据的key按照新的容量重新hash放上去新组建的数组中,愿意相较于HashMap的扩容,ConcurrentHashMap有了些许改进。    大伙儿来看个小例子:假设原有数组长度为16,根据上一节知识,大伙儿知道掩码为1111,扩容后新的数组长度为16*2=32,掩码为11111。由下图时需看出扩容前掩码15到扩容后掩码31,也却说粉色那一列的掩码值由0变为1,那我子意味hash淡蓝色那一列的值那我是0,则扩容后下标和扩容前一样,意味那我是1,则扩容后下标=扩容前下标+16,由此大伙儿时需得出结论:扩容前的长度为length的数组下标为n的元素,映射到扩容后数组的下标为n或n+length。0111|1110 hash二进制0000|1111 掩码15-------------‘与’运算-----------0000|1110 扩容前数组下标0111|1110 hash二进制0001|1111 掩码31-------------‘与’运算-----------0001|1110 扩容后数组下标,比扩容前下标大500,转换为十进制却说16,中括号内代表的是扩容后的数组下标。    假设大伙儿有链表A[5] -> B[21] -> C[5] -> D[21] -> E[21] -> F[21]基于后面 的原理,ConcurrentHashMap扩容是先把链表后面 的一整段连续相同下标的元素链(D[21] -> E[21] -> F[21])找出来,直接复用你你这种 链,愿意qq克隆好友 你你这种 链日后的元素(A[5] -> B[21] -> C[5]),那我就解决了所有元素的qq克隆好友 。事实上,根据JDK的描述:Statistically, at the default threshold, only about one-sixth of them need cloning when a table double,翻译过来却说:据统计,使用默认的阈值,扩容时仅有1/6的数据时需qq克隆好友 。清单5:缓存数据的扩容12345678910111213141516171819202122232425262728295031323334353637383940414243444546void rehash() {/**     * .... 每段代码省略     */for (int oldIndex = 0; oldIndex < oldCapacity; ++oldIndex) {        HashEntry head = oldTable.get(oldIndex);if (head != null) {            HashEntry next = head.next;int headIndex = head.getHash() & newMask;// next为空代表你你这种 链表就只有有另1个元素,直接把你你这种 元素设置到新数组中if (next == null) {                newTable.set(headIndex, head);            } else {// 有多个元素时                HashEntry tail = head;int tailIndex = headIndex;// 从head日后结束了了,时不时到链条末尾,找到最后有另1个下标与head下标不一致的元素for (HashEntry e = next; e != null; e = e.next) {int newIndex = e.getHash() & newMask;if (newIndex != tailIndex) { // 这里的找到后那末退出循环,继续找下有另1个不一致的下标                        tailIndex = newIndex;                        tail = e;                    }                }// 找到的是最后有另1个不一致的,不多有tail往后的都是一致的下标                newTable.set(tailIndex, tail);// 在这日后的元素下标有意味一样,都意味不一样,不多有把前面的元素重新qq克隆好友 一遍放上去新数组中for (HashEntry e = head; e != tail; e = e.next) {int newIndex = e.getHash() & newMask;                    HashEntry newNext = newTable.get(newIndex);                    HashEntry newFirst = copyEntry(e, newNext);if (newFirst != null) {                        newTable.set(newIndex, newFirst);                    } else {accessQueue.remove(e);                        newCount--;                    }                }            }        }    }    table = newTable;this.count = newCount;}4.过期机制(expire)    既然叫做缓存,则必定存在缓存过期的概念。为了提高性能,读写数据时时需自动延长缓存过期时间。又意味大伙儿这里所讲的缓存有持久化操作,则要求数据写入DB日后缓存只有过期。    数据拥有生命周期,大伙儿可设置缓存的accessTime解决;读写数据时自动延长周期,也却说读写的日后都时需修改缓存的accessTime;那何何如证数据写入DB前只有清除缓存呢?    四种 辦法 却说定期遍历缓存中所有的元素,检测缓存中数据是与否完整篇 写入到库中,意味已写入且达到过期时间,则可移除此缓存。很明显你你这种 辦法 最大的问题报告 在于时需定期检测所有数据,也却说短期内会有高CPU负载;许多人面,缓存的过期时间不精准,意味缓存的过期是基于定期检测的,只有定期检测时间,缓存就会存在于内存中。时间轴    在平时,大伙儿意味会了解到有另1个名词:timeline,翻译过来却说“时间轴”。请看下面有另1个简单的示例清单6:时间轴TimeLine----进入时间最短-----Enter-->--D-->--C-->--B-->--A-->--进入时间最久-----大伙儿的缓存数据就存在于你你这种 时间轴上,如上例所示:数据A产生或变化后大伙儿时需把它放上去时间轴的Enter点,随着时间的推移,B、C、D也完会依次放上去Enter点,最终就形成了后面 的有另1个时间轴。当有时间轴上的数据存在变更,大伙儿再把它从时间轴上移除,当做新数据重新加入Enter点。很简单了,那大伙儿何如检测数据有那末过期?意味在时间轴上的数据都是有序的,问题报告 就缓存的产生和改变都是有先后顺序的,大伙儿假若找到第有另1个没过期的元素,则比它进入时间短的数据都是没过期的。整个流程进一步看来却说有另1个时需删除指定元素的先进先出队列,基于你你这种 原理可实现缓存的过期。删除指定元素的先进先出队列AccessQueue    目前存在四种 常见做法-双向链表形式的环状队列,在你你这种 队列中的元素提供了获取前有另1个和后有另1个元素的引用,新的元素插入到链表的尾端,过期元素从头部过期,而双向链表有另1个有点硬要的特点却说它时需很方便的从队列后面 移除元素。队列AccessQueue继承了AbstractQueue,拥有了队列的基本功能,队列内的元素都是ReferenceEntry,它有五个子类:Head(队列头)、HashEntry(队列内元素)、NullEntry(主要用于移除队列元素)。其中Head元素是时不时存在的,默认其previousAccess和nextAccess都指向head自身。清单7:接口ReferenceEntry清单8:队列AccessQueue的内外部    请看队列AccessQueue的内外部图,这里大伙儿假设队列是按照逆时针再加元素的,则元素0、1、2是依次再加到队列中的。    数据移除:假设时需移除节点1,时需先把节点1的上个节点0和下个节点2链接起来,愿意把节点1的previousAccess和nextAccess都链接到NullEntry,以确保元素1在JVM中无法再被引用,方便被GC回收。    数据新增:假设时需增加节点1到tail,有意味节点1意味存在于链表中,则时需先把节点1的上个节点0和下个节点2链接起来,愿意再再加到尾部。 清单9:时需移除元素的先进先出队列1234567891011121314151617181920212223242526272829503132333435363738394041424344454647484950staticfinalclass AccessQueue extends AbstractQueue<ReferenceEntry> {// head代码省略final ReferenceEntry head = XXX;// 许多每段代码省略    @Overridepublicboolean offer(ReferenceEntry entry) {// 将上有另1个节点与下有另1个节点链接,也却说把entry从链表中移除        connectAccessOrder(entry.getPreviousInAccessQueue(), entry.getNextInAccessQueue());// 再加到链表tail        connectAccessOrder(head.getPreviousInAccessQueue(), entry);        connectAccessOrder(entry, head);return true;    }    @Overridepublic ReferenceEntry peek() {// 从head日后结束了了获取        ReferenceEntry next = head.getNextInAccessQueue();return (next == head) ? null : next;    }    @Overridepublicboolean remove(Object o) {        ReferenceEntry e = (ReferenceEntry) o;        ReferenceEntry previous = e.getPreviousInAccessQueue();        ReferenceEntry next = e.getNextInAccessQueue();// 将上有另1个节点与下有另1个节点链接        connectAccessOrder(previous, next);// 方便GC回收        nullifyAccessOrder(e);return next != NullEntry.INSTANCE;    }}// 将previous与next链接起来staticvoid connectAccessOrder(ReferenceEntry previous, ReferenceEntry next) {    previous.setNextInAccessQueue(next);    next.setPreviousInAccessQueue(previous);}// 将nulled的previousAccess和nextAccess都设为nullEntry,方便GC回收nulledstaticvoid nullifyAccessOrder(ReferenceEntry nulled) {    ReferenceEntry nullEntry = nullEntry();    nulled.setNextInAccessQueue(nullEntry);    nulled.setPreviousInAccessQueue(nullEntry);}何时能 进行过期移除?    在拥有了定制版的先进先出队列,缓存过期就相对比较简单了,大伙儿假若把新增和修改的数据放上去队列尾部,愿意从队列首部依次判断数据是与否过期就时需了。那何时能 去执行你你这种 操作呢?google的缓存是放上去每次写入操作意味每64次读操作执行一次清理操作。一方面,意味缓存是不停在使用的,这就决定了过期的缓存不意味每段不多;许多人面,缓存的过期仅仅是时间点的判断,传输速率非常快。不多有那我操作性能并那末带来性能的降低,愿意却带来了缓存过期的准确性。清单10:读操作执行清理1234567void postReadCleanup() {// 作为位操作的mask(DRAIN_THRESHOLD),时需是(2^n)-1,也却说1111的二进制格式if ((readCount.incrementAndGet() & DRAIN_THRESHOLD) == 0) {// 代表每2^n执行一次        cleanUp();    }}清单11:缓存过期移除1234567891011void expireEntries(long now) {    drainRecencyQueue();    ReferenceEntry e;// 从头部获取,过期且已保存db则移除while ((e = accessQueue.peek()) != null && map.isExpired(e, now)) {if (e.getValue().isAllPersist()) {            removeEntry((HashEntry) e, e.getHash());        }    }}5.个数统计(size)    前面提到,缓存中数据是分为多个segment的,意味大伙儿要统计缓存的大小,就要统计所有segment的大小后求和,大伙儿是都是直接把所有Segment的count相加就时需得到整个ConcurrentHashMap大小了呢?答案当然是与否定的,真是相加时时需获取每个Segment的count的最新值,愿意拿到日后意味累加前使用的count存在了变化,那末统计结果就不准了。那该何如解决你你这种 问题报告 ?有另1个辦法 却说把所有segment都锁定愿意求和,很显然你你这种 辦法 传输速率非常低下,不可取。愿意ConcurrentHashMap里提供了另四种 解决辦法 ,却说先尝试2次通过不锁住Segment的辦法 来统计各个Segment大小,意味统计的过程中,容器的count存在了变化,则再采用加锁的辦法 来统计所有Segment的大小。那末ConcurrentHashMap是何如判断在统计的日后segment是与否存在了变化呢?答案是使用modCount变量。每个segment中都是有另1个modCount变量,代表的是对segment中元素的数量造成影响的操作的次数,你你这种 值只增不减。有了你你这种 它就时需判定segment是与否变化了。    不多有,size操作本质上却说两次循环尝试,失败了则锁定获取,你你这种 累似 无锁的操作辦法 对性能是有很大的提升,意味大每段情况汇报下两次循环尝试就时需得到结果了。源码相对比较简单,有兴趣的大伙儿时需许多人去了解下,这里就不贴出来了。总结:    结合前2节的内容,至此大伙儿就拥有了有另1个强大的缓存,它时需并发且高效的数据读写、数据加载和数据移除,支持数据过期控制和持久化的平衡。在下一节中大伙儿会在此基础上复杂化缓存的使用,以方便日常的调用。

有点硬说明:尊重作者的劳动成果,转载请注明出处哦~~~http://blog.yemou.net/article/query/info/tytfjhfascvhzxcyt207