OSC 第 94 期高手问答 —— 分布式 ID 生成策略

叶秀兰 发布于 2015/10/19 16:57
阅读 10K+
收藏 54

OSCHINA 本期高手问答( 10月20日- 10月26日) 我们请来了 @Burn1ng1ce 为大家解答关于 分布式 ID 生成策略 方面的问题。

廖雄杰,@Burn1ng1ce ,现在担任听云研发副总裁、架构师,是资深 Java 工程师,致力于应用性能优化及流式数据处理,对构建高性能 Java 应用和架构有着深入研究。当前负责听云平台后端的架构,包括核心架构的设计,流式数据处理,后端消息系统等。曾担任 QCon 等多个技术大会讲师。

分布式唯一 ID 的生成在分布式架构下很常见的问题,单纯从唯一 ID 生成的角度考虑只需要一些简单的机制就能实现,twitter snowflake 就是一个足够简单高性能的实现。

今 天的主题除了讨论分布式架构下唯一ID的实现,也会关注一些扩展的场景,例如,海量对象按值去重生成ID并持久化,举个实际的例子,很多系统需要给每个 URL分配一个唯一ID,简单的方式是对持久化的URL做唯一索引,仅对新URL生成新ID,当数据量达到亿级甚至更多的时候,如何高效处理存储和检索? 如果对象不止一个属性,并且可能随需求增加新的属性,如果处理数据兼容?这些都是值得讨论的问题。

为了鼓励踊跃提问,@听云APM 会在问答结束后从提问者中抽取 10 名幸运会员赠予听云抱枕一个。

OSChina 高手问答一贯的风格,不欢迎任何与主题无关的讨论和喷子。

下面欢迎大家就 分布式 ID 生成策略 方面或者跟 Java 相关的问题向 @Burn1ng1ce 提问,请直接回帖提问。

加载中
0
听云APM
听云APM

感谢问答期间小伙伴们的捧场~

以下10位同学,请将您的姓名,地址,电话私信@听云APM ,听云抱枕为您送上。

@darkmoon13 @宇智波唐嫣 @西夏一品堂 @CodingKu @仪山湖 @chencliff @小树鹿鸣 @神码都是浮云 @王大麻烦 @无锡IT招聘

聊了这么多页,欢迎大家来www.tingyun.com部署使用听云Server for Java探针呦!

听云Server/听云App 基础版,面向非公司行为的开发者,永久免费,欢迎来玩

chencliff
chencliff
被at了,第一次在OSC中奖。。。
王大麻烦
王大麻烦
我也被at了,好幸福
noday
noday
回复 @叶秀兰 : 听到有人@我
4
d
darkmoon13

@Burn1ng1ce :

您好,我们在项目中也遇到了分布式唯一ID的要求,一开始我们使用分段自增ID,但是随着ID增多,分的表和服务器越来越多,不得不另外维护一张表进行索引。而且这种方法不灵活,一旦超出预先分段的max就进行不下去了。后来也用过以毫秒值作为唯一ID,但是确实有不唯一的可能性。现在我们使用了GUID,虽然保证了为唯一性,但是分布式查询的效率就降低了,因为GUID的不连贯性,很难组织索引。

最后我们采用了部分GUID+时间戳的ID方式,可以大大提高索引率,并且能保证唯一性,至于表达不够友好以及占用位数过多的问题暂时忽略了。

虽然能解决我们目前的问题,但是我不认为这是一种优秀的方法,或者说,我不知道什么才算是优秀的方法。

我想请教的问题就是,在占用、唯一、索引效率、友好、等等方面如何取舍,是否有评判的一个标准呢?以及在我们目前的基础上,有没有更好的改进方式呢?

望不吝赐教,谢谢啦。

3
西夏一品堂
西夏一品堂
@Burn1ng1ce 你好,请问自增的ID,UUID各自的优劣和实用场景
1
西夏一品堂
西夏一品堂
@Burn1ng1ce 假设我们自己另起一个服务,用来生成唯一ID,其他各个子系统都来这里获取ID,请问如何保证,生成速度快、无重复、长度尽可能短等问题
1
yzbty23
yzbty23
@Burn1ng1ce :先推荐你看 Instagram 的这篇 [0],他们要求生成 ID 尽量短而且可按生成时间排序,里面提到了好几种不同的 ID 生成方法的优缺点,比如:
  • 在应用里面直接生成 UUID,优点是独立生成、性能好,缺点是生成的 ID 比较长。
  • 单独运行一套 ID 生成服务,比如 Twitter 的 Snowflake [1],优点是可以生成比较短而且可以排序的 ID,并且分布式系统不容易挂,缺点是维护麻烦。
  • 依赖数据库自增,比如 Flickr [2],优点是可以重用现有的计数,缺点是数据库写性能可能会是瓶颈,并且如果使用多个数据库,如何保证生成的 ID 可排序是个问题。
Instagram 然后根据自己的需要定制了基于 PostgreSQL 数据库的预分片 (pre-sharding) ID 生成机制。核心思想是预先分配足量的逻辑片 (logical shard),然后将大量的逻辑片映射到少量的物理片 (physical shard),最终依赖数据库的自增特性保证 ID 的唯一性。


注意以上提到的几套机制生成的都是 64 位的整数 ID,主要是给程序用来标记新建的数据对象用的。而原题目提到的用户 ID,我理解除了给程序用外,更重要的是要给人看。给人看的 ID 需要更加简短,因为对机器来说,64 位已经足够短了,而显然人是无法快速记忆 8744239352046571174 这样一长串数字的。所以生成给人看的 ID 需要根据应用场景尽可能短,比如绝大部分时候用户数量不会过亿,那么生成的 ID 的十进制表达最好不要超过 8 位数。

题目中要求的另外一点『不能直接看出规则』也是需要特别考虑的。对于中国互联网这样没有任何道德底限的地方来说尤为重要。原因大家都懂,如果 ID 是连续的,扒取内容的工作就非常简单了,直接按顺序下载指定的 URL 范围即可,爬虫都不用写了。所以对于公开 ID,不连续、无规则是基本要求。

以上两点和前述 Instagram 文章提到的几种 ID 生成需求有本质不同。结合知乎的用例,我把题目提到的这种 ID 需求特性概括为九个字:尽量短、无规则、无顺序。对于这样的应用场景,个人认为写一套单独的 ID 生成服务是比较好的办法。这个功能很简单,依赖过多的外部组件(如数据库)有点得不偿失。

目前我正在写的 ID 生成服务的基本思路是这样的:
  • ID 生成服务管理多个不同名字的 ID 池 (pool)。
  • 每种不同类型的 ID 属于不同的 ID 池,比如知乎会有用户 ID 池、问题 ID 池、回答 ID 池等等。
  • 每个 ID 池由多个定长 ID 块 (block) 构成。
  • 每个 ID 块包含一段连续的 ID,比如第一块是从 0~1023,第二块从 1024~2047,以此类推。
  • 每个 ID 块并不完全分配,而是按照一个给定的填充率 (fill ratio) 随机选择来分配,比如假设填充率是 50%,那么每个 ID 块中只有大约一半的 ID 会被分配。也就是说每个 ID 块是有随机空洞的。
  • 如果某个 ID 块中可用 ID 被分配完毕,服务会自动生成下一个新的 ID 块,并按照填充率去掉不可用 ID。生成新的 ID 块时需要记录下最后一个 ID 块的起始 ID。
  • 已经分配过的 ID 会写入一个 append-only 日志。新的 ID 块生成时会创建一个新的 append-only 日志(因为旧的已经不需要了)。
  • 服务重新启动的时候先拿到最后一个 ID 块的起始 ID,再读取 append-only 日志将已经分配过的 ID 剔除,再剔除掉部分未分配的 ID 以维持填充率。
  • 客户端发送请求访问 ID 生成服务。服务端返回 ID 做为回复。

优点是逻辑简单,生成的 ID 短小,单个进程维护起来方便。缺点是知道生成的 ID 的上限(可以用很大的块部分解决这个问题)。大概这样。欢迎讨论。

[0]: http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram
[1]: https://github.com/twitter/snowflake
[2]: http://code.flickr.com/blog/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
0
noday
noday
@Burn1ng1ce :讲解一下snowflake ;听云在此方面是如何实践的?
0
木川瓦兹
木川瓦兹
@Burn1ng1ce :我了解了一下snowflake ,应该是时间、机器相关的一组数据,也就是说这串id在单机上是按序的,但是分布式多台机器上不是按序增长的,请问有没有可以完成分布式部署后,生成唯一ID服务还是按序增长的呢?
0
noday
noday
@Burn1ng1ce :怎样减少id长度,64进制或者更多,那些字符适合用在id中
0
小树鹿鸣
小树鹿鸣

@Burn1ng1ce :

您好,我现在这边也有参考twitter snowflake思想去做,定义为字符串类型,机器码(3位)+时间戳 + 自增长序列(4)位,当毫秒并发超过9999后,时间戳毫秒+1,序列从0开始计时。机器码是在通过配置的,可以是100,101,这样设计合理不?

0
梦朝思夕
梦朝思夕
如果需要有序自增id如果实现
返回顶部
顶部