基于雪花算法生成分布式ID(Golang版)

2021年11月20日 阅读数:2
这篇文章主要向大家介绍基于雪花算法生成分布式ID(Golang版),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

SnowFlake算法原理介绍

在分布式系统中会将一个业务的系统部署到多台服务器上,用户随机访问其中一台,而之因此引入分布式系统就是为了让整个系统可以承载更大的访问量。诸如订单号这些咱们须要它是全局惟一的,同时咱们基本上都会将它做为查询条件;出于系统安全考虑不该当让其它人轻易的就猜出咱们的订单号,同时也要防止公司的竞争对手直接经过订单号猜想出公司业务体量;为了保证系统的快速响应那么生成算法不能太耗时。而雪花算法正好解决了这些问题。算法

SnowFlake 算法(雪花算法), 是Twitter开源的分布式id生成算法。其核心思想就是: 使用一个64 bit的long型的数字做为全局惟一id。它的结构以下:安全

下面咱们来对每一部分进一步的分析:服务器

  • 符号标识位(1位):计算机中为了区分负数(1)和正数(0),设计者将第一位作为符号位,ID一般使用正数,所以最高位固定为0;
  • 41位时间截(毫秒),这个是使用 当前时间 减去 开始时间 获得的值;所以一旦咱们的算法投入使用,那么程序中设置的开始时间就不能再去随意更改了,不然将可能出现重复的id值;
    因为是基于时间来实现的且只有41位,由此能够计算出该算法只能使用70年左右:(2^41)/(1000*60*60*24*365) = 69.7 年
  • 10位机器ID:共计1024个节点,一般将其分为2部分:机房ID(dataCenterId) 和 机器ID(workerId);
  • 12 位序列号:毫秒内的计数,共计4098个;简单来讲就是每毫秒内从0开始计算获得值;

最终SnowFlake算法总结以下:总体上按照时间自增排序,而且整个分布式系统内不会产生ID 碰撞(由机房ID和机器ID做区分),而且效率较高。最多支持1024台机器,每台机器每毫秒可以生成最多4096个ID,整个集群理论上每秒能够生成 1024 * 1000 * 4096 = 42 亿个ID。less

这里不要以为每毫秒4098个ID少了,咱们计算一下每台机器理论上每秒能够支持 4096*1000 = 400万左右;要知道天猫双11那么大的订单量每秒也才50万笔;所以是彻底够用的。分布式

算法实现

type SnowFlakeIdWorker struct {
	
	// 开始时间戳
	twepoch int64

	// 机器ID所占的位数
	workerIdBits int64

	// 数据标识ID所占的位数
	dataCenterIdBits int64

	// 支持的最大机器ID
	maxWorkerId int64

	// 支持的最大机房 ID
	maxDataCenterId int64

	// 序列在ID中占的位数
	sequenceBits int64

	// 机器ID向左移位数
	workerIdShift int64

	// 机房ID向左移位数
	dataCenterIdShift int64

	// 时间截向左移位数
	timestampLeftShift int64

	// 生成序列的掩码最大值
	sequenceMask int64

	// 工做机器ID
	workerId int64

	// 机房ID
	dataCenterId int64

	/**
	 * 毫秒内序列
	 */
	sequence int64

	// 上次生成ID的时间戳
	lastTimestamp int64

	// 锁
	lock sync.Mutex
}

func (p *SnowFlakeIdWorker) init(dataCenterId int64, workerId int64) {
	// 开始时间戳;这里是2021-06-01
	p.twepoch = 1622476800000
	// 机器ID所占的位数
	p.workerIdBits = 5
	// 数据标识ID所占的位数
	p.dataCenterIdBits = 5
	// 支持的最大机器ID,最大是31
	p.maxWorkerId = -1^(-1 << p.workerIdBits)
	// 支持的最大机房ID,最大是 31
	p.maxDataCenterId = -1^(-1 << p.dataCenterIdBits)
	// 序列在ID中占的位数
	p.sequenceBits = 12
	// 机器ID向左移12位
	p.workerIdShift = p.sequenceBits
	// 机房ID向左移17位
	p.dataCenterIdShift = p.sequenceBits+p.workerIdBits
	// 时间截向左移22位
	p.timestampLeftShift = p.sequenceBits+p.workerIdBits+p.dataCenterIdBits
	// 生成序列的掩码最大值,最大为4095
	p.sequenceMask = -1^(-1 << p.sequenceBits)

	if workerId > p.maxWorkerId || workerId < 0 {
		panic(errors.New(fmt.Sprintf("Worker ID can't be greater than %d or less than 0", p.maxWorkerId)))
	}
	if dataCenterId > p.maxDataCenterId || dataCenterId < 0 {
		panic(errors.New(fmt.Sprintf("DataCenter ID can't be greater than %d or less than 0", p.maxDataCenterId)))
	}

	p.workerId = workerId
	p.dataCenterId = dataCenterId
	// 毫秒内序列(0~4095)
	p.sequence = 0
	// 上次生成 ID 的时间戳
	p.lastTimestamp = -1
}

// 生成ID,注意此方法已经经过加锁来保证线程安全
func (p *SnowFlakeIdWorker) nextId() int64 {
	p.lock.Lock()
	defer p.lock.Unlock()

	timestamp := p.timeGen()
	// 若是当前时间小于上一次 ID 生成的时间戳,说明发生时钟回拨,为保证ID不重复抛出异常。
	if timestamp < p.lastTimestamp {
		panic(errors.New(fmt.Sprintf("Clock moved backwards. Refusing to generate id for %d milliseconds", p.lastTimestamp - timestamp)))
	}

	if p.lastTimestamp == timestamp {
		// 同一时间生成的,则序号+1
		p.sequence = (p.sequence + 1) & p.sequenceMask
		// 毫秒内序列溢出:超过最大值
		if p.sequence == 0 {
			// 阻塞到下一个毫秒,得到新的时间戳
			timestamp = p.tilNextMillis(p.lastTimestamp)
		}
	} else {
		// 时间戳改变,序列重置
		p.sequence = 0
	}
	// 保存本次的时间戳
	p.lastTimestamp = timestamp

	// 移位并经过或运算拼到一块儿
	return ((timestamp - p.twepoch) << p.timestampLeftShift) |
		(p.dataCenterId << p.dataCenterIdShift) |
		(p.workerId << p.workerIdShift) | p.sequence
}

func (p *SnowFlakeIdWorker) tilNextMillis(lastTimestamp int64) int64 {
	timestamp := p.timeGen()
	for ;timestamp <= lastTimestamp; {
		timestamp = p.timeGen()
	}
	return timestamp
}

func (p *SnowFlakeIdWorker) timeGen() int64 {
	return time.Now().UnixNano()/1e6
}

使用示例线程

idWorker := &SnowFlakeIdWorker{}
idWorker.init(0, 1)
fmt.Println(idWorker.nextId())

注意:对于一个业务来讲只须要建立一个SnowFlakeIdWorker对象便可。设计

注意服务器不能发生时钟回拨,即系统时间发生错误,由于雪花算法是基于时间来生成,全部当发生时钟回拨后会致使出现重复ID的问题。code