性能文章>浅谈JDK并发包下面的分治思想及分治思想在高并发场景的运用>

浅谈JDK并发包下面的分治思想及分治思想在高并发场景的运用原创

698618

提到分治思想,大家比较容易想起其在归并排序与快速排序中的运用。今天先给大家分享一下JDK并发包下面分治思想的运用,再和大家分享一下如何利用分治思想解决高并发场景下面的一些问题。本文说的分治思想是广义范围的分治。可能和大家之前理解的分治不太一样。我理解的分治思想是并行处理、分开处理。关键在于并行与分开,并行提高速率,分开隔离资源,达到并行且互不影响。如果我说分治时,你想到的是Dubbo集群的负载均衡策略、Redis Cluster下面的节点、Kafka的分区Partition,很可能我理解的分治与你理解的是一样的。为了提高大家的阅读兴趣,先抛出高并发场景下面的两个问题?

  1. Redis集群下面能支持的QPS只有20,现在有一个热点key的QPS是100,在不扩容的提前下如何支持这个热点key上面的操作?
  2. 商品的库存采用分布式锁保证正确性(不超卖或少卖),现在分布式锁能支持的QPS只有20,而热门商品QPS为100,如何利用这个分布式锁保证热门商品购买正确性?

JDK并发包下面的分治思想

大家可能都知道JDk7中ConcureentHashMap中采用分段加锁思想来提高ConcurrentHashMap在并发场景下面的效率。在JDK7中ConcurrentHashMap内部维护了一个Segment的数组,一个key会映射到Segment数组中的某一个Segment上,一个线程对于这个key的操作只是对这个Segment进行加锁进行操作;其它线程可以并行的操作其它Segemet上的key,而不会阻塞挂起。这里的分段加锁,便可以理解为我上面说的分治思想。一个ConcurrentHashMap分开为多个Segment,多个线程可以并行处理各个Segment上的key,只要线程操作的key映射的Segment不是同一个,线程就可以并处理。扩容操作也是针对Segment进行隔离的,而不是针对整个ConcurrentHashMap进行扩容,这点与HashMap扩容的实现不一致。
JDK8中引入了LongAdder类。该类在高并发时性能优于AtomicLong,AtomicInteger等类。AtomicLong的原子增加(getAndIncrement)、原子减少(getAndDecrement)等操作,依赖于不断地自旋CAS操作。如果在竞争激烈的情况下,大量线程的CAS操作将失败,这些线程将不断地自旋尝试CAS操作直到对应值设置成功,这势必造成大量的CPU消耗。为此LongAdder采用了分治的思想,当并发量不太高时其直接通过不断地在其内部成员变量base上进行自旋CAS操作设置值,这时实际与AtomicLong实现一致;当并发量很高时,不同线程的自旋CAS操作会映射到LongAdder内部Cell数组中的某一个Cell上,从而减少了单个值上面自旋CAS操作失败的次数,降低了CPU因为CAS自旋操作失败的消耗。
上面说的ConcurrentHashMap与LongAdder都采用分治的思想将并发的请求分发不同的区间,实现上各区间相互隔离,互不影响。ConcurrentHashMap是通过Segement数组进行分治,而LongAdder则通过Cell数组进行分治。下图简单描述通过分区分治的思相来提高整体并行度。

image.png

image.png

分法思想在高并发场景的运用

1、Redis集群下面能支持的QPS只有20,现在有一个热点key的QPS为100,在不扩容的提前下如何支持这个热点key上面的操作?
热点key的QPS为100,而Redis集群支持的QPS只有20,如果能够利用分治思想将热点key拆分为5个映射的MapKey,每次对热点key操作采用一定的算法转换为对映射的MapKey操作,这时5个映射的MapKey整体能支持的QPS将为100,最终达到了热点key在Redis集群支持的QPS只有20时,能达到保证热点key的QPS达到100。下图给出了采用分治思想,将热点key拆分为5个映射的MapKey的整体过程。

image.png

上面提到每次对热点key操作采用一定的算法转换为对映射的MapKey操作,这里面说的一定的算法大家有没有联想到什么?Dubbo集群负载均衡LoadBalance算法,Random LoadBalance、RoundRobin LoadBalance、LeastActive LoadBalance、ConsistentHash LoadBalance。针对不同的业务场景可以借鉴LoadBalance算法,将热点key的操作转为映射MapKey上的操作。分治的本质就是减少单一个体上的压力,这个个体可以是一个节点(Dubbo中服务节点、Redis集群中的节点)、可以是热点Key、也可以是资源(商品库存)等。JDK中的ConcurrentHashMap与LongAdder则分别是Segement与Cell,只不过Segement下面聚集一下很多的key,而Cell保存了具体要进行原子操作的value。
2、商品的库存采用分布式锁保证正确性(不超卖或少卖),现在分布式锁能支持的QPS只有20,而热门商品QPS为100,如何利用这个分布式锁保证热门商品购买正确性?
结合上面热点key的解决思路,采用分治的方式,将热门商品分成5份分别存储,当对热门商品的请求到来时按一定算法将请求转换为对这5份中的某一份的请求,此时分式锁将加在这5份中的某一份上面,而不是直接加在热商品上面。达到最终热门商品QPS支持100的效果。

总结

今天给大家分享了我对分治思想的理解,从JDK的ConcurrentHashMap与LongAdder,聊到了两个具体的高并发场景,如何利用分治进行优化。大家下次再碰到数据量很大或者QPS很高的问题时,首先要想到的就是分治法,这招应该基本能应对大部分问题,关键在对什么进行分治,采取什么策略分治。数据量很大或者QPS很高本质都是大规模,一个是针对于空间维度,另一个是针对时间维度。分治思想要解决的就是这种大规模问题。写这篇文章的目的一个是为了归纳总结,另一个是时刻提醒自己下次再阅读源码时能多思考提炼其中的精华然后能迁移到实际场景中。可能JDk7中ConcurrentHashMap分段加锁与LongAdder的Cell数组分摊单个数据上并发操作量,不足以让我们马上想到这是分治。但当我们去不断地思考、归纳、联系、总结时,我们会发现其中背后的核心思想与本质是分治。我能说我在这个时候感受到搞马哲人的屌不?不得不说一个字服。水平有限写的不对的地方欢迎拍砖。

请先登录,再评论

👍受教了

1年前

为你推荐

不起眼,但是足以让你收获的JVM内存案例
今天的这个案例我觉得应该会让你涨姿势吧,不管你对JVM有多熟悉,看到这篇文章,应该还是会有点小惊讶的,不过我觉得这个案例我分享出来,是想表达不管多么奇怪的现象请一定要追究下去,会让你慢慢变得强大起来,
字符串字面量长度是有限制的
前言 偶然在一次单元测试中写了一个非常长的字符串字面量。 正文 在一次单元测试中,我写了一个很长的字符串字面量,大概10万个字符左右,编译时,编译器给出了异常告警 `java: constant
多次字符串相加一定要用StringBuilder而不用-吗?
今天在写一个读取Java class File并进行分析的Demo时,偶然发现了下面这个场景(基于oracle jdk 1.8.0_144): ``` package test; public c
如何通过反射获得方法的真实参数名(以及扩展研究)
前段时间,在做一个小的工程时,遇到了需要通过反射获得方法真实参数名的场景,在这里我遇到了一些小小的问题,后来在部门老大的指导下,我解决了这个问题。通过解决这个问题,附带着我了解到了很多新的知识,我觉得
谨防JDK8重复类定义造成的内存泄漏
概述 如今JDK8成了主流,大家都紧锣密鼓地进行着升级,享受着JDK8带来的各种便利,然而有时候升级并没有那么顺利?比如说今天要说的这个问题。我们都知道JDK8在内存模型上最大的改变是,放弃了Perm
JDK13 GA发布:5大特性解读
JDK13 GA版本 5大新特性如下: 350: Dynamic CDS Archives 351: ZGC: Uncommit Unused Memory 353: Reimplement the
译:谁是 JDK8 中最快的 GC
我们都知道 OpenJDK8 有好几个垃圾回收算法,比如 ParallelGC,CMS,还有 G1,那么哪个才是最快的?如果 GC 算法从 Java8 中默认的 ParallelGC 切换到 G1 会
高吞吐、低延迟 Java 应用的 GC 优化实践
本篇原文作者是 LinkedIn 的 Swapnil Ghike,这篇文章讲述了 LinkedIn 的 Feed 产品的 GC 优化过程,虽然文章写作于 April 8, 2014,但其中的很多内容和