分布式系统中, 怎么样生成全局唯一的 ID

标签： 分布 系统 怎么样 | 发表时间：2016-03-26 08:39 | 作者：
出处：http://m635674608.iteye.com

一, 问题描述

 

在分布式系统存在多个 Shard 的场景中, 同时在各个 Shard 插入数据时, 怎么给这些数据生成全局的 unique ID?

 

在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现.

 

但在一个存在多个 Shards 的分布式系统 (例如多个 MySQL 实例组成一个集群, 在这个集群中插入数据), 这个问题会变得复杂, 所生成的全局的 unique ID 要满足以下需求:

 

  1. 保证生成的 ID 全局唯一
  2. 今后数据在多个 Shards 之间迁移不会受到 ID 生成方式的限制
  3. 生成的 ID 中最好能带上时间信息, 例如 ID 的前 k 位是 Timestamp, 这样能够直接通过对 ID 的前 k 位的排序来对数据按时间排序
  4. 生成的 ID 最好不大于 64 bits
  5. 生成 ID 的速度有要求. 例如, 在一个高吞吐量的场景中, 需要每秒生成几万个 ID (Twitter 最新的峰值到达了 143,199 Tweets/s, 也就是 10万+/秒)
  6. 整个服务最好没有单点

 

如果没有上面这些限制, 问题会相对简单, 例如:

 

  1. 直接利用 UUID.randomUUID() 接口来生成 unique ID (http://www.ietf.org/rfc/rfc4122.txt). 但这个方案生成的 ID 有 128 bits, 另外, 生成的 ID 中也没有带 Timestamp
  2. 利用一个中心服务器来统一生成 unique ID. 但这种方案可能存在单点问题; 另外, 要支持高吞吐率的系统, 这个方案还要做很多改进工作 (例如, 每次从中心服务器批量获取一批 IDs, 提升 ID 产生的吞吐率)
  3. Flickr 的做法 (http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/). 但他这个方案 ID 中没有带 Timestamp, 生成的 ID 不能按时间排序

 

在要满足前面 6 点要求的场景中, 怎么来生成全局 unique ID 呢?

 

Twitter 的 Snowflake 是一种比较好的做法. 下面主要介绍 Twitter Snowflake, 以及它的变种

 

二, Twitter Snowflake

 

https://github.com/twitter/snowflake

 

Snowflake 生成的 unique ID 的组成 (由高位到低位):

 

  • 41 bits: Timestamp (毫秒级)
  • 10 bits: 节点 ID (datacenter ID 5 bits + worker ID 5 bits)
  • 12 bits: sequence number

 

一共 63 bits (最高位是 0)

 

unique ID 生成过程:

 

  • 10 bits 的机器号, 在 ID 分配 Worker 启动的时候, 从一个 Zookeeper 集群获取 (保证所有的 Worker 不会有重复的机器号)
  • 41 bits 的 Timestamp: 每次要生成一个新 ID 的时候, 都会获取一下当前的 Timestamp, 然后分两种情况生成 sequence number:
  • 如果当前的 Timestamp 和前一个已生成 ID 的 Timestamp 相同 (在同一毫秒中), 就用前一个 ID 的 sequence number + 1 作为新的 sequence number (12 bits); 如果本毫秒内的所有 ID 用完, 等到下一毫秒继续 (这个等待过程中, 不能分配出新的 ID)
  • 如果当前的 Timestamp 比前一个 ID 的 Timestamp 大, 随机生成一个初始 sequence number (12 bits) 作为本毫秒内的第一个 sequence number

 

整个过程中, 只是在 Worker 启动的时候会对外部有依赖 (需要从 Zookeeper 获取 Worker 号), 之后就可以独立工作了, 做到了去中心化.

 

异常情况讨论:

 

  • 在获取当前 Timestamp 时, 如果获取到的时间戳比前一个已生成 ID 的 Timestamp 还要小怎么办? Snowflake 的做法是继续获取当前机器的时间, 直到获取到更大的 Timestamp 才能继续工作 (在这个等待过程中, 不能分配出新的 ID)

 

从这个异常情况可以看出, 如果 Snowflake 所运行的那些机器时钟有大的偏差时, 整个 Snowflake 系统不能正常工作 (偏差得越多, 分配新 ID 时等待的时间越久)

 

从 Snowflake 的官方文档 (https://github.com/twitter/snowflake/#system-clock-dependency) 中也可以看到, 它明确要求 "You should use NTP to keep your system clock accurate". 而且最好把 NTP 配置成不会向后调整的模式. 也就是说, NTP 纠正时间时, 不会向后回拨机器时钟.

 

三, Snowflake 的其他变种

 

Snowflake 有一些变种, 各个应用结合自己的实际场景对 Snowflake 做了一些改动. 这里主要介绍 3 种.

 

1. Boundary flake

 

http://boundary.com/blog/2012/01/12/flake-a-decentralized-k-ordered-unique-id-generator-in-erlang/

 

变化:

 

  • ID 长度扩展到 128 bits:
  • 最高 64 bits 时间戳;
  • 然后是 48 bits 的 Worker 号 (和 Mac 地址一样长);
  • 最后是 16 bits 的 Seq Number
  • 由于它用 48 bits 作为 Worker ID, 和 Mac 地址的长度一样, 这样启动时不需要和 Zookeeper 通讯获取 Worker ID. 做到了完全的去中心化
  • 基于 Erlang

 

它这样做的目的是用更多的 bits 实现更小的冲突概率, 这样就支持更多的 Worker 同时工作. 同时, 每毫秒能分配出更多的 ID

 

2. Simpleflake

 

http://engineering.custommade.com/simpleflake-distributed-id-generation-for-the-lazy/

 

Simpleflake 的思路是取消 Worker 号, 保留 41 bits 的 Timestamp, 同时把 sequence number 扩展到 22 bits;

 

Simpleflake 的特点:

 

  • sequence number 完全靠随机产生 (这样也导致了生成的 ID 可能出现重复)
  • 没有 Worker 号, 也就不需要和 Zookeeper 通讯, 实现了完全去中心化
  • Timestamp 保持和 Snowflake 一致, 今后可以无缝升级到 Snowflake

 

Simpleflake 的问题就是 sequence number 完全随机生成, 会导致生成的 ID 重复的可能. 这个生成 ID 重复的概率随着每秒生成的 ID 数的增长而增长.

 

所以, Simpleflake 的限制就是每秒生成的 ID 不能太多 (最好小于 100次/秒, 如果大于 100次/秒的场景, Simpleflake 就不适用了, 建议切换回 Snowflake).

 

3. instagram 的做法

 

先简单介绍一下 instagram 的分布式存储方案:

 

  • 先把每个 Table 划分为多个逻辑分片 (logic Shard), 逻辑分片的数量可以很大, 例如 2000 个逻辑分片
  • 然后制定一个规则, 规定每个逻辑分片被存储到哪个数据库实例上面; 数据库实例不需要很多. 例如, 对有 2 个 PostgreSQL 实例的系统 (instagram 使用 PostgreSQL); 可以使用奇数逻辑分片存放到第一个数据库实例, 偶数逻辑分片存放到第二个数据库实例的规则
  • 每个 Table 指定一个字段作为分片字段 (例如, 对用户表, 可以指定 uid 作为分片字段)
  • 插入一个新的数据时, 先根据分片字段的值, 决定数据被分配到哪个逻辑分片 (logic Shard)
  • 然后再根据 logic Shard 和 PostgreSQL 实例的对应关系, 确定这条数据应该被存放到哪台 PostgreSQL 实例上

 

instagram unique ID 的组成:

 

  • 41 bits: Timestamp (毫秒)
  • 13 bits: 每个 logic Shard 的代号 (最大支持 8 x 1024 个 logic Shards)
  • 10 bits: sequence number; 每个 Shard 每毫秒最多可以生成 1024 个 ID

 

生成 unique ID 时, 41 bits 的 Timestamp 和 Snowflake 类似, 这里就不细说了.

 

主要介绍一下 13 bits 的 logic Shard 代号 和 10 bits 的 sequence number 怎么生成.

 

logic Shard 代号:

 

  • 假设插入一条新的用户记录, 插入时, 根据 uid 来判断这条记录应该被插入到哪个 logic Shard 中.
  • 假设当前要插入的记录会被插入到第 1341 号 logic Shard 中 (假设当前的这个 Table 一共有 2000 个 logic Shard)
  • 新生成 ID 的 13 bits 段要填的就是 1341 这个数字

 

sequence number 利用 PostgreSQL 每个 Table 上的 auto-increment sequence 来生成:

 

  • 如果当前表上已经有 5000 条记录, 那么这个表的下一个 auto-increment sequence 就是 5001 (直接调用 PL/PGSQL 提供的方法可以获取到)
  • 然后把 这个 5001 对 1024 取模就得到了 10 bits 的 sequence number

 

instagram 这个方案的优势在于:

 

  • 利用 logic Shard 号来替换 Snowflake 使用的 Worker 号, 就不需要到中心节点获取 Worker 号了. 做到了完全去中心化
  • 另外一个附带的好处就是, 可以通过 ID 直接知道这条记录被存放在哪个 logic Shard 上

同时, 今后做数据迁移的时候, 也是按 logic Shard 为单位做数据迁

 

http://darktea.github.io/notes/2013/12/08/Unique-ID



已有 0 人发表留言，猛击->> 这里<<-参与讨论


ITeye推荐



相关 [分布 系统 怎么样] 推荐：

分布式系统中, 怎么样生成全局唯一的 ID

- - zzm
在分布式系统存在多个 Shard 的场景中, 同时在各个 Shard 插入数据时, 怎么给这些数据生成全局的 unique ID?. 在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现.. 但在一个存在多个 Shards 的分布式系统 (例如多个 MySQL 实例组成一个集群, 在这个集群中插入数据), 这个问题会变得复杂, 所生成的全局的 unique ID 要满足以下需求:.

开发一个业务逻辑复杂的系统，应该怎么样设计才能使项目的扩展性更好？

- - SegmentFault 最新的文章
看到一篇 好文章，收藏一下. 我在知乎关于《 开发一个业务逻辑复杂的系统，应该怎么样设计才能使项目的扩展性更好. 既然业务逻辑复杂，那意味着项目前期的业务建模、需求分析、分析设计极为重要，直接抛开这几个阶段进入技术实施开发阶段，不管套用什么设计模式、架构模式，系统的扩展性肯定难以保证. 项目的扩展性虽然最终体现为系统架构、技术实现的扩展性，但系统扩展性的根源在于系统业务架构及业务模型的扩展性.

分布式缓存系统 Xixibase

- Le - 开源中国社区最新软件
Xixibase是一个高性能，跨平台的分布式缓存系统. Xixibase server 采用 C++ 实现，底层网络库采用的是Boost Asio. Xixibase 主要特点： 1. 实现'Local Cache'功能, 当客户端打开'Local Cache'选项, 客户端可以将数据同时存储在Server 端和本地，并且保证本地数据和Server 端的数据的一致性.

分布式检索系统 ElasticSearch

- - 丕子
ElasticSearch最近发展不错，github等都用它，可以关注I下. ElasticSearch是分布式,REST风格,搜索和分析系统. 具有实时数据，实时分析，分布式，高可用性，多租户，全文搜索，面向文档，冲突管理，自由模式，rest风格API，每个操作的持久性，Apache 2的开源许可证，基于Apache Lucene之上的特点.

分布式消息系统：Kafka

- - 标点符
Kafka是分布式发布-订阅消息系统. 它最初由LinkedIn公司开发，之后成为Apache项目的一部分. Kafka是一个分布式的，可划分的，冗余备份的持久性的日志服务. 在大数据系统中，常常会碰到一个问题，整个大数据是由各个子系统组成，数据需要在各个子系统中高性能，低延迟的不停流转. 传统的企业消息系统并不是非常适合大规模的数据处理.

分布式系统介绍-PNUTS

- - CSDN博客推荐文章
PNUTS是Yahoo!的分布式数据库系统，支持地域上分布的大规模并发操作. 它根据主键的范围区间或者其哈希值的范围区间将表拆分为表单元（Tablet），多个表单元存储在一个服务器上. 一个表单元控制器根据服务器的负载情况，进行表单元的迁移和拆分. 每条记录的数据都没有固定的模式（采用JSON格式的文本）.

Ganglia：分布式监控系统

- - CSDN博客移动开发推荐文章
1         环境安装配置. 1.1      依赖软件下载. Ganglia是伯克利开发的一个集群监控软件. 可以监视和显示集群中的节点的各种状态信息，比如如：cpu 、mem、硬盘利用率， I/O负载、网络流量情况等，同时可以将历史数据以曲线方式通过php页面呈现. 而ganglia又依赖于一个web服务器用来显示集群状态，用rrdtool来存储数据和生成曲线图，需要xml解析因此需要expat，配置文件解析需要libconfuse.

kafka分布式消息系统

- - CSDN博客云计算推荐文章
Kafka[1]是linkedin用于日志处理的分布式消息队列，linkedin的日志数据容量大，但对可靠性要求不高，其日志数据主要包括用户行为（登录、浏览、点击、分享、喜欢）以及系统运行日志（CPU、内存、磁盘、网络、系统及进程状态）. 当前很多的消息队列服务提供可靠交付保证，并默认是即时消费（不适合离线）.

分布式内存文件系统：Tachyon

- - 杨尚川的个人页面
Tachyon是一个分布式内存文件系统，可以在集群里以访问内存的速度来访问存储在Tachyon里的文件. Tachyon是架构在最底层的分布式文件系统和上层的各种计算框架之间的一种中间件，其主要职责是将那些不需要落地到DFS里的文件，落地到分布式内存文件系统中，来达到共享内存，从而提高效率，减少内存冗余，减少GC时间等.

FastDFS分布式文件系统

- - 开源软件 - ITeye博客
       FastDFS是一个开源的轻量级 分布式文件系统，它对文件进行管理，功能包括：文件存储、文件同步、文件访问（文件上传、文件下载）等，解决了大容量存储和负载均衡的问题. 特别适合以中小文件（建议范围：4KB < file_size <500MB）为载体的在线服务，如相册网站、视频网站等等.