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

给开始在日本学习生活的人的一点参考:在日本看病(2)

上篇大致讲了一下在日本看病的常识。小毛小病在诊所能解决掉是最好的,不过有些必须去医院,比如我昨天做的拔智齿的手术。

本文主要是记录自己拔智齿的前后过程,顺带讲一下医院与诊所的不同。

前篇中也提到过,如果直接去医院,也就是是紹介状なし(しょうかいじょうなし,没有介绍信)的情况下去的话,会收额外的一笔不少的费用。所以建议先在诊所看病,如果不行的话,可以让诊所开介绍信,你再去医院。

这次我就是親知らずの抜歯(おやしらずのばっし、拔智齿),需要动手术,歯科(しか、牙科)帮忙开了介绍信。注意开介绍信也是要费用的,但是比没介绍信直接去医院要便宜。我拿到的介绍信是一个信封,上面给你指定了医院,科室和医生。信封里面的内容我没有确认,估计就是你在这家诊所的病例卡。

Read More

给开始在日本学习工作的人的一点参考:在日本看病(1)

最近到医院预约了拔智齿,突然想到对于一个到了人生地不熟的日本,而且不喜欢抱团的人来说,如何在日本学习或者工作的同时看病是一个很大的难题。语言是一方面,日本和国内大相径庭的看病方式也需要时间适应。所以,考虑了下,分享顺便也记录下自己的看病经历。

到现在为止,个人经历过的主要是皮肤科(皮膚科、ひふか),牙医(歯科、しか)。个人体质原因,不大感冒,没去过耳鼻咽喉科(耳鼻咽喉科、じびいんこうか)。不过今年春天好像得了花粉症(花粉症、かふんしょう),可能之后会去。

和国内不同,小毛小病这边不会去医院(病院、びょういん),而是先去诊所(クリニック)。直接去医院的话,会额外收一笔费用,而且你会等很长时间。

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

Raft实现笔记-开篇

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

现在,2018-08-09已经实现的功能

  • leader election + log replication
  • membership change(one server change)
  • log compaction(snapshot)

Read More

你想做偏技术的项目呢?还是偏业务的项目?

最近和某人聊天,谈论一些工作上的环境等等。谈话中让我想起来以前的主管问过我的一个问题:你想做偏技术的项目呢?还是偏业务的项目?这种问题估计在程序员的面谈中并不少见,而且有变体,比如问你之后想做什么类型的项目等等。对于很多偏技术的程序员,比如喜欢看技术类杂志,参与技术类活动,甚至无时不刻不在学习最新技术的人来说,选择偏技术向的项目更多一些。按照自己的兴趣正面回答这个问题固然很好,但是有些时候需要审视一下这个问题的背后主管的意图。

猜测主管的想法并不是说主管对你有猜忌,只是像做题时理解出题者的出发点一样分析一下主管为什么会这么问,期望得到什么样的答案。从主管角度来说,他除了要完成自己的任务之外,理论上还需要引导自己的下属。具体可能是帮你解决一些问题,辅导你工作上的成长,甚至推荐你升职等等。而从公司层面来说,一个能解决问题的员工比一个不能解决问题,或者花了更长时间解决问题的员工更好。更现实一点,一个代码平平或者还相对差的人比一个代码比他好甚至高一个等级却花了几个星期解决一个中小问题的人更受欢迎。这是一个比较残酷的公司潜规则。比较常见的是,你在某个需求中为了让某个功能更通用自己造了某个小的框架,但是开发时间比其他人要长。代码质量上你确实比其他人高,甚至bug也相对其他人少,只是很少有人会在有代码问题时问你问题,组外的人也不理解你的代码能力,主管面谈时甚至被”虽然你写的代码在组内相对不错“等评价,过了一段时间之后你就会觉得苦恼,对这样一种不被认可的环境所困扰。

对于本应在程序方面最拿手的程序员来说,参与各种项目,解决掉负责的需求,通过自己的技术给公司带来价值,公司给予相应的薪酬,还有阶段性的升职。但是现实情况是,你所看到的公司代码很多都是一种被同化的平淡无奇的有时候违背最佳实践的代码,偶尔会有一些可能会造成性能,安全问题的代码会被CR出来改掉,而你所做的优化,改进,框架等并没有受到主管或者其他人进一步的期待,特别是他们自己对于代码要求不高的时候。负责任的主管可能会适当的时候与你交流下代码的关注度问题,引导你关注一下其他方面。比如系统发展,业务前景等等。如果你在让项目顺利进行上还有所欠缺的话,可能还会要求加强那些方面。此时的主管如果问你这个问题,主管会综合你的回答和你的现状来进一步阐述他的一些想法,换句话说,面谈时候的这个问题,你的答案并不重要,特别是在半年评价的时候。

大部分项目,都是有具体的业务需求,配合代码上的修改来实现的,少部分升级安全,性能等自发的技术型项目。后者在基础开发组比较多,但是偏基础的组肯定不会问让你在业务和技术中选择的问题。所以大部分时候,你要明白,公司层面期望的是越快越好地完成项目,并不关注你的代码。理解这一点,之后很多事情就可以轻松一些了。