分布式ID生成方案
IM消息ID技术专题(一)：微信的海量IM聊天消息序列号生成实践（算法原理篇）-IM开发/专项技术区 - 即时通讯开发者社区! (52im.net)
常见的策略
- 1）UUID：这种方法简单直观，可以很好的保证唯一性，但对于技术洁癖的人来说ID长度会有点长，而且是无序的；
2）使用时间戳长整数：这个最偷懒，用在吞吐量不大的场景下，凑活也能用，但存在重复的风险，也无法保证分布式下的唯一性；
3）使用twitter开源的snowflake算法：在分布式高并发的情况下，这也是个不错的选择；
4）按用户使用独立的ID生成空间生成顺序的ID：比如微信的消息序列号生成策略就很不错。
UUID会重复吗？
- UUID Version 1：基于时间的UUID
基于时间的UUID通过计算当前时间戳、随机数和机器MAC地址得到。由于在算法中使用了MAC地址，这个版本的UUID可以保证在全球范围的唯一性。但与此同时，使用MAC地址会带来安全性问题，这就是这个版本UUID受到批评的地方。如果应用只是在局域网中使用，也可以使用退化的算法，以IP地址来代替MAC地址（不考虑手动更改MAC地址的情况）。- UUID Version 2：DCE安全的UUID
DCE（Distributed Computing Environment）安全的UUID，和基于时间的UUID算法相同，但会把时间戳的前4位置换为POSIX的UID或GID。这个版本的UUID在实际中较少用到。- UUID Version 3：基于名字的UUID（MD5）
基于名字的UUID通过计算名字和名字空间的MD5散列值得到。这个版本的UUID保证了：相同命名空间中不同名字生成的UUID的唯一性；不同命名空间的UUID的唯一性；相同名字空间中相同名字的UUID重复生成是相同的。- UUID Version 4：随机UUID
根据随机数，或者伪随机数生成UUID。这种UUID产生重复的概率是可以计算出来的，但随机的东西就像是买彩票：你指望它发财是不可能的，但狗屎运通常会在不经意中到来。- UUID Version 5：基于名字的UUID（SHA1）
和版本3的UUID算法类似，只是散列值计算使用SHA1（Secure Hash Algorithm 1）算法。
- Version 1.2 适合应用于分布式计算环境下，具有高度唯一性
- Version 3.5 适合于一定范围内名字唯一，且有需要生成重复UUID的场景下
- Version 4 最为简单和方便，适合数据量不是特别大的场景下，Java默认的uuid工具便是此种
融云设计思路
融云消息数据的唯一ID长度采用80Bit
每 5 个 Bit ，进行一次 32 进制编码，转换为一个字符，字符取值范围是：数字 “2 ~ 9 ”和字母“A ~ B”。其中，已经去掉容易造成肉眼混淆的数字 0 和 1 （余下可用的数字就是8个了），及字母 O 和 I（余下可用的字母就是24个了），那么总可用字符就是32个（刚好可按32进制进行编码）。
这样，80bit可以转换为16个字符，在加上3个分隔符-，将16个字符分为4组，最终得到一个19字符的唯一ID，形如：“ BD8U-FCOJ-LDC5-L789 ”。这样设计，既可以保证生成ID是有序的，也能方便阅读。
如上图所示，80Bit被分为4段
- 第一段42bit：用于存放时间戳，最长可表示到2190年，足够开发者当前使用了。时间戳数据放在高位，可以保证生成的唯一ID是时间有序的，这是消息ID必须要满足的条件。
- 第二段12Bit：用于存放自旋ID。我们知道时间戳的精度是到毫秒的，对于一套亿级IM系统来说，同一毫秒内产生多条消息太正常不过了，这个自旋ID就是在落到同一毫秒内的消息进行自增编号。12bit则意味着，同一毫秒内，单台主机最多可标识4096（2的十次方）条消息。
- 第三段4Bit：用于标识会话类型。4 Bit ，最多可以标识 16 中会话，足够涵盖单聊、群聊、系统消息、聊天室、客服及公众号等常用会话类型。
- 第四段22Bit：会画ID。如群聊中的群ID，聊天室中的聊天室ID等。与第三段会话类型组合在一起，可以标识一个唯一的会话。其他的一些ID生成算法，会预留俩段，分别来标识数据中心编号和主机编号（如snowFlake算法），我们并没有这样做，而是将这俩段用来标识会话。这样，ID生成可以直接融入到业务中，而且不必关心服务所在的主机，做到无状态扩容。
微信ID思路
IM消息ID技术专题(一)：微信的海量IM聊天消息序列号生成实践（算法原理篇）-IM开发/专项技术区 - 即时通讯开发者社区! (52im.net)
引言
微信在立项之初，就确立了利用数据版本号（也就是消息序列号），实现终端后台的数据增量同步机制，确保发消息时可靠送达对方对方手机。
而在这同步机制的背后，需要一个高可用、高可靠的消息序列号生成器来产生同步数据用的版本号（注：因为序列号天生的递增特性，完全可以当版本号来使用，但又不仅限于版本号的用途）。这个消息序列号生成器我们微信内部称之为 seqsvr ，目前已经发展为一个每天万亿级调用的重量级系统，其中每次申请序列号平时调用耗时1ms，99.9%的调用耗时小于3ms，服务部署于数百台4核 CPU 服务器上。
技术思路
微信服务器端为每一份需要与客户端同步的数据（例如聊天消息）都会赋予一个唯一的、递增的序列号（后文称为sequence），作为这份数据的版本号（这是利用了序列号递增的特性）。在客户端与服务端同步时候，客户端会带上已经同步下去数据的最大版本号，后台会根据客户端最大版本号与服务器端最大版本号，计算出需要同步的增量数据，返回给客户端。这样不仅保证了客户端与服务端的数据同步的可靠性，同时也大幅减少了
这里不用乐观锁机制来生成版本号，而是使用了一个独立的seqsvr来处理序列号操作。
- 递增的64位整形变量
- 每个用户都有自己独立的sequence空间
这里用了每个用户独立的64为sequence的体系，而不是一个全局的64位（或更高维）sequence，很大原因是全局唯一的sequence会有非常严重的申请互斥问题，不容易去实现一个高性能可靠架构。对微信业务来说，每个用户独立的64位sequence空间已经满足业务需求。
目前sequence用在终端与后台的数据同步外，同时也广泛用于微信后台逻辑层的基础数据一致性cache中，大幅减少逻辑层堆存储层的访问。虽然一个用于终端--后台同步数控，一个用于后台cache一致性保证，场景大不相同。
但我们仔细分析就会发现，两个场景都是利用 sequence 可靠递增的性质来实现数据的一致性保证，这就要求我们的 seqsvr 保证分配出去的 sequence 是稳定递增的，一旦出现回退必然导致各种数据错乱、消息消失；另外，这两个场景都非常普遍，我们在使用微信的时候会不知不觉地对应到这两个场景：小明给小红发消息、小红拉黑小明、小明发一条失恋状态的朋友圈，一次简单的分手背后可能申请了无数次 sequence。
微信目前拥有数亿的活跃用户，每时每刻都会有海量 sequence 申请，这对 seqsvr 的设计也是个极大的挑战。那么，既要 sequence 可靠递增，又要能顶住海量的访问，要如何设计 seqsvr 的架构？我们先从 seqsvr 的架构原型说起。
具体技术架构原型
不考虑 seqsvr 的具体架构的话，它应该是一个巨大的64位数组，而我们每一个微信用户，都在这个大数组里独占一格8 bytes 的空间，这个格子就放着用户已经分配出去的最后一个 sequence：cur_seq。每个用户来申请sequence的时候，只需要将用户的cur_seq+=1，保存回数组，并返回给用户。
预分配中间层
任何一件看起来很简单的事，在海量的访问量下都会变得不简单。前文提到，seqsvr 需要保证分配出去的sequence 递增（数据可靠），还需要满足海量的访问量（每天接近万亿级别的访问）。满足数据可靠的话，我们很容易想到把数据持久化到硬盘，但是按照目前每秒千万级的访问量（~10^7 QPS），基本没有任何硬盘系统能扛住。
后台架构设计很多时候是一门关于权衡的哲学，针对不同的场景去考虑能不能降低某方面的要求，以换取其它方面的提升。仔细考虑我们的需求。
我们只要求递增，并没有要求连续，也就是说出现一大段跳跃是允许的（例如分配出的sequence序列：1,2,3,10,100,101）。
于是我们实现了一个简单而又优雅的策略。
- 内存中存储最近一个分配出去的sequence：cur_seq，以及分配上限：max_seq
- 分配sequence时将cur_seq++，同时与分配上限max_seq比较：如果cur_seq>max_seq，将分配上限提升一个步长max_seq+=step，并持久化max_seq
- 重启时，读出持久化的max_seq，赋值给，cur_seq。
▲ 图2：小明、小红、小白都各自申请了一个sequence，但只有小白的max_seq增加了步长100
这样通过增加一个预分配sequence的中间层，保证sequence不会退的前提下，大幅提升了分配sequence的性能。十几种每次提升步长为10000，那么持久化的硬盘IO次数从之前~10^7 QPS降低到~10^3 QPS，处于可接受范围。在正常运作时分配出去的sequence是顺序递增的，只有在机器重启后，第一次分配的 sequence 会产生一个比较大的跳跃，跳跃大小取决于步长大小。
分号段共享存储
请求带来的硬盘IO问题解决了，可以支持服务平稳运行，但该模型还存在一些问题：重启时需要读取大量的max_seq加载到内存中。
我们可以简单计算下，以目前 uid（用户唯一ID）上限2^32个、一个 max_seq 8bytes 的空间，数据大小一共为32GB，从硬盘加载需要不少时间。另一方面，出于数据可靠性的考虑，必然需要一个可靠存储系统来保存max_seq数据，重启时通过网络从该可靠存储系统加载数据。如果max_seq数据过大的话，会导致重启时在数据传输花费大量时间，造成一段时间不可服务。
为了解决这个问题，我们引入号段Section的概念，uid相邻的一段用户属于一个号段，而同个号段内的用户共享一个max_seq，这样答复减少了max_seq数据的大小，同时降低了IO次数。
▲ 图3：小明、小红、小白属于同个Section，他们共用一个max_seq。在每个人都申请一个sequence的时候，只有小白突破了max_seq上限，需要更新max_seq并持久化
目前 seqsvr 一个 Section 包含10万个 uid，max_seq 数据只有300+KB，为我们实现从可靠存储系统读取max_seq 数据重启打下基础。
工程实现
工厂实现在上面俩个策略上做了一些调整，主要是出于数据可靠性以及灾难隔离考虑：
- 把存储层和缓存中间层分成俩个模块StoreSvr以及AllocSvr，StoreSvr为了存储利用了多级NRW策略来保证持久化后不丢失，AllocSvr则是缓存中间层，部署于多台机器，每台AllocSvr负责若干号段的sequence分配，分摊海量的sequnce申请请求。
- 整个系统又按uid范围进行分Set，每个Set都是一个完整的、堵路的Store+AllocSvr系统。分Set设计目的是为了做容灾隔离，一个Set出现故障只会影响该Set内的用户，而不会影响到其它用户。
