专栏|雪花算法系列

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,高可用系列 2核4GB
简介: 雪花算法

## 雪花算法(Snowflake)


雪花算法(Snowflake)是Twitter公司内部分布式项目采用的ID生成算法,开源后广受国内大厂的好评,在该算法影响下各大公司相继开发出各具特色的分布式生成器。


`Snowflake`生成的是Long类型的ID,一个Long类型占8个字节,每个字节占8比特,也就是说一个Long类型占64个比特。Snowflake ID组成结构:`正数位`(占1比特)+ `时间戳`(占41比特)+ `机器ID`(占5比特)+ `数据中心`(占5比特)+ `自增值`(占12比特),总共64比特组成的一个Long类型。


- **第一个bit位(1bit)**:Java中long的最高位是符号位代表正负,正数是0,负数是1,一般生成ID都为正数,所以默认为0

- **时间戳部分(41bit)**:毫秒级的时间,不建议存当前时间戳,而是用(当前时间戳 - 固定开始时间戳)的差值,可以使产生的ID从更小的值开始;41位的时间戳可以使用69年,(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年

- **工作机器id(10bit)**:也被叫做`workId`,这个可以灵活配置,机房或者机器号组合都可以

- **序列号部分(12bit)**:自增值支持同一毫秒内同一个节点可以生成4096个ID




**优点**


- 每秒能够生成百万个不同的ID,性能佳

- 时间戳值在高位,中间是固定的机器码,自增的序列在地位,整个ID是趋势递增的

- 能够根据业务场景数据库节点布置灵活挑战bit位划分,灵活度高


**缺点**


- **强依赖于机器时钟**,如果时钟回拨,会导致重复的ID生成,所以一般基于此的算法发现时钟回拨,都会抛异常处理,阻止ID生成,这可能导致服务不可用


**适用场景**


- 雪花算法有很明显的缺点就是时钟依赖,如果确保机器不存在时钟回拨情况的话,那使用这种方式生成分布式ID是可行的,当然小规模系统完全是能够使用的




## 百度(Uid-Generator)


`uid-generator`是基于`Snowflake`算法实现的,与原始的`snowflake`算法不同在于,`uid-generator`支持自`定义时间戳`、`工作机器ID`和 `序列号` 等各部分的位数,而且`uid-generator`中采用用户自定义`workId`的生成策略。


`uid-generator`需要与数据库配合使用,需要新增一个`WORKER_NODE`表。当应用启动时会向数据库表中去插入一条数据,插入成功后返回的自增ID就是该机器的`workId`数据由host,port组成。




**对于`uid-generator` ID组成结构**:


`workId`占用了22个bit位,时间占用了28个bit位,序列化占用了13个bit位。这里的时间单位是秒,而不是毫秒,`workId`也不一样,而且同一应用每次重启就会消费一个`workId`。




## 美团(Leaf)


`Leaf`同时支持号段模式和`snowflake`算法模式,可以切换使用。


### Leaf-segment数据库方案



在建一张表`leaf_alloc`:


```mysql

DROP TABLE IF EXISTS `leaf_alloc`;

CREATE TABLE `leaf_alloc` (

 `biz_tag` varchar(128)  NOT NULL DEFAULT '' COMMENT '业务key',

 `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '当前已经分配了的最大id',

 `step` int(11) NOT NULL COMMENT '初始步长,也是动态调整的最小步长',

 `description` varchar(256)  DEFAULT NULL COMMENT '业务key的描述',

 `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '数据库维护的更新时间',

 PRIMARY KEY (`biz_tag`)

) ENGINE=InnoDB;

```


test_tag在第一台Leaf机器上是1~1000的号段,当这个号段用完时,会去加载另一个长度为step=1000的号段,假设另外两台号段都没有更新,这个时候第一台机器新加载的号段就应该是3001~4000。同时数据库对应的biz_tag这条数据的max_id会从3000被更新成4000,更新号段的SQL语句如下:


```mysql

Begin

UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx

SELECT tag, max_id, step FROM table WHERE biz_tag=xxx

Commit

```


**优点**


- Leaf服务可以很方便的线性扩展,性能完全能够支撑大多数业务场景

- ID号码是趋势递增的8byte的64位数字,满足上述数据库存储的主键要求

- 容灾性高:Leaf服务内部有号段缓存,即使DB宕机,短时间内Leaf仍能正常对外提供服务

- 可以自定义max_id的大小,非常方便业务从原有的ID方式上迁移过来


**缺点**


- ID号码不够随机,能够泄露发号数量的信息,不太安全

- TP999数据波动大,当号段使用完之后还是会hang在更新数据库的I/O上,tg999数据会出现偶尔的尖刺

- DB宕机会造成整个系统不可用




**双buffer优化**


针对第二个缺点是因为在号段用完后才会出现,因此可以在消耗完前提前获取下一个号段,从而解决问题:



采用双buffer的方式,Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时,如果下一个号段未更新,则另启一个更新线程去更新下一个号段。当前号段全部下发完后,如果下个号段准备好了则切换到下个号段为当前segment接着下发,循环往复:


- 每个biz-tag都有消费速度监控,通常推荐segment长度设置为服务高峰期发号QPS的600倍(10分钟),这样即使DB宕机,Leaf仍能持续发号10-20分钟不受影响

- 每次请求来临时都会判断下个号段的状态,从而更新此号段,所以偶尔的网络抖动不会影响下个号段的更新




**Leaf高可用容灾**


对于第三点“DB可用性”问题,采用一主两从的方式,同时分机房部署,Master和Slave之间采用**半同步方式**同步数据。






### Leaf-snowflake方案


Leaf-segment方案可以生成趋势递增的ID,同时ID号是可计算的,不适用于订单ID生成场景,比如竞对在两天中午12点分别下单,通过订单id号相减就能大致计算出公司一天的订单量,这个是不能忍受的。面对这一问题,我们提供了 Leaf-snowflake方案。Leaf-snowflake方案完全沿用snowflake方案的bit位设计,即是“1+41+10+12”的方式组装ID号。对于workerID的分配,当服务集群数量较小的情况下,完全可以手动配置。Leaf服务规模较大,动手配置成本太高。所以使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID。Leaf-snowflake是按照下面几个步骤启动的:


- 启动Leaf-snowflake服务,连接Zookeeper,在leaf_forever父节点下检查自己是否已经注册过(是否有该顺序子节点)

- 如果有注册过直接取回自己的workerID(zk顺序节点生成的int类型ID号),启动服务

- 如果没有注册过,就在该父节点下面创建一个持久顺序节点,创建成功后取回顺序号当做自己的workerID号,启动服务


![Leaf-snowflake方案](Leaf-snowflake方案.png)




## 滴滴(TinyID)


`Tinyid`是基于号段模式原理实现的与`Leaf`如出一辙,每个服务获取一个号段(1000,2000]、(2000,3000]、(3000,4000]


![滴滴(TinyID)](滴滴(TinyID).png)


`Tinyid`提供`http`和`tinyid-client`两种方式接入。




### Http方式接入


**第一步**:导入Tinyid源码


```shell```


**第二步**:创建数据表


```mysql

-- 建表SQL

CREATE TABLE `tiny_id_info` (

 `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键',

 `biz_type` varchar(63) NOT NULL DEFAULT '' COMMENT '业务类型,唯一',

 `begin_id` bigint(20) NOT NULL DEFAULT '0' COMMENT '开始id,仅记录初始值,无其他含义。初始化时begin_id和max_id应相同',

 `max_id` bigint(20) NOT NULL DEFAULT '0' COMMENT '当前最大id',

 `step` int(11) DEFAULT '0' COMMENT '步长',

 `delta` int(11) NOT NULL DEFAULT '1' COMMENT '每次id增量',

 `remainder` int(11) NOT NULL DEFAULT '0' COMMENT '余数',

 `create_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '创建时间',

 `update_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新时间',

 `version` bigint(20) NOT NULL DEFAULT '0' COMMENT '版本号',

 PRIMARY KEY (`id`),

 UNIQUE KEY `uniq_biz_type` (`biz_type`)

) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'id信息表';


CREATE TABLE `tiny_id_token` (

 `id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增id',

 `token` varchar(255) NOT NULL DEFAULT '' COMMENT 'token',

 `biz_type` varchar(63) NOT NULL DEFAULT '' COMMENT '此token可访问的业务类型标识',

 `remark` varchar(255) NOT NULL DEFAULT '' COMMENT '备注',

 `create_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '创建时间',

 `update_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新时间',

 PRIMARY KEY (`id`)

) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'token信息表';


-- 添加tiny_id_info

INSERT INTO `tiny_id_info` (`id`, `biz_type`, `begin_id`, `max_id`, `step`, `delta`, `remainder`, `create_time`, `update_time`, `version`) VALUES (1, 'test', 1, 1, 100000, 1, 0, '2018-07-21 23:52:58', '2018-07-22 23:19:27', 1);

INSERT INTO `tiny_id_info` (`id`, `biz_type`, `begin_id`, `max_id`, `step`, `delta`, `remainder`, `create_time`, `update_time`, `version`) VALUES(2, 'test_odd', 1, 1, 100000, 2, 1, '2018-07-21 23:52:58', '2018-07-23 00:39:24', 3);


-- 添加tiny_id_token

INSERT INTO `tiny_id_token` (`id`, `token`, `biz_type`, `remark`, `create_time`, `update_time`) VALUES(1, '0f673adf80504e2eaa552f5d791b644c', 'test', '1', '2017-12-14 16:36:46', '2017-12-14 16:36:48');

INSERT INTO `tiny_id_token` (`id`, `token`, `biz_type`, `remark`, `create_time`, `update_time`) VALUES(2, '0f673adf80504e2eaa552f5d791b644c', 'test_odd', '1', '2017-12-14 16:36:46', '2017-12-14 16:36:48');

```


**第三步**:配置数据库


```properties

datasource.tinyid.names=primary

datasource.tinyid.primary.driver-class-name=com.mysql.jdbc.Driver

datasource.tinyid.primary.url=jdbc:mysql://ip:port/databaseName?autoReconnect=true&useUnicode=true&characterEncoding=UTF-8

datasource.tinyid.primary.username=root

datasource.tinyid.primary.password=123456

```


**第四步**:启动`tinyid-server`后测试


```properties

# 获取分布式自增ID

http://localhost:9999/tinyid/id/nextIdSimple?bizType=test&token=0f673adf80504e2eaa552f5d791b644c'

返回结果: 3


# 批量获取分布式自增ID

http://localhost:9999/tinyid/id/nextIdSimple?bizType=test&token=0f673adf80504e2eaa552f5d791b644c&batchSize=10'

返回结果:  4,5,6,7,8,9,10,11,12,13

```




### Java客户端方式接入


**第一步**:引入依赖


```xml

      <dependency>

           <groupId>com.xiaoju.uemc.tinyid</groupId>

           <artifactId>tinyid-client</artifactId>

           <version>${tinyid.version}</version>

       </dependency>

```


**第二步**:配置文件


```properties

tinyid.server =localhost:9999

tinyid.token =0f673adf80504e2eaa552f5d791b644c

```


**第三步**:`test` 、`tinyid.token`是在数据库表中预先插入数据,`test` 是具体业务类型,`tinyid.token`表示可访问的业务类型


```java

// 获取单个分布式自增ID

Long id =  TinyId . nextId( " test " );

// 按需批量分布式自增ID

List< Long > ids =  TinyId . nextId( " test " , 10 );

```

相关实践学习
如何在云端创建MySQL数据库
开始实验后,系统会自动创建一台自建MySQL的 源数据库 ECS 实例和一台 目标数据库 RDS。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
|
6月前
|
算法
雪花算法id生成器
雪花算法id生成器
396 0
|
6月前
|
存储 算法 数据库
C++ “雪花算法“原理
C++ “雪花算法“原理
128 2
|
6月前
|
算法 Java
雪花算法生成id
雪花算法生成id
|
4月前
|
算法 数据库
|
4月前
|
文字识别 算法 Java
文本,保存图片09,一个可以用id作为图片名字的pom插件,利用雪花算法生成唯一的id
文本,保存图片09,一个可以用id作为图片名字的pom插件,利用雪花算法生成唯一的id
|
5月前
|
算法 数据中心 Python
基于python雪花算法工具类Snowflake-来自chatGPT
基于python雪花算法工具类Snowflake-来自chatGPT
115 4
|
5月前
|
算法 Java
基于java雪花算法工具类SnowflakeIdUtils-来自chatGPT
基于java雪花算法工具类SnowflakeIdUtils-来自chatGPT
263 3
|
5月前
|
算法 PHP 数据中心
基于php雪花算法工具类Snowflake -来自chatGPT
基于php雪花算法工具类Snowflake -来自chatGPT
|
5月前
|
算法 数据中心 C++
基于C++雪花算法工具类Snowflake -来自chatGPT
基于C++雪花算法工具类Snowflake -来自chatGPT
|
4月前
|
存储 算法 Java
分布式自增ID算法---雪花算法(SnowFlake)Java实现
分布式自增ID算法---雪花算法(SnowFlake)Java实现
250 0