【295期】面试官问：如何选择合适的分布式 ID 生成方案？

点击上方“Java精选”，选择“设为星标”

别问别人为什么，多问自己凭什么！

下方有惊喜，留言必回，有问必答！

每一天进步一点点，是成功的开始...

在分布式系统中，经常需要用到全局唯一ID发生器，标识需要存储的数据。我们需要什么样的ID生成器？

ID生成器除了是数据的唯一标识以外，一般需要在系统中承担更多的责任，概括起来有以下几点。

分布式系统使用唯一的ID生成器，会有非常严重的申请互斥问题。互斥加锁意味着成本和性能的下降，不容易去实现一个高性能高可靠的架构。在业务系统中，往往也不需要全局唯一的ID。

比如在通讯系统里，聊天消息不需要全局唯一，标识一条用户发出的消息的ID，只要保证用户唯一性即可。因为消息本身归属于某一用户，因此用户唯一已经隐含了“全局唯一ID （ = 用户ID + 消息ID ）”。

时间是天然唯一的，因此也是很多设计的选择。但对于一个8Byte的 ID 而言，时间并没有那么多。你如果精确到秒级别，三十年都要使用30bit，到毫秒级则要再增加10bit，你也只剩下20bit 可以做其他事情了。每秒一个或者每毫秒一个ID明显是不够的，刚才说到还有20bit 可以做其他事情，就包括一个SequenceID。

那时间用秒还是毫秒呢？其实不用毫秒的时候就可以把空出来的10bit 送给 Sequence，但整个ID 的精度就下降了。峰值速度是更现实的考虑。Sequence 的空间决定了峰值的速度，而峰值也就意味着持续的时间不会太久。这方面，每秒100万比每毫秒1000限制更小。

有序：“粗略有序” vs “精确有序”？

首先，如果要达到精确的有序，就要对 Sequence 进行并发控制，性能上肯定会打折。其次，同一时间只能生成一个ID，意味着同一时间只有一个ID生成服务实例可以提供服务，精确有序还会面临容灾问题。

另外一个选择就是，在这个秒的级别上不再保证顺序，而整个 ID 则只保证时间上的有序。后一秒的 ID肯定比前一秒的大，但同一秒内可能后取的ID比前面的号小。粗略有序在使用时非常关键，业务上可接受才能成为候选方案。

看下业界如何设计ID发生器。

SnowFlake

41bit留给毫秒时间，10bit给机器 (MachineID) ，剩下12bit留给Sequence。另外，关于各类场景面试题，公众号Java精选，回复java面试，获取面试题资料，支持在线随时随地刷题。

Weibo

微博 30bit的秒级时间，4bit来区分IDC，2bit 区分业务，15bit 给 Sequence。理论上限3.2w/s的速度。由于当前发号服务是机房中心式的，1bit 来区分热备。最终，没有用满64bit。

Flicker

Flicker 在解决全局ID生成方案里就采用了MySQL自增长ID的机制（auto_increment + replace into + MyISAM）。在我们的应用端需要做下面这两个操作，在一个事务会话里提交：

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();


Flicker启用了两台数据库服务器生成ID来容灾，通过区分auto_increment的起始值和步长来生成奇偶数的ID。

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2


微信

微信使用MySQL持久化未分配的最大ID，每次从DB取一段放到内存分配给调用方。微信的ID生成是严格递增的，意味着同一时间只能有一台机器提供服务，因此使用仲裁服务+租约机制+路由表，进行容灾。

考虑到Feeds业务的特性，并不需要精确有序，因此我们使用snowflake算法进行ID生成。使用39 (毫秒)+ 5（机器） + 9（seq），来保证ID作为Redis的score不会溢出。

这样的ID生成器可以使用大约17年，对于一款产品的生命周期来说已经足够使用。

针对时间回拨产生的问题，因为发生的频率极小，所以只需要简单判断，如果不满足 currentMillis <= lastTime，则返回错误即可。

作者：有疑说

https://www.cyningsun.com/12-26-2018/id-generator.html

公众号“Java精选”所发表内容注明来源的，版权归原出处所有（无法查证版权的或者未注明出处的均来自网络，系转载，转载的目的在于传递更多信息，版权属于原作者。如有侵权，请联系，笔者会第一时间删除处理！

------ THE END ------

精品资料，超赞福利！

3000+ 道面试题在线刷，最新、最全 Java 面试题！

期往精选  点击标题可跳转

 技术交流群！

最近有很多人问，有没有读者交流群！想知道如何加入？方式很简单，兴趣相投的朋友，只需要点击下方卡片，回复“加群”，即可无套路入交流群！

文章有帮助的话，在看，转发吧！