业界常用的分布式ID生成算法
分布式id生成
- 对于IM应用来说，消息ID（或称序列号）是个看似不起眼，但非常重要的东西之一。
- 1）UUID：这种方法简单直观，可以很好的保证唯一性，但对于技术洁癖的人来说ID长度会有点长，而且是无序的；
- 2）使用时间戳长整数：这个最偷懒，用在吞吐量不大的场景下，凑活也能用，但存在重复的风险，也无法保证分布式下的唯一性；
- 3）使用twitter开源的snowflake算法：在分布式高并发的情况下，这也是个不错的选择；
- 4）按用户使用独立的ID生成空间生成顺序的ID：比如微信的消息序列号生成策略就很不错。
分布式唯一id：snowflake算法思考
- snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。
- 优点：快，简单，熟悉原理后可更根据时机情况调整位段
- 缺点：依赖机器时间。解决方法可参考美团的leaf-snowflake
百度分布式ID生成器UidGenerator
- baidu开源的UidGenerator，UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。
- 引入了高性能队列高性能队列disruptor中RingBuffer思想，进一步提升了效率。
- UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。 在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
DefaultUidGenerator
- 如果选用UidGenerator的DefaultUidGenerator，一定要根据你的业务的情况和特点，调整各个字段占用的位数
- DefaultUidGenerator的关键实现点
- a. synchronized保证线程安全；
- b. 如果时间有任何的回拨，那么直接抛出异常；（简单粗暴）
- c. 如果当前时间和上一次是同一秒时间，那么sequence自增。如果同一秒内自增值超过2^13-1，那么就会自旋等待下一秒（getNextSecond）；
- d. 如果是新的一秒，那么sequence重新从0开始。
CachedUidGenerator
- CachedUidGenerator是DefaultUidGenerator的重要改进实现。它的核心利用了RingBuffer，它本质上是一个数组，数组中每个项被称为slot。CachedUidGenerator设计了两个RingBuffer，一个保存唯一ID，一个保存flag。RingBuffer的尺寸是2^n，n必须是正整数。
- 自增列：CachedUidGenerator的workerId在实例每次重启时初始化，且就是数据库的自增ID，从而完美的实现每个实例获取到的workerId不会有任何冲突；
- RingBuffer：CachedUidGenerator不再在每次取ID时都实时计算分布式ID，而是利用RingBuffer数据结构预先生成若干个分布式ID并保存；（这就是借助未来时间来生成id）
- 时间递增：传统的SnowFlake算法实现都是通过System.currentTimeMillis()来获取时间并与上一次时间进行比较，这样的实现严重依赖服务器的时间。而CachedUidGenerator的时间类型是AtomicLong，且通过incrementAndGet()方法获取下一次的时间，从而脱离了对服务器时间的依赖，也就不会有时钟回拨的问题（这种做法也有一个小问题，即分布式ID中的时间信息可能并不是这个ID真正产生的时间点
Ring Buffer的概念，其实来自于Linux内核（Maybe），是为解决某些特殊情况下的竞争问题提供了一种免锁的方法。这种特殊的情况就是当生产者和消费者都只有一个，而在其它情况下使用它也是必须要加锁的。
环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区中可写的缓冲区。通过移动读指针和写指针就可以实现缓冲区的数据读取和写入。在通常情况下，环形缓冲区的读用户仅仅会影响读指针，而写用户仅仅会影响写指针。如果仅仅有一个读用户和一个写用户，那么不需要添加互斥保护机制就可以保证数据的正确性。如果有多个读写用户访问环形缓冲区，那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区。
解密融云IM产品的聊天消息ID生成策略
http://www.52im.net/thread-2747-1-1.html
设计思路
- 融云消息数据的唯一 ID 长度采用 80 Bit。
- 每 5 个 Bit ，进行一次 32 进制编码，转换为一个字符，字符取值范围是：数字 “2 ~ 9 ”和字母“A ~ B”。其中，已经去掉容易造成肉眼混淆的数字 0 和 1 （余下可用的数字就是8个了），及字母 O 和 I（余下可用的字母就是24个了），那么总可用字符就是32个（刚好可按32进制进行编码）。
- 这样，80 Bit 可以转换为 16 个字符，再加上 3 个分隔符（ - ），将 16 个字符分为 4 组，最终得到一个 19 字符的唯一 ID ，形如：“ BD8U-FCOJ-LDC5-L789 ”。 这样设计，即可以保证生成的 ID 是有序的，也能方便阅读。
- 80bit分为四段：
- 1）第一段 42 Bit：用于存放时间戳，最长可表示到 2109 年，足够开发者当前使用了。时间戳数据放在高位，可以保证生成的唯一 ID 是按时间有序的，这个是消息 ID 必须要满足的条件。
- 2）第二段 12 Bit：用于存放自旋转 ID 。我们知道，时间戳的精度是到毫秒的，对于一套亿级 IM 系统来说，同一毫秒内产生多条消息太正常不过了，这个自旋 ID 就是在给落到同一毫秒内的消息进行自增编号。12 Bit 则意味着，同一毫秒内，单台主机中最多可以标识 4096（ 2 的 12 次方）条消息。
- 3）第三段 4 Bit：用于标识会话类型。4 Bit ，最多可以标识 16 中会话，足够涵盖单聊、群聊、系统消息、聊天室、客服及公众号等常用会话类型。
- 4）第四段 22 Bit：会话 ID 。如群聊中的群 ID ，聊天室中的聊天室 ID 等。与第三段会话类型组合在一起，可以唯一标识一个会话。其他的一些 ID 生成算法，会预留两段，分别用来标识数据中心编号和主机编号（如 SnowFlake 算法），我们并没有这样做，而是将这两段用来标识会话。这样，ID 生成可以直接融入到业务服务中，且不必关心服务所在的主机，做到无状态扩缩容。
- 注意点：
- 1）注意保证自旋 ID 的生成是线程安全的；
- 2）避免在并发情况下，生成出同样的 ID ；
- 3）此 ID 生成算法，强烈依赖系统时间，如果系统时间被改小，理论上也可能造成 ID 生成重复。
微信IM序列号生成算法与容灾实践
IM消息ID技术专题(一)：微信的海量IM聊天消息序列号生成实践（算法原理篇）
IM消息ID技术专题(二)：微信的海量IM聊天消息序列号生成实践（容灾方案篇）
背景
- 微信服务器端为每一份需要与客户端同步的数据（例如聊天消息）都会赋予一个唯一的、递增的序列号（后文称为 sequence ），作为这份数据的版本号（这是利用了序列号递增的特性）。
- seq是递增的64位整形变量
- 每个用户都有自己独立的64位seq空间（够用了）
- 原因：全局唯一的seq很难做到高可用，所以用户独立即可
算法
- 服务端存储的seq空间可以抽象为一个巨大的64位数组，其中每个元素存放着对应用户当前已分配的最后一个seq，每个用户来申请时，只需要将seq+1存储并返回即可
- 考虑到仅要求递增，不要求连续，所以可出现跳跃的msgid，每次+1都要持久化非常吃磁盘IO，于是微信实现了一个简单优雅的策略，简单优雅的策略：
- 1）内存中储存最近一个分配出去的sequence：cur_seq，以及分配上限：max_seq；
- 2）分配sequence时，将cur_seq++，同时与分配上限max_seq比较：如果cur_seq > max_seq，将分配上限提升一个步长max_seq += step，并持久化max_seq；
- 3）重启时，读出持久化的max_seq，赋值给cur_seq。
- 实际应用中步长为10000，持久化IO次数从10^7 qps降低到10^3 qps
- 分号段共享存储优化：上述方案看上去很不错了，但还有个缺点是重启时需要读取大量max_seq到内存中，实际上每个用户不用单独分配一个max_seq，可以将uid相邻的一段用户聚合成一个号段，同一个号段所有用户共享一个max_seq，这样可大幅减少max_seq数据的大小，也可以减少磁盘IO
架构与高可用
- 考虑到可靠性和容灾，微信把消息id生成服务分成两个模块：StoreSvr与AllocSvr，StoreSvr为存储层，利用NRW策略保证不丢失;而每台 AllocSvr 负责若干号段的 sequence 分配，
- 高可用核心：任意时刻任意 uid 有且仅有一台 AllocSvr 提供服务，就可以比较容易地实现 sequence 递增不回退的要求
- 单点服务：于是，Alloc只能采用单点服务，当单机ALlocSvr不可用时，将该机服务的uid段切换到其他AllocSvr机器，这里就需要一个仲裁服务，探测AllocSvr状态，并决定每个 uid 段由哪台 AllocSvr 加载。
- 仲裁/探活：出于可靠性的考虑，仲裁模块并不直接操作 AllocSvr ，而是将加载配置写到 StoreSvr 持久化，然后 AllocSvr 定期访问 StoreSvr 读取最新的加载配置，决定自己的加载状态。
- 租约：为了避免失联AllocSvr提供错误的服务，返回脏数据，AllocSvr需要跟StoreSvr保持租约。
- 1）租约失效：AllocSvr N秒内无法从StoreSvr读取加载配置时，AllocSvr停止服务；
- 2）租约生效：AllocSvr读取到新的加载配置后，立即卸载需要卸载的号段，需要加载的新号段等待N秒后提供服务。
- 以上两点保证了新Alloc肯定在旧Alloc下线之后再提供服务的，但会造成小段时间不可用，由于微信后台逻辑层存在重试机制及异步重试队列，租约失效与切换是小概率事件，可以接受
容灾架构演变
- 1.0时代：全量的 uid 空间均匀分成N个 Section，连续的若干个 Section 组成了一个 Set，每个 Set 都有一主一备两台 AllocSvr
- 好处是逻辑简单开发快，而且客户端更新AllocSvr的路由状态非常容易实现，因为客户端知道每个uid会在Alloc的一主一备中的一台机器进行加载，最多浪费一次请求就可以知道主备的状态。
- 缺点是扩缩容麻烦，客户端需要维护和AllocSvr完全一致的配置文件。另一个隐患是如果一个Set的一主一备都过载，无法用另一个Set的机器进行容灾，虽然可以用一致性哈希，但是还是面临配置变更的麻烦
- 2.0时代：1.0最大问题是客户端需要感知AllocSvr的配置信息，于是把 AllocSvr 的路由状态嵌入到 Client 请求 sequence 的响应包
- seqsvr 所有模块使用了统一的路由表，描述了 uid 号段到 AllocSvr 的全映射。这份路由表由仲裁服务根据 AllocSvr 的服务状态生成，写到 StoreSvr 中，由 AllocSvr 当作租约读出，最后在业务返回包里旁路给 Client 端。
- 这种看似简单的动作，却给整个架构带来了灵活性，比如所有机器都可互为备机，还可以轻松地负载均衡，运维也可大大简化
- 优化：不用每次请求都返回路由表，客户端可维护一份路由表缓存，带有版本号，向Alloc发起请求时带上版本号即可，Alloc判断版本号如果是旧版就在请求附上最新路由表
深度解密美团的分布式ID生成算法
- 美团开源了两种id生成算法，其中segment非常适合IM场景：
- 1）Leaf-segment方案：可生成全局唯一、全局有序的ID；
- 2）Leaf-snowflake方案：可生成全局唯一、局部有序的ID。
- 经过分析，纯粹的snowflake强烈依赖机器时钟，二数据库自增的id也不合适，因为强依赖db且受限于db的单机性能，单机性能可根据Flickr团队Ticket Servers: Distributed Unique Primary Keys on the Cheap进行优化，但仍有db性能问题，且水平扩展受限
Leaf-segment
- 这是基于数据库自增id方案的改进：
- 1）原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用proxy server批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力；（这跟微信的max_seq持久化策略有异曲同工之妙）
- 2）各个业务不同的发号需求用biz_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。
- 优点：易扩展，容灾（号段有缓存）
- 缺点：不随机所以不安全，数据库IO时会造成尖刺，强依赖db
- 双buffer解决IO尖刺：因为在号段耗尽的临界点事需要等待IO完成，可以多设置一个号段buffer，当当前号段快耗尽时，启动另一个线程去获取下一个号段填充第二个号段buffer，以此循环往复
- 该方案可以生成趋势递增的id，且id可计算，但不试用于订单生成场景，因为竞争对手可根据连续两天同一时间下单的订单号推测业务量
Leaf-snowflake
- 基于snowflake的改进，每个leaf-snowflake服务启动后都会连接zookeeper，在leaf_forever父节点上检查自己是否注册，若未注册择创建一个持久顺序节点，取回顺序号作为workerid；若注册则直接取回自己的workerid
- zookeeper可若依赖，每个leaf-snowflake本机文件系统有workerid的缓存
- 解决时钟问题：
- 1）若写过，则用自身系统时间与leaf_forever/${self}节点记录时间做比较，若小于leaf_forever/${self}时间则认为机器时间发生了大步长回拨，服务启动失败并报警；
- 2）若未写过，证明是新服务节点，直接创建持久节点leaf_forever/${self}并写入自身系统时间，接下来综合对比其余Leaf节点的系统时间来判断自身系统时间是否准确，具体做法是取leaf_temporary下的所有临时节点(所有运行中的Leaf-snowflake节点)的服务IP：Port，然后通过RPC请求得到所有节点的系统时间，计算sum(time)/nodeSize；
- 3）若abs( 系统时间-sum(time)/nodeSize ) < 阈值，认为当前系统时间准确，正常启动服务，同时写临时节点leaf_temporary/${self} 维持租约；
- 4）否则认为本机系统时间发生大步长偏移，启动失败并报警；
- 5）每隔一段时间(3s)上报自身系统时间写入leaf_forever/${self}。
- 由于强依赖时钟，对时间的要求比较敏感，在机器工作时NTP同步也会造成秒级别的回退，建议可以直接关闭NTP同步。要么在时钟回拨的时候直接不提供服务直接返回ERROR_CODE，等时钟追上即可。或者做一层重试，然后上报报警系统，更或者是发现有时钟回拨之后自动摘除本身节点并报警。
深度解密滴滴的高性能ID生成器(Tinyid)
- Tinyid是滴滴用Java开发的一款分布式id生成系统，基于数据库号段算法实现。基于美团的leaf-segment扩展而来，支持数据库多主节点模式
- 特点：
- 1）全局唯一的long型ID：即id极限数量是2的64次方；
- 2）趋势递增的id：趋势递增的意思是，id是递增但不一定是连续的（这跟微信的ID生成策略类似）；
- 3）提供 http 和 java-client 方式接入；
- 4）支持批量获取ID；
- 5）支持生成1,3,5,7,9…序列的ID；
- 6）支持多个db的配置。
- 试用场景，只关心id是数字、趋势递增的系统，可容忍不连续，不适用于订单场景，因为id可推算
Tinyid的技术优势
性能方面：
- 1）http方式：访问性能取决于http server的能力，网络传输速度；
- 2）java-client方式：id为本地生成，号段长度(step)越长，qps越大，如果将号段设置足够大，则qps可达1000w+。
可用性方面：
- 1）当db不可用时，因为server有缓存，所以还可以使用一段时间；
- 2）如果配置了多个db，则只要有1个db存活，则服务可用；
- 3）使用tiny-client时，只要server有一台存活，则理论上server全挂，因为client有缓存，也可以继续使用一段时间。
Tinyid的技术原理详解
- 每次获取id会读db，浪费性能，可以一次性从db获取一个号段加载到tinyid-server的内存中
- 缺点：如果tiny-server重启，号段丢失，就浪费了；db是单点；http每次获取都要网络开销
- 优化方法：
- 双号段缓存，跟美团的leaf思想一致
- 多db支持，每台db生成的号段分隔开，比如两台db就是一个只生成偶数一个只生成奇数，这个与Flickr的思想一致
- 增加tinyid-client：没有什么是缓存解决不了的，client可以构建本地的双号段与id生成
PS：感觉还是美团的leaf强大一点
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 一知半解！