- 手艺 tags:
- algorithm
- distribute published: true comments: true
分布式系统中检测节点的工作情况，最直观的方法是采用心跳包的方式，通过定时发送心跳包，如果对端节点没有正常返回，则认为此节点处在failure状态，这时系统需要采取一定的措施来保证正常运行。目前，Zookeeper就是采用这种方式（org.apache.zookeeper.ClientCnxn）。
但是为了避免由于网络抖动等等意外因素导致的误报，通常在心跳包的基础上做一些改进。我在盛大做服务的路由代理时，代理和后端的服务通过心跳包保持连接。当心跳包出现异常，或服务调用出现异常（类似HTTP 500的系统异常），代理会记录当时的时间戳。根据配置，代理会存储最近50次的时间戳，并且检查他们的方差，当方差小于一个阈值时，就认定服务为failure状态，将服务从列表中剔除并发送报警。在一些测试里，这套机制是可以按照预期工作的。可惜这个系统最后没有上生产系统，所以也没有实际的运维经验。
最近看到了Cassandra使用的Failure Detection机制，叫做Phi Failure Detection Model。这个思路在一定程度上跟我的方式类似，在Cassandra的实现里，他会存储最近1000次失败的信息（org.apache.cassandra.gms.FailureDetector#sampleSize_）。此外，Cassandra存储的是失败的间隔，而不是绝对的时间戳（首次失败，存储的是心跳间隔的二分之一）。判断失败的φ值是通过这个公式就算： φ = (now - last_failure) * lnE / mean(interval_samples) 当φ值大于配置的threshold时，Cassandra的Gossip机制认为这个节点为failure。默认的配置里，这个threshold值为8. 关于Phi Failure Detection Model，可以参考论文：Information Propagation on the Phi Failure Detector
而为了提高Zookeeper的Failure Detection的质量，去年的一个Google Summer of Code项目为Zookeeper引入了一些流行的检测模型，包括前面提到的Phi Failure Detector，以及Bertier的方法和Chen的方法。
Chen方法以一个固定的alpha常数，加平均到达时间作为估计的timeout值。
在Bertier方法中，用于判断心跳包失败的timeout时间通过三个参数gamma/beta/phi被动态修正：
error = now -ea - delay; （收到心跳包的时间-估计的心跳包到达时间-估计的延迟）
delay = delay + gamma * error; （根据gamma和error修正延迟）
var = var + gamma*(abs(error) - var); （error值的variation，即varn=Σ g(1-g)n-i*ei）
ea = now + avg(interval); （根据心跳包的平均间隔修正估计时间）
timeout = avg(interval) + beta*delay + phi*var (计算新的timeout)
假如心跳包在timeout后到达，timeout还需要在上面的基础上加上常数moderationStep。
GSoC项目里，gamma/beta/phi/moderationStep的默认值分别为0.1/1.0/4.0/500。Bertier方法的timeout值根据网络情况自适应。
评价一种Failure Detector的标准，包括它发现failure节点的时间和误报率。这里有GSoC项目中作者进行的实验及结论，可供参考。
