分布式id生成方案概述

Terry_Tai 发布于2019-08-16 10:42 / 2444人阅读

摘要：序本文主要来聊聊分布式的生成方案。分布式的生成，以为代表的，系列算法采用的就是划分命名空间并行生成的思路。

序

本文主要来聊聊分布式id的生成方案。

目标

业务系统需要什么样的ID生成器中提出了几点目标：

唯一性

时间相关

粗略有序

可反解

可制造

主要思路

对于每个标识，都需要有一个命名空间（namespace），来保证其相对唯一性。
分布式的ID生成，以Twitter Snowflake为代表的， Flake 系列算法采用的就是划分命名空间并行生成的思路。

UUID

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字(每个字符0-F的字符代表4bit,共128bit)，以连字号分为五段，形式为8-4-4-4-12的32+4个字符。
比如bc96c351-bea3-4e53-b0a8-d9806763dd69。
主要的格式如下：

时间戳＋UUID版本号，分三段占16个字符(60bit+4bit)，

Clock Sequence号与保留字段，占4个字符(13bit＋3bit)，

节点标识占12个字符(48bit)，

version 4 基于随机数的算法，也是JDK里的算法，不管原来各个位的含义了，除了少数几个位必须按规范填，其余全部用随机数表达。

mongo object id

通过“时间+机器码+pid+inc”共12个字节，通过4+3+2+3的方式最终标识成一个24长度的十六进制字符。ObjectId是一个12字节 BSON 类型数据，有以下格式：

4个字节表示的Unix timestamp

3个字节表示的机器的ID

2个字节表示的进程ID

3个字节表示的计数器

snow flake算法

个64 bits的唯一long型的ID，使用其中41bit作为毫秒数，10bit作为机器编号，12bit作为毫秒内序列号。IdWorker

+---------------+----------------+----------------+
|timestamp(ms)42  | worker id(10) | sequence(12)  |
+---------------+----------------+----------------+

id  = timestamp | workerid | sequence (eg. 1451063443347648410)

默认采用上图字节分配方式：

第一位为未使用，接下来的41位为毫秒级时间(41位的长度可以使用69年)

5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点）

12位是毫秒内的计数（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）

snowflake生成的ID整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和workerId作区分），并且效率较高。这个算法单机每秒内理论上最多可以生成1000*(2^12)，也就是400W的ID。

snow flake算法变种 Boundary flake

Boundary flakeID 长度扩展到 128 bits:

+---------------+----------------+----------------+
|timestamp(ms)64  | worker id(48) | sequence(16)  |
+---------------+----------------+----------------+
id  = timestamp | workerid | sequence

最高 64 bits 时间戳;

然后是 48 bits 的 Worker 号 (和 Mac 地址一样长);

最后是 16 bits 的 Seq Number

由于它用 48 bits 作为 Worker ID, 和 Mac 地址的长度一样, 这样启动时不需要和 Zookeeper 通讯获取 Worker ID. 做到了完全的去中心化
它这样做的目的是用更多的 bits 实现更小的冲突概率, 这样就支持更多的 Worker 同时工作. 同时, 每毫秒能分配出更多的 ID

Simple flake

simpleflake取消 Worker 号, 保留 41 bits 的 Timestamp, 同时把 sequence number 扩展到 22 bits

+---------------+----------------+
|timestamp(ms)42  | sequence(22) 
+---------------+----------------+
id  = timestamp | sequence

Simpleflake 的特点:

sequence number 完全靠随机产生 (这样也导致了生成的 ID 可能出现重复)

没有 Worker 号, 也就不需要和 Zookeeper 通讯, 实现了完全去中心化

Timestamp 保持和 Snowflake 一致, 今后可以无缝升级到 Snowflake
缺点：

生成的 ID 重复的可能. 这个生成 ID 重复的概率随着每秒生成的 ID 数的增长而增长。

每秒生成的 ID 不能太多 (最好小于 100次/秒, 如果大于 100次/秒的场景, Simpleflake 就不适用

百度唯一id

UidGenerator

+---------------+----------------+----------------+
|timestamp(ms)29  | worker id(22) | sequence(13)  |
+---------------+----------------+----------------+
id  = sign + delta seconds | workerid | sequence

timestap
sign(1bit)固定1bit符号标识，即生成的UID为正数。

delta seconds (28 bits)前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可支持约8.7年

worker id (22 bits)
机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。

sequence (13 bits)
每秒下的并发序列，13 bits可支持每秒8192个并发。

doc

服务化框架－分布式Unique ID的生成方法一览

Leaf——美团点评分布式ID生成系统

分布式系统中唯一 ID 的生成方法

细聊分布式ID生成方法

生成全局唯一ID的3个思路，来自一个资深架构师的总结

Announcing Snowflake

A distributed, k-sortable unique ID generation system using Redis and Lua

经典的雪花算法-springboot

一个实现 Twitter SnowFlake 算法的 Go 分布式 UID 生成器

Java实现的, 基于Snowflake算法的唯一ID生成器

云服务器混合云分布式id生成器分布式数据库概述 RDS 分布式数据库概述全局id生成

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70301.html

服务器架构

摘要：我的后端书架阿里大牛，书单整合一整合一分布式生成器架构师之路这也是本文要讨论的核心问题如何高效生成趋势有序的全局唯一。轻松搞定 rabbitMQ rabbitMQ 的基本使用。 REST 真的完全适合微服务架构吗？作者根据自己的微服务经验，提出 REST 并不是微服务的唯一通信机制，从而介绍了微服务的几种通信机制，包括 REST、管道以及基于异步消息传递。同时，作者提出了在不同的场...

nidaye 2019-06-24 17:56 评论0 收藏0
java学习(一) —— java概述

摘要：编译完成后，如果没有报错，那么通过命令对字节码文件进行解释运行，执行时不需要添加后缀总结说白了，整个程序对编写运行有三步编写为后缀对程序文件通过程序文件进行编译生成文件文件名解释运行写代码编译解释运行前言最近开始学习下java，毕竟web开发还是java比较完善功能也较php更加强大。学习资料参考：https://github.com/DuGuQiuBai... 此章主要记录下...

edgardeng 2019-08-19 11:03 评论0 收藏0
理解分布式id生成算法SnowFlake

摘要：分布式生成算法的有很多种，的就是其中经典的一种。负数的二进制表示在计算机中，负数的二进制是用补码来表示的。分布式id生成算法的有很多种，Twitter的SnowFlake就是其中经典的一种。概述 SnowFlake算法生成id的结果是一个64bit大小的整数，它的结构如下图： showImg(https://segmentfault.com/img/bVVulC?w=1021&h=...

harriszh 2019-08-16 10:48 评论0 收藏0
微服务与Spring Cloud概述

摘要：微服务架构概述应用架构的发展应用是可独立运行的程序代码，提供相对完善的业务功能。阿里开源的是的典型实现。它目前由官方开发维护，基于开发，提供一套完整的微服务解决方案。微服务与Spring Cloud 随着互联网的快速发展，云计算近十年也得到蓬勃发展，企业的IT环境和IT架构也逐渐在发生变革，从过去的单体应用架构发展为至今广泛流行的微服务架构。微服务是一种架构风格，能给软件应用...

scwang90 2019-08-16 17:09 评论0 收藏0
NewSQL数据库大对象块存储原理与应用

摘要：图元数据与数据文件结构映射在建立集合的过程当中，大对象存储必须依附于普通集合存在，一个集合中的大对象仅归属于该集合，不能被另外一个集合管理。前言企业内容管理（Enterprise Content Management，ECM）系统是一种管理非结构化内容的系统，传统代表为EMC Documentum或IBM Filenet等ECM解决方案。随着大数据技术的越发普及，越来越多的客户开始...

Jenny_Tong 2019-06-25 18:23 评论0 收藏0