雪花算法 Snowflake & Sonyflake

唯一ID算法Snowflake相信大家都不墨生，他是Twitter公司提出来的算法。非常广泛的应用在各种业务系统里。也因为Snowflake的灵活性和缺点，对他的改造层出不穷，比百度的UidGenerator、美团的Leaf、索尼的Sonyflake等等。这篇帖子主要是讲一下原生的Snowflake算法、缺点及改造方案，并分析索尼的Sonyflake源码对原生Snowflake的改造，

原生Snowflake

原生Snowflake算法使用一个64 bit的整型数据，根据当前的时间来生成ID。

原生Snowflake结构如下：

• 因为最高位是标识位，为1表示为负数，所以最高位不使用。
• 41bit 保存时间戳，精确到毫秒。也就是说最大可使用的年限是69年。
• 10bit 的机器位，能部属在1024台机器节点来生成ID。
• 12bit 的序列号，一毫秒最大生成唯一ID的数量为4096个。

原生的Snowflake算法是完全依赖于时间的，如果有时钟回拨的情况发生，会生成重复的ID，市场上的解决方案也是非常多的：

• 最简单的方案，就是关闭生成唯一ID机器的时间同步。
• 使用阿里云的的时间服务器进行同步，2017年1月1日的闰秒调整，阿里云服务器NTP系统24小时“消化”闰秒，完美解决了问题。
• 如果发现有时钟回拨，时间很短比如5毫秒,就等待，然后再生成。或者就直接报错，交给业务层去处理。
• 可以找2bit位作为时钟回拨位，发现有时钟回拨就将回拨位加1，达到最大位后再从0开始进行循环。

个人比较推荐的是最后一个方案

找2bit位作为时钟回拨位，发现有时钟回拨就将回拨位加1，达到最大位后再从0开始进行循环。

比如下图这样，从机器位上，均出来2位做回拨位：

Sonyflake

Snowflake算法是相当灵活的，我们可以根据自己的业务需要，对63 bit的的各个部分进行增减。索尼公司的Sonyflake对原生的Snowflake进行改进，重新分配了各部分的bit位:

• 39bit 来保存时间戳，与原生的Snowflake不同的地方是，Sonyflake是以10毫秒为单位来保存时间的。这样的话，可以使用的年限为 174年 比Snowflake长太多了。

const sonyflakeTimeUnit = 1e7 // nsec, i.e. 10 msec
func toSonyflakeTime(t time.Time) int64 {
return t.UTC().UnixNano() / sonyflakeTimeUnit
}
func currentElapsedTime(startTime int64) int64 {
return toSonyflakeTime(time.Now()) - startTime
}


• 8bit 做为序列号，每10毫最大生成256个，1秒最多生成25600个，比原生的Snowflake少好多，如果感觉不够用，目前的解决方案是跑多个实例生成同一业务的ID来弥补。

• 16bit 做为机器号，默认的是当前机器的私有IP的最后两位

sf.machineID, err = lower16BitPrivateIP()


func lower16BitPrivateIP() (uint16, error) {
ip, err := privateIPv4()
if err != nil {
return 0, err
}
return uint16(ip[2])<<8 + uint16(ip[3]), nil
}


对于时间回拨的问题Sonyflake简单暴力，就是直接等待 :

func (sf *Sonyflake) NextID() (uint64, error) {
const maskSequence = uint16(1<<BitLenSequence - 1)
sf.mutex.Lock()
defer sf.mutex.Unlock()
current := currentElapsedTime(sf.startTime)
if sf.elapsedTime < current {
sf.elapsedTime = current
sf.sequence = 0
} else { // sf.elapsedTime >= current
sf.sequence = (sf.sequence + 1) & maskSequence
if sf.sequence == 0 {
sf.elapsedTime++
overtime := sf.elapsedTime - current
time.Sleep(sleepTime((overtime)))
}
}
return sf.toID()
}


雪花算法 Snowflake & Sonyflake的更多相关文章

1. 雪花算法-snowflake

   雪花算法-snowflake 分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的. 有 ...

2. 分布式系统-主键唯一id,订单编号生成-雪花算法-SnowFlake

   分布式系统下 我们每台设备(分布式系统-独立的应用空间-或者docker环境) * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作 ...

3. Twitter雪花算法 SnowFlake算法 的java实现

   概述 SnowFlake算法是Twitter设计的一个可以在分布式系统中生成唯一的ID的算法,它可以满足Twitter每秒上万条消息ID分配的请求,这些消息ID是唯一的且有大致的递增顺序. 原理 Sn ...

4. 【Java】分布式自增ID算法---雪花算法 (snowflake，Java版)

   一般情况,实现全局唯一ID,有三种方案,分别是通过中间件方式.UUID.雪花算法. 方案一,通过中间件方式,可以是把数据库或者redis缓存作为媒介,从中间件获取ID.这种呢,优点是可以体现全局的递增 ...

5. 雪花算法(snowflake)delphi版

   雪花算法简单描述: + 最高位是符号位,始终为0,不可用. + 41位的时间序列,精确到毫秒级,41位的长度可以使用69年.时间位还有一个很重要的作用是可以根据时间进行排序. + 10位的机器标识,1 ...

6. 分布式唯一ID生成方案选型！详细解析雪花算法Snowflake

   分布式唯一ID 使用RocketMQ时,需要使用到分布式唯一ID 消息可能会发生重复,所以要在消费端做幂等性,为了达到业务的幂等性,生产者必须要有一个唯一ID, 需要满足以下条件: 同一业务场景要全局 ...

7. Twitter雪花算法SnowFlake算法的java实现

   https://juejin.im/post/5c75132f51882562276c5065 package javaDemo; /** * twitter的snowflake算法 -- java实 ...

8. 一秒可生成500万ID的分布式自增ID算法—雪花算法 (Snowflake，Delphi 版)

   概述 分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的. 有些时候我们希望能使用一种 ...

9. 分布式ID生成系统 UUID与雪花（snowflake）算法

   Leaf——美团点评分布式ID生成系统 -https://tech.meituan.com/MT_Leaf.html 网游服务器中的GUID(唯一标识码)实现-基于snowflake算法-云栖社区-阿 ...

随机推荐

1. 10、ASP.NET MVC入门到精通——Model(模型)和验证

   本系列目录:ASP.NET MVC4入门到精通系列目录汇总 模型就是处理业务,想要保存.创建.更新.删除的对象. 注解(通过特性实现) DisplayName Required StringLengt ...

2. Testlink安装问题收录

   1.windows下安装testlink,进入安装页面后,在检查一些相关配置环境时报错,如下:     Checking if /var/testlink/logs/ directory exists ...

3. < 独立项目 - 文本挖掘 > - 2016/10/25 第一更 - <Linux相关知识准备>

   < 独立项目 -  文本挖掘 > 项目立项的相关背景介绍,TODO方向. 一.Ubuntu环境配置 主机系统:Windows 7 SP1  64位操作系统 | i5-4210 CPU | ...

4. Sql server之路 （二）登录本地服务器

   安装环境 Microsoft SQL Server Management Studio Express  http://www.microsoft.com/zh-cn/download/details ...

5. BZOJ2883 &colon; gss2加强版

   首先离散化颜色 设pre[x]表示与x颜色相同的点上一次出现的位置,对于每种颜色开一个set维护 修改时需要修改x.x修改前的后继.x修改后的后继 询问[l,r]等价于询问[l,r]内pre[x]&l ...

6. app应用程序本地化－－备用

   一.简介 * 使用本地化功能,可以轻松地将应用程序翻译成多种语言,甚至可以翻译成同一语言的多种方言 * 如果要添加本地化功能,需要为每种支持的语言创建一个子目录,称为”本地化文件夹”,通常使用.lpr ...

7. mybatis-redis项目分析

   redis作为现在最优秀的key-value数据库,非常适合提供项目的缓存服务.把redis作为mybatis的查询缓存也是很常见的做法.在网上发现N多人是自己做的Cache,其实在mybatis的g ...

8. c&plus;&plus;构造析构顺序

   class A { public: A(){ cout << "constrcut A" << endl; }; ~A(){ cout << & ...

9. 超越村后端开发（3：安装djangorestframework&plus;序列化&plus;API开发前期准备）

   1.安装djangorestframework 1.安装djangorestframework及其依赖包markdown.django-filter. pip install djangorestfr ...

10. &period;Net-using-Class：MemoryCache 类

    ylbtech-.Net-using-Class:MemoryCache 类 初始化 System.Runtime.Caching.MemoryCache 类的新实例. 1. 程序集 System.R ...