扯扯ID

1,856 阅读3分钟

🙂🙂🙂关注微信公众号:【芋艿的后端小屋】有福利:

  1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
  2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
  3. 您对于源码的疑问每条留言将得到认真回复。甚至不知道如何读源码也可以请教噢
  4. 新的源码解析文章实时收到通知。每周更新一篇左右


在日常开发中,数据库的id是不可少的。在各个场景下会有不同的选择,本文对互联网上常见的ID算法进行归纳,希望对工程师们有一点点帮助。

1. 数据库自增

  1. MySQL、Oracle、PGSQL等关系数据库的id主键自增
  2. Redis、Memcached等K/V数据库的incr操作自增
    • 需要考虑持久化的问题
  3. MongoDB自己维护一个id自增集合
    • MongoDB的Update操作支持incr操作,因此可以这么做。
    • 该方式适用于支持该操作的其他数据库。

2. 类UUID算法

  1. UUID
  2. MongoDB的ObjectId

3. SnowFlake

3.1 Twitter-Snowflake

Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同。

64bits从左往右依次是

  • 1bit 保留
  • 41bits 时间戳
    • 支持69.7年需要的id。2 ^41 /365/24/60/60/1000=69.7
  • 10bits work-id
    • 支持1024个work
  • 12bits sequence-id
    • 支持每work每毫秒4096个id
    • 支持每work每秒4096000个id
    • 若当前毫秒超过4096,则sleep1毫秒,获取下一毫秒的自增

snowflake的意义,不仅仅在于提供了解决方式,更多的是一种基于Long长度实现具有时间相关性的id自增序列。因此,很多公司基于它进行二次改造适应自己的场景

3.2 Instagram SnowFlake

去中性化,基于PGSQL实现

64bits从左至右依次是

  • 41bits 时间戳
  • 13bits logic-shard-id
  • 10bits sequence-id

实现方式

  • 根据share-key获取对应的PGSQL实例-库
  • id使用PGSQL的存储过程
  • 13bits = share-key对应值%logic-share-id
  • 10bits = 该Table的auto_increment_id%(2 ^10)

好处

  • 去中性化
  • 根据id可以获得对应PGSQL实例-库

3.3 Simpleflake

64bits

  • 去中性化
  • 将work-id的12bits给sequence-id。完全随机,每毫秒有1/(2^22 )出现冲突的情况。数据量大时需要注意。
  • 未来可以平滑迁移到Twitter SnowFlake

3.4 Boundary flake

去中性化,基于erlang实现
128bits从左到右依次是

  • 64bits 时间戳
    • 和毫秒时间戳等长
  • 48bits work-id
    • 和mac地址等长,使用时要避免相同mac多个进程
  • 14bits sequence-id

3.5 自己的想法

参考Instagram SnowFlake的做法

去中心化,基于redis实现
64bits从左到右依次是

  • 1bit 保留
  • 41bits 时间戳
  • 12bits 基于logic-shard-id
  • 10bits 基于时间戳+logic-shard-id在redis里自增

4. 参考文章

  1. 互联网分布式id生成方法|msup微课干货
  2. 服务化框架-分布式Unique ID的生成方法一览
  3. 分布式系统中 Unique ID 的生成方法