Skip to content

Sntpd开发日志2 Marzullo算法

实现了学生T分布之后,有趣的是,在集群中使用时发现sntpd的偏移量变化非常有规律
student-t-offset

最后我确认是两个问题引起的:

  1. s.poll 的区间设置得过长,时钟一旦偏移,要花很长的时间去校正
  2. 由于95%置信区间的设定,导致时钟源总是变化,因此总有跳变

读了一次论文之后,发现,DLM博士早就知道这事,而且在论文中也指出了这种只使用offset的方法是他们的第一版算法……但是发现由于时钟dispersion(误差)的存在,导致时钟offset不一定准确,会丢掉误差的数值,所以他们使用了Marzullo算法。

https://en.wikipedia.org/wiki/Marzullo%27s_algorithm

marzullo-example-1

看着很复杂,但是主要思想却相当简单,就是先假设所有的区间都是“好区间”,把区间值按大小排序,得出最多的夹杂着最少最大值的区间,然后在反向求最多的夹杂着最少最小值的区间。如果得不出,就缩减窗口项,好区间=所有区间减一,直到找到为止。

以下是我的Go实现

# iset 即区间拆分之后的数值
func (s *Service) marzullo(iset []Interset) (surviors []*Peer) {
sort.Sort(byOffset(iset))
nlist := len(iset) / 2
nl2 := len(iset)
var n int
low := time.Hour
high := -time.Hour
for allow := 0; 2*allow < nlist; allow++ {
n = 0
for _, set := range iset {
low = set.val
n -= set.typE
if n >= nlist-allow {
break
}
}
n = 0
for j := nl2 - 1; j > 0; j-- {
high = iset[j].val
n += iset[j].typE
if n >= nlist-allow {
break
}
}
if high > low {
break
}
}
var p *Peer
for i := 0; i < len(iset); i += 2 {
p = iset[i].peer
if high <= low || p.offset+p.rootDistance < low || p.offset-p.rootDistance > high {
continue
}
surviors = append(surviors, p)
}
return
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.