Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

分布式系统中唯一 ID 的生成

Posted on 06/30/201706/23/2019 by 四火

其实老早就像写一点这个话题。几乎我见过的所有大型系统中,都需要一个唯一 ID 的生成逻辑。别看小小的 ID,需求和场景还挺多:

  • 这个 ID 多数为数字,但有时候是数字字母的组合;
  • 可能随机,也可能要求随时间严格递增;
  • 有时 ID 的长度和组成并不重要,有时候却要求它严格遵循规则,或者考虑可读性而要求长度越短越好;
  • 某些系统要求 ID 可以预期,某些系统却要求 ID 随机性强,无法猜测(例如避免爬虫等等原因)。

独立的生成服务

比如数据库。最常见的一种,也是应用最多的一种,就是利用数据库的自增长序列。比如 Oracle 中的 sequence 的 nextVal。有多台 application 的 host,但是只有一个数据库。本质上这是耍了个小赖皮,把某分布式系统唯一 ID 的生成逻辑寄托到一个特定的数据库上,于是分布式系统存在中心节点了。

这个方法简单,而且可以严格保证单调递增。不过中心化带来的问题众所周知,比如单点故障,比如性能方面的扩展上限。有一种 workaround,正如同数据库有主从库一样,可以给不同的数据库设置 sequence 范围(比如一个是从 1~100000000,另一个是从 100000001 到 200000000),或者是设置相同的步长(比如一个是 1、3、5、7……另一个是 2、4、6、8……),但是互相不重复,从而保证唯一性。不过这样不同 sequence 生成节点整体内的 ID 递增性就丢失了。

其它的生成服务也有很多,很多系统中设计的 ticket server 本质上也就是扮演这样一个角色,特点是这个 ID 生成服务系统必须独立于现有母系统(客户系统)。但是注意,单点 service 不代表一定会存在单点故障,单点 service 一样可以 HA。因为这个 service 也可以是去中心化的。

既然说到这样的 service,开源 ID 生成算法上,最最有名的是 Twitter 的 snowflake,它正是重点考虑到 high scale 而设计的。64bit 长度以下,无需节点间复杂的协作,ID 有序。每一条 snowflake 生成的 ID 都包含三个部分:timestamp、节点编号,以及一个自增的子序列号。额外地,需要提及其中两个问题的处理:

  • timestamp 冲突:timestamp 本身是毫秒级的,如果出现冲突,那么其中的自增子序列号会自动+1 从而保证生成的 ID 不会和上一条的冲突。
  • 节点编号的生成:这个其实是从 Zookeeper 去获取的,也是被诟病说它不够去中心化的原因之一(一个改进方案是 Boundary Flake,不需要依赖于这个获取逻辑)。

本地生成器

这个也很常见,局限性也非常明显。通常必须满足这样的要求:在不同的 host(分布式节点)之间没有关系保证(比如递增性)。

比如我见过这样的逻辑,用 host 的唯一编号来作前缀(保证环境中节点编号的唯一性即可),毫秒数来生成 ID 的主体部分。看似简单,一样可以解决唯一 ID 的问题。当然它的局限性也很多,如果使用当前毫秒数,无法对于不同 host 生成的 ID 进行先后比较(因为无法确保时间是严格一致的);而且只能一个毫秒最多只能生成一个 ID,如果要生成两个就会产生冲突。这两个问题当中,对于后者有一个改进方案,就是使用一个 AtomicLong 来保证冲突情况下的自增序列。

既然提到了 AtomicLong,有一些开源项目做到了对 AtomicLong 的分布式实现。比如 Redisson(基于 Redis)。但这不属于这里讨论的本地生成器范畴。

还有一种典型是 UUID。UUID 的全称叫做 universally unique identifier,Java 中一个 UUID 代表一个 128bit 的数。在分布式系统中,它比前面说的方案有更多优势,比如长度一致,比如没有一个毫秒内最多只能生成一个的要求。但是,尽管可以认为它是唯一的,基于随机数产生的 UUID 冲突却是理论上可能存在的。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

×Scan to share with WeChat

你可能也喜欢看:

  1. Notes: Hadoop-based open source projects
  2. 2013 年特别回顾
  3. Grails 引发的中文乱码问题
  4. 三次性能优化经历
  5. 关于 RESTful 不足的思考

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Python Spark 互联网 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 程序员 管理 系统设计 缓存 编码 编程范型 英语 西雅图 设计 评审 问题 面试 项目

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Big Data and Machine Learning (5)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • + 1.943624 BTC.NEXT - https://graph.org/Ticket--58146-05-02?hs=9a9c6f8dfe3cdbe0074006e3e640b19b& on 所有文章
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
  • Anonymous on 我裸辞了
  • Dylan on 我裸辞了
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme