Java并发研究 ConcurrentSkipListMap与HM Linked List

本文是Java并发博客的第四篇。按照同步器和并发数据结构交替的顺序,本次是并发数据结构相关。之前介绍ConcurrentLinkedQueue的时候也提到过,并发数据结构不涉及同步器特有的问题,所以相对简单一些。分析的重点在于数据结构本身。

这次的主题是ConcurrentSkipListMap。老实说个人一开始也不知道这个类,既然有ConcurrentHashMap为什么还要有ConcurrentSkipListMap?单线程环境下的TreeMap用的次数本来就不多,并发环境下带排序的Map用得就更少了。话虽这么说,但在阅读了《the art of multiprocessor programming》第14章之后,个人发现ConcurrentSkipListMap是一个非常好的学习范本,特别是Java下HM Linked List(或者叫Harris Linked List)的实际产品代码。

如果你阅读过一些分析ConcurrentSkipListMap代码的文章的话,你可能会知道SkipList,因为名字里面就包括SkipList嘛。但实际上ConcurrentSkipListMap中维护正确性的不是SkipList,而是最底下的那一层HM Linked List。换句话说核心是在HM Linked List上,而不是帮助快速访问的SkipList。

个人建议在阅读ConcurrentSkipListMap的代码之前,了解以下内容

  1. HM Linked List
  2. HM Linked List基于marker节点的优化方式
  3. 普通的(非并发环境下的)SkipList

Read More

Java并发研究 Exchanger以及背后的dual data structure

在CLQ(ConcurrentLinkedQueue)之后,想了一下继续分析什么类比较好。

想到的是《the art of multiprocessor programming》11章中EliminationStack。当然Java的并发库里面没有这个Stack。EliminationStack是书中为了解决TreiberStack的串行特性提出的方案。TreiberStack虽然是比较简单的无锁并发数据类型,但是由于所有请求都在一个地方(top节点)上CAS,在高并发下,性能并不理想。书中认为这是TreiberStack或者说Stack本身的串行特性导致的(相对的,队列可以通过队首与队尾两个节点来分离请求),所以提出一种方案:dual stack,即在TreiberStack的基础上,push和pop两个请求配对。实际代码中先尝试常规的CAS push或者pop,如果失败,转而使用push和pop配对方式。这样做一方面把并发的请求分布到了不同的地方,另一方面提高了Stack的并发度。

为了实现push和pop请求配置,书中创建了一种Exchanger同步器,即线程A把数据给线程B,线程B把数据给线程A。(如果你奇怪pop可以给push什么数据的话,想想看pop把null给push,而push不使用pop给的数据)正好,Java的类库里也有一个叫做Exchanger的同步器,而且在注释中提到了dual data structure。所以,我想比较一下两者的实现细节。

Java类库中的Exchanger,作者除了Doug Lea还有Bill Scherer和Michael Scott,其中Michael Scott是写了dual data structure论文的两人之一(不确定Bill Scherer是不是William N. Scherer III)。这三人其实还写了SynchronousQueue,即CSP中用做channel的那种同步器,其实SynchronousQueue也是dual data structure的一种典型用法。dual data structure论文的名字是Nonblocking concurrent data structures with condition synchronization,完整的引用如下:

Scherer, William N., and Michael L. Scott. “Nonblocking concurrent data structures with condition synchronization.” International Symposium on Distributed Computing. Springer, Berlin, Heidelberg, 2004.

示例代码dualstack和dualqueue可以看这里。

http://www.cs.rochester.edu/research/synchronization/pseudocode/duals.html

Read More

Java并发学习 ConcurrentLinkedQueue以及被魔改的M&S算法

前面分析了FutureTask,一个同步器,下面分析一个经典的数据结构:队列。并发环境下的队列实现有很多,针对的问题和使用场景也有所不同。这里分析一个比较基础的lock free unbounded queue:ConcurrentLinkedQueue。

按照《the art of multiprocessor programming》里的定义,ConcurrentLinkedQueue属于total类型。即enqueue与dequeue不会阻塞。不阻塞就代表这个类不需要考虑同步器需要考虑的逻辑,专注于数据结构本身的实现上。

注意,本文并不会详细介绍M&S,也就是Michael & Scott算法,如果你有兴趣,请自行阅读论文 Michael, Maged M., and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. No. TR-600. ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE, 1995. 或者《the art of multiprocessor programming》第10章。

ConcurrentLinkedQueue在注释中提到自己是M&S的变体,但是当你看了核心代码offer与poll(分别对应enqueue与dequeue)之后你不会认为这是个变体,因为改得面目全非了。M&S算法最有名的helping在offer没有直接体现,enqueue时的二次CAS被改成了一次,最让人不可思议的是tail可以在某种情况下指向head之前的节点,也就是说数据结构,甚至queue本身的不变条件都被修改了。所以如果你想分析ConcurrentLinkedQueue的话,建议把M&S算法放在一边,以一种新算法的角度来分析和阅读。

Read More

Java并发学习 类FutureTask分析与改进

大约两个月没有写博客了,原因是最近自己一直在看《The Art of Multiprocessor Programming》。这本书从理论到实践介绍了多核编程,给出的数据结构和算法都有相应的论文。如果你想好好学习多核编程,而不是某种语言的并发机制介绍的话,非常推荐这本书。同时这本书里介绍的算法,在Java的并发库里面都能找到影子。作为继续深入学习的一部分,个人打算逐个分析典型的并发类,并且基于个人理解给出一些改进或者变化。

Java的并发库里面,从版本1.5(Java 5)开始引入了接口Future和实现类FutureTask。与其他Synchronizer(同步类)不同,FutureTask并没有依赖AQS,所以是相对简单的一个并发类。FutureTask包含执行Task和同步结果两块主要功能。这里主要分析如何同步结果。

注意,本文并不会逐行代码分析FutureTask。为了学习如何设计并发类,本文以个人理解的原型类开始,逐渐修改成为接近实际FutureTask甚至超过FutureTask的代码。

Read More

自适应分布式速率限制(distributed rate limiter)

本文是针对xratelimiter的算法说明。

https://github.com/xnnyygn/xratelimiter

首先对rate limiter做一下简单介绍。

rate limiter主要用在限流,比如希望网站的访问在一定的量的时候,对于API有调用量限制,作为云服务商限制访问用户网站的流量等等。

常见的rate limiter算法有token bucket。具体算法这里不作展开。一般实现中,会有一个记录最后添加了token的时间戳,还有一个记录当前token数的变量。由于有两个变量,在使用redis实现集中式的token bucket时无法原子修改。

Read More

基于GOSSIP的集群成员管理-成员的加入和退出

本文是对于以下项目的算法说明。

https://github.com/xnnyygn/xgossip

首先简单介绍一下GOSSIP。

GOSSIP据说最早见于论文《Epidemic Algorithms for Replicated  Database Maintenance》,对于GOSSIP有兴趣的人建议阅读一下此论文。

GOSSIP算法如论文标题是一种epidemic algorithm,可以理解为传染病的传播。有三个人A,B,C。A是传染源,当A传染给B,B传染给C之后,所有人都被传染了。在分布式系统中,可以把传染病类比为更新,当所有参与的节点都获取到了更新之后,集群达到最终一致状态。从这个角度来说,GOSSIP是一种弱一致性,或者说最终一致性算法。

Read More

Raft实现笔记-日志结构

本系列是在实现了绝大部分raft论文中描述的功能之后实现过程中遇到的问题,设计的决策等的记录。随着功能的增减,项目的逐渐完善,系统中的实现笔记可能会有偏差,但是基本上对于第一次实现或者想要理解raft的人来说可以作为一个参考。

本篇是针对0.1.0版本xraft,0.1.0之后的版本可能会有所变化。

Read More

PostGIS笔记(下)

上篇说了为什么用Geography,这篇具体讲怎么取“范围n米以内的数据”。

Rails里运行Migration,建Portal Model,以下是Schema

距离东京站1km内所有的portals

  • ST_Distance

    float ST_Distance(geography gg1, geography gg2, boolean use_spheroid);

  • ST_DWithin

    boolean ST_DWithin(geography gg1, geography gg2, double precision distance_meters, boolean use_spheroid);

结果:

Read More