|
crm志字辈小蚂蚁 技术大厂机会，前后端/测试可投
一. 业界常用的几种分布式ID方案主要是那么几种 ： 基于雪花算法：通常基于雪花 + 自身的系统特性来进行一定的改造 基于分布式锁 + 号段 + 雪花算法： 美团的 Leaf 就是采用这种方式 ，会更适用于并发高的场景 基于数据库的分布式ID： 不同于老一代的数据库，现在很多新一代分布式数据库都带有ID生成的功能
除了以上这几种常见的方式 , 还有一些不太常见或者存在一定缺陷的分布式ID方式 ：
UUID：长度较长 ，性能较差， 并没有实现系统间的可见和通信，所以还是存在重复的可能 基于组件的分布式ID： 基于外部组件来实现通信 / 上锁 / 数据生成 常见的包括 Redis , 或者 MongoDB 本身的 ObjectId 生成方式 问题在于并发不高 ，而且代码可能会很复杂，需要控制锁的粒度
二. 浅学一下大厂的实现方案 Leaf-snowflake ： 即常规的雪花算法，但是在雪花的基础上做了一些变动 通过 Zookeeper 来配置 WorkerId ，最大的特性在于WorkerID 的可重用 本机系统上缓存 WorkerID 文件 启动时会校验时钟时间，时钟要大于之前机器时间（会和其他的机器时间做对比）
![]() 3.2 雪花 ： 百度的uid-generator **ID 格式 **： sign(1bit) ： 固定1bit符号标识，即生成的UID为正数 delta seconds (28 bits) ： 当前时间，相对于时间基点"2016-05-20"的增量值 时间不依赖于系统时间，而是基于 AtomicLong 进行自增 带来的后果就是时间可能会和实际时间偏移 存在借用未来时间的现象
worker id (22 bits) ： 机器id，最多可支持约420w次机器启动 每次启动时初始化，数据库自增实现 可以自定义 WorkerId 位数和初始化策略 （这样的话就可以适配不同的集群范围） sequence (13 bits) ：每秒下的并发序列，13 bits可支持每秒8192个并发 RingBuffer 的使用，不实时计算并发ID，预生成多个分布式ID进行保存
❓总结： 可以看到 ， 百度认为机器ID的位数需要得更多,可能是由于服务器多，启动比较频繁导致 对于单机而言 ，每秒每条业务线 8000 并发已经很高了
❓精华 ： sequence ID 的生成 一般简单的实现方式是通过加锁 synchronized 或者通过原子变量实现一个单机的自增 百度采用了RingBuffer的形式 ，来实现 sequence 的生成 总结一下 ，在我看来主要是 ：预生成 + 预占 + 消费 百度的精髓在于 RingBuffer 实现的环形数组，实现了并发位ID的生产消费关系，在这个数组中存在两个指针 ： Tail指针： 当前生产的 ID 序列号 Cursor 指针： 当前消费的 ID 序列号 CachedUidGenerator采用了双RingBuffer，Uid-RingBuffer用于存储Uid、Flag-RingBuffer用于存储Uid状态(是否可填充、是否可消费) 由于RingBuffer是一个环形，所以要保证生产不能超过消费（PutRejectPolicy策略），还要避免消费追上了生产 （TakeRejectPolicy） 同时百度案例里面也提到了伪共享的问题，在 RingBuffer 中连续分配的数组可以通过 CPU Cache 最大程度的提升性能。 但是由于多个线程对同一缓存行竞争，会带来缓存行的失效和写前的缓存行校验，就带来了额外的性能损耗。
❓ 问题一 ： 伪共享是什么意思 ？ 不同核心（或处理器）共享同一缓存行而导致的性能问题 。 当多个核心同时修改或读取同一缓存行中的不同数据时，由于缓存的一致性协议，这个缓存行会被加载到多个核心的缓存中。 所以当多线程处理不相干的变量时会相互影响 ， 造成伪共享拖慢速度。 （缓存竞争 / 无效化等）
❓ 问题二 ：怎么解决伪共享 ？ 核心点 ：CPU 是以缓存行的形式进行读取的 基于这个概念 ，比较常见的解决方式是通过特殊的结构，或者通过填充缓存行的方式 ，确保不同的数据项被存储在不同的缓存行中，从而避免不必要的缓存行竞争
❓ 问题三：百度 UID Generator 具体解决思路 ？ RingBuffer填充时机 程序启动时，将RingBuffer填充满，缓存着8192个id 在调用getUID()获取id时，检测到RingBuffer中的剩余id个数小于总个数的50%，将RingBuffer填充满，使其缓存8192个id 定时填充 CacheLine补齐 : 通过 缓存行填充 ， 避免tail和cursor落到同一个缓存行上 ❓ 问题四：借用未来时间？？ ？ 简单点说 ，就是由于每秒只有 8192 个空位 ，所以当超过这个空位的时候 ，会借用 delta seconds 未来的位置，也就是借用未来时间。 也就是使用了未来的时间来生成id，【最多】可支持约8.7年
3.3 号段 ：美团 Leaf-segment @Leaf——美团点评分布式ID生成系统
Leaf-segment ： 这种方案的核心在于每次从DB中拿取一个号段，那么锁的竞争主要在拿号段的过程中 为了解决这种问题，美团采用第一个号段使用百分之10的时候就提前拿后面一个号段 缺点在于号段是可以推导和预测的，比如预测销量。 所以很多现实里面会进行跳段，跳过多个数到下一个数。
3.4 号段 ：滴滴Tinyid Tinyid扩展了leaf-segment算法，支持了多db(master)，同时提供了java-client(sdk)使id生成本地化，获得了更好的性能与可用性 总结和思考 分布式ID方案真的不难，业界常用的就是这些。 这些概念点也基本上写烂了，但是执意发出来的原因是想看过这些之后得出一些自己的理解。
想法心得 ： 雪花算法 是 鼻祖 ，其他的算法或多或少在这个基础上进行了改造。充分说明了这个方案的优秀。 几大厂商里面 ，使用难度方面美团和百度的都比较简单 ，引入 SDK 通常就能实现 ，最多需要部署时间服务器，上手难度较低。 滴滴的方案需要部署多套服务器 ，还要引入 client 消费 ，依赖性比较强了。 技术深度最深的应该是 百度的 uid-generator ， 设计的思路感悟很多。 滴滴的 Tinyid 走出了另外一条路线，没有局限于雪花的思路。
三. 阶段总结 ： | 
楼主
标题置顶
标题高亮
