mzh/blog

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
}