专栏首页码匠的流水账分布式id生成方案概述

分布式id生成方案概述

本文主要来聊聊分布式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 (eg. 1451063443347648410)

  • 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生成器

本文分享自微信公众号 - 码匠的流水账(geek_luandun)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-09-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 聊聊eureka的TaskDispatcher

    eureka-core-1.8.8-sources.jar!/com/netflix/eureka/cluster/ReplicationTask.java

    codecraft
  • 聊聊storm的ICommitterTridentSpout

    storm-core-1.2.2-sources.jar!/org/apache/storm/trident/spout/ICommitterTridentSp...

    codecraft
  • 聊聊storm的ICommitterTridentSpout

    storm-core-1.2.2-sources.jar!/org/apache/storm/trident/spout/ICommitterTridentSp...

    codecraft
  • Oracle mybatis 新增返回主键ID

    <selectKey resultType="String" order="BEFORE" keyProperty="enterp_no"> ...

    斯文的程序
  • 分布式系统ID的几种生成办法

    一般单机或者单数据库的项目可能规模比较小,适应的场景也比较有限,平台的访问量和业务量都较小,业务ID的生成方式比较原始但是够用,它并没有给这样的系统带来问题和瓶...

    用户1214487
  • mysql left( right ) join使用on 与where 筛选的差异

    有这样的一个问题mysql查询使用mysql中left(right)join筛选条件在on与where查询出的数据是否有差异。 可能只看着两个关键字看不出任...

    java达人
  • python:爬虫入门

    直接上代码吧: 一、爬取某外卖平台的指定商家菜品信息 from urllib import request import json import random ...

    菩提树下的杨过
  • SQLServer SQL连接查询深度探险(摘录

    测试的SQL脚本如下:此脚本适合MySQL、DB2,如果要在Oracle上执行,需要做个替换BIGINT->INTEGER,VARCHAR、->VARCHAR...

    授客
  • Google Analytics里的各种ID

    默认情况下,Google Analytics 会为每台设备分配一个唯一的 Client ID,并在报告中将每个 Client ID 视为一个唯一身份用户。Cli...

    GA小站
  • 你用.NET开发APP时,在云平台打包APP要填个“包名”的含义

    在ios平台,包名有它专有的名词:bundle ID.bundle ID可以翻译成包ID,也可以叫APP ID或者应用ID,他是每一个ios应用的全球唯一标识,...

    Amanda.li

扫码关注云+社区

领取腾讯云代金券