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

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

https://github.com/xnnyygn/xratelimiter

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

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

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

Continue reading “自适应分布式速率限制(distributed rate limiter)”

基于GOSSIP的集群成员管理-失败检测

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

https://github.com/xnnyygn/xgossip

失败检测即Failure Detection,在xgossip中主要是指由于网络或者节点当机问题导致无法正常通讯的问题的检测。除此之外,检测到之后系统如何处理也是需要根据实际需求来决定的。以下主要针对这两方面进行讲解。

Continue reading “基于GOSSIP的集群成员管理-失败检测”

基于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是一种弱一致性,或者说最终一致性算法。

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

Raft实现笔记-日志结构

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

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

Continue reading “Raft实现笔记-日志结构”

Raft实现笔记-开篇

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

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

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

Continue reading “Raft实现笔记-开篇”

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

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

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

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

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

网络编程中的半包粘包问题

本文主要是讨论一下网络编程的基础,组包解包,以及常见的半包粘包。

在开发网络应用程序的话,特别是偏底层涉及具体的应用协议的时候,你可能会碰到服务端得到的数据不完全的问题。比如说客户端发送了1024个字符,但是你先得到了其中512字节,剩下的数据之后才送到。而已这通常发生在TCP协议下。理论上来说,TCP相对于另一种协议UDP,保证不会丢包,丢了也会重传,而且包的顺序是可预测的,但是对于传输的包大小没有约定。

一方面有类似nagle算法会把客户端的一些长度很短的包组合起来一次发送,另一方面因为以太网MTU等数据长度限制的存在,发到服务器的包有可能被分割成几个连续发送。前者可能会造成把逻辑上分离的包合在了一起,这通常称为粘包问题。后者可能会导致服务端处理包需要多次接收才能开始处理,这通常称为半包问题。

对于这两类问题,首先你要把TCP理解为面向流的协议,而不是包。其次你可以考虑怎么用处理文件的输入流的方式来处理网络的输入流。具体的,常见的解决方案:

  • 逻辑上定长,你可以不关心底层传输的包长度,一个逻辑上的完整包的长度
  • 使用特定分隔符分割,比如按行
  • 对于内容长度不定的数据,你可以采用先传包长度,然后传包内容
  • 应用层处理

(来自 http://www.cnblogs.com/sloong/p/5047743.html

其中,按行分割在普通文件读取中也有应用,库往往会开辟一个缓冲区,读入一定数据,找到行分隔符停止,这和网络编程中有点类似,不过网络编程的异常处理要更加小心,否则你会碰到帧(比如一行)过长等攻击。

Java NIO基础之ByteBuffer学习

Java NIO使用的数据结构不是普通的byte[],而是类似ByteBuffer的类。ByteBuffer使用起来与byte[]有很大不同,下面主要是自己学习到的一些使用方法。

ByteBuffer同时可以读写,一开始理解有点困难,建议按照推荐的操作步骤来使用ByteBuffer。即

  1. Channel#read(ByteBuffer)或者ByteBuffer#put方法,往ByteBuffer里面写入数据
  2. ByteBuffer#flip
  3. Channel#write(ByteBuffer)或者ByteBuffer#get方法,从ByteBuffer里面读取数据
  4. ByteBuffer#clear, ByteBuffer#compact

读写模式通过不同的API来切换,一般情况下,按照上面这个顺序使用ByteBuffer就可以。不过要正确理解和使用ByteBuffer,需要对ByteBuffer的内部有所了解。

ByteBuffer主要有三个位置指针(不是C/C++的pointer)

  • position,当前位置
  • limit,当前模式下的位置限制
  • capacity,分配时确定的空间大小

capacity因为一开始就被确定了,最容易理解。剩下两个位置指针需要配合ByteBuffer的“读写模式”来理解。

  1. ByteBuffer被分配之后,默认是“写模式”,因为刚分配的空间你读取是没有意义的。这时position为0,limit为capacity的值。假设代码中执行了一些写入操作,每次写入都会增加position。
  2. flip切换读写模式,position为0,即你写入的第一个byte的位置,limit变成你写入数据的最后一个byte后面的位置。
  3. 接下来你可以从ByteBuffer中读取数据了,每次读取增加position。
  4. 读取完毕之后,可以复用这个ByteBuffer,调用clear的话,position重置为0,limit设置为capacity,即回到写模式的初始状态。调用compact的话,你没有读取的数据会向前移动(System.arrayCopy),position设置为这些数据末尾之后的位置,limit设置为capacity。

用代码来测试一下

Continue reading “Java NIO基础之ByteBuffer学习”

非阻塞IO与reactor模式

在写了非阻塞IO的基础知识之后,决定学习一下常规的非阻塞IO运行模式。

所谓运行模式,就是指以怎样的代码来实现非阻塞IO服务。为了比较和说明,先从阻塞IO的线程池化的服务器开始。

这是一个简单的Echo服务。ServerSocket在accept得到一个Socket之后,由线程池中的某个线程来处理这个Socket。

Continue reading “非阻塞IO与reactor模式”

非阻塞IO与异步IO

本文是自己对最近学习到的IO相关知识的一点整理,之后会逐渐增加。

首先非阻塞IO(non-blocking IO)相信很多人都听说过,比如Nginx,Redis,NodeJS等等。得到的印象大多是非阻塞IO比传统IO(blocking IO)要好。这里多少有点误解。

非阻塞IO的目的是高并发,比如C10K这种目标。在连接数不高的时候性能并不会比传统IO好。为什么传统IO难以做到C10K,主要原因还是可以建立的进程/线程数量有限,以及高并发情况下IO等待时间太多,阻塞进程/线程运行等原因。

当然非阻塞IO并不是完全非阻塞的,IO通常分为数据等待和数据从内核空间拷贝到用户空间的两部分,传统IO(阻塞IO)在这两个步骤都会阻塞,但是非阻塞IO只在数据拷贝的时候阻塞,数据等待时系统通常会返回一个特定的异常码来提示数据未准备好。

非阻塞IO是一个行为特征,具体实现有select/poll,Linux 2.6之后的epoll等IO多路复用的系统调用。直观上来讲,非阻塞IO和IO多路复用没有关系,但是如果你一直在某个fd(文件描述符)上轮询的话,就会变得和传统IO没有区别,所以一般都是在多个fd上等待,当其中某个数据就绪了再取数据,这样就可以体现在非阻塞IO在数据等待这一步非阻塞的优势了。

从编程语言来说,非阻塞也可以选择用注册callback异步调用来实现。实际的IO类型中也有异步IO,但是大部分人都不怎么谈到异步IO,说非阻塞IO其实就是指epoll,其原因之一是Linux上AIO(异步IO)实现差强人意,Windows上IO多路复用只有select,剩下的就是异步IO,即IOCP,Windows貌似希望开发人员使用IOCP而不是开发类似epoll在Windows上的实现。服务器端开发,你懂的,Windows的用武之地很少。

IO多路复用为什么epoll脱颖而出,主要还是他的数据通知机制。select虽然大部分平台都支持,但是fd有数量限制,1024个。poll消除了这个限制,但是得到数据就绪的响应之后,你必须遍历庞大的fd列表来得到就绪的fd。epoll的优势在于返回的响应中包含数据就绪的fd,综合各方面来说是最优的。

当然epoll是Linux的系统调用,如果在Windows上你只能用select,在Solaris上你需要/dev/poll,OS X是kqueue,通常编程语言会帮你统一API,比如Java。但是关于非阻塞IO的基本知识建议还是要了解一下。

参考: