crdb HLC 实现

HLC

HLC是Hybrid Logical Clock的缩写，混合逻辑时钟。时钟分为物理时钟和逻辑时钟。

物理时钟: 电子设备，计算有固定频率晶体的震荡次数，存在时钟偏移和时钟漂移，会导致时钟不连续的变化，比如时间回退等, 以及长时间使用导致时钟存在偏差，普通石英晶体时钟漂移率在(10)-6s/s, 即每1 000 000s会导致1s的偏差。 原子钟的偏倚率在(10)-13.

逻辑时钟: 时间发生的逻辑顺序，可以是顺序的序号，和物理时间相对。

HLC同时使用了物理时钟和逻辑时钟，能够保证单点的时间发生器是单调递增的，同时能够尽量控制不同节点之间的时钟偏差在规定的误差范围内。主要用于分布式系统中。

HLC实现

pkg/util/hlc/hlc.go

结构体

type Timestamp struct {
	// Holds a wall time, typically a unix epoch time expressed in
	// nanoseconds.
	WallTime int64 `protobuf:"varint,1,opt,name=wall_time,json=wallTime,proto3" json:"wall_time,omitempty"`
	// The logical component captures causality for events whose wall
	// times are equal. It is effectively bounded by (maximum clock
	// skew)/(minimal ns between events) and nearly impossible to
	// overflow.
	Logical int32 `protobuf:"varint,2,opt,name=logical,proto3" json:"logical,omitempty"`
}

分为两部分，WallTime表示物理时钟，单位是纳秒，Logical表示逻辑时钟，用于在WallTime相同的时候，进行递增。 Timestamp是绝对单调递增的，单点内不存在相同的Timestamp，不存在时钟的回退。

物理时钟的获取

func (c *Clock) PhysicalNow() int64 {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.getPhysicalClockLocked()
}

func (c *Clock) getPhysicalClockLocked() int64 {
	newTime := c.physicalClock()

	if c.mu.lastPhysicalTime != 0 {
		interval := c.mu.lastPhysicalTime - newTime
		if interval > int64(c.maxOffset/10) {
			c.mu.monotonicityErrorsCount++
			log.Warningf(context.TODO(), "backward time jump detected (%f seconds)", float64(-interval)/1e9)
		}
	}

	c.mu.lastPhysicalTime = newTime
	return newTime
}

// UnixNano returns the local machine's physical nanosecond
// unix epoch timestamp as a convenience to create a HLC via
// c := hlc.NewClock(hlc.UnixNano, ...).
func UnixNano() int64 {
	return timeutil.Now().UnixNano()
}

其中c.physicalClock()即调用函数UnixNano(), 直接获取当前操作系统的时间。

逻辑时钟的获取逻辑

func (c *Clock) Now() Timestamp {
	c.mu.Lock()
	defer c.mu.Unlock()
	if physicalClock := c.getPhysicalClockLocked(); c.mu.timestamp.WallTime >= physicalClock {
		// The wall time is ahead, so the logical clock ticks.
		c.mu.timestamp.Logical++
	} else {
		// Use the physical clock, and reset the logical one.
		c.mu.timestamp.WallTime = physicalClock
		c.mu.timestamp.Logical = 0
	}
}

如果获取的物理时钟小于之前的WallTime，则只进行逻辑时钟的递增。否则，重置WallTime为最新的physicalClock。

不同节点间时钟同步

分布式系统中，每个节点的时间是不精确的，各个节点的HLC也无法准确判断先后顺序，故分布式系统时间处理上出现了两种方式：

1. Timestamp oracle: 专门的一台机器用于生成时间戳。优点是时间全局排序唯一，缺点是TO存在单点问题, 跨机房问题，以及性能瓶颈问题。
2. Spanner: 通过高精度物理时钟，如原子钟、GPS，保证节点间的时钟误差在合理范围，比如Spanner能保证节点间时间误差在10ms以内。优点是完全分布式，无单点，缺点是无全局排序唯一的时间生成。

crdb使用类似snapper的方式，但是没有使用专用硬件，需要通过节点间通信来控制节点间的时钟误差。

所有节点间的gRPC消息都会把时间戳带入到消息中，接收到消息的节点会通过消息中的时间戳更新自己的时间, 从而达到节点间时间同步的效果。

func (c *Clock) updateLocked(rt Timestamp, updateIfMaxOffsetExceeded bool) (Timestamp, error) {
	var err error
	physicalClock := c.getPhysicalClockLocked()

	if physicalClock > c.mu.timestamp.WallTime && physicalClock > rt.WallTime {
		// Our physical clock is ahead of both wall times. It is used
		// as the new wall time and the logical clock is reset.
		c.mu.timestamp.WallTime = physicalClock
		c.mu.timestamp.Logical = 0
		return c.mu.timestamp, nil
	}

	offset := time.Duration(rt.WallTime - physicalClock)
	if c.maxOffset > 0 && c.maxOffset != timeutil.ClocklessMaxOffset && offset > c.maxOffset {
		err = fmt.Errorf("remote wall time is too far ahead (%s) to be trustworthy", offset)
		if !updateIfMaxOffsetExceeded {
			return Timestamp{}, err
		}
	}

	// In the remaining cases, our physical clock plays no role
	// as it is behind the local or remote wall times. Instead,
	// the logical clock comes into play.
	if rt.WallTime > c.mu.timestamp.WallTime {
		// The remote clock is ahead of ours, and we update
		// our own logical clock with theirs.
		c.mu.timestamp.WallTime = rt.WallTime
		c.mu.timestamp.Logical = rt.Logical + 1
	} else if c.mu.timestamp.WallTime > rt.WallTime {
		// Our wall time is larger, so it remains but we tick
		// the logical clock.
		c.mu.timestamp.Logical++
	} else {
		// Both wall times are equal, and the larger logical
		// clock is used for the update.
		if rt.Logical > c.mu.timestamp.Logical {
			c.mu.timestamp.Logical = rt.Logical
		}
		c.mu.timestamp.Logical++
	}
	return c.mu.timestamp, err
}

rt表示rpc中消息的时间戳， 更新逻辑如下：

1. 获取本地物理时间pt

2. 如果pt大于之前的c.mu.timestamp.WallTime本地时间，且pt大于rt，则使用pt时间

3. 如果rt时间大于c.mu.timestamp.WallTime
   

   c.mu.timestamp.WallTime = rt.WallTime
   c.mu.timestamp.Logical = rt.Logical + 1

4. 如果rt时间小于c.mu.timestamp.WallTime
   

   c.mu.timestamp.Logical = rt.Logical + 1

5. 如果rt时间等于c.mu.timestamp.WallTime
   

   if rt.Logical > c.mu.timestamp.Logical {
   	c.mu.timestamp.Logical = rt.Logical
   }
   c.mu.timestamp.Logical++

总之就是比较pt，rt, c.mu.timestamp，取其最大者作为最新时间。