分布式系统中生成全局唯一ID方案

2017-04-02  本文已影响872人  FX_SKY

本文主要介绍在一个分布式系统中, 如何去生成全局唯一的 ID。

前言

单纯的生成全局ID并不是什么难题,生成全局的 unique ID 要满足以下需求:

问题描述

当用户量激增 系统架构演进到一定的阶段,常常会设计到分库分表,
例如根据id对用户表(t_user)进行分表,[0,999999]保存在t_user_0表,[1000000,1999999]保存在t_user_1表中,依次类推,怎么给这些用户生成全局的 unique ID?

全局ID产生的几种方式

1、数据库自增id

当服务使用的数据库只有单库单表时,可以利用数据库的auto_increment来生成全局唯一递增ID.

优势:

劣势:

2、UUID

一般的编程语言中会自带UUID的实现,比如Java中UUID方式UUID.randomUUID().toString(),可以通过服务程序本地产生,ID的生成不依赖数据库的实现。

优势:

劣势:

3、Flickr 的全局主键生成方案

flickr巧妙地使用了MySQL的自增ID,及replace into语法,十分简洁地实现了分片ID生成功能。详见 :http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

比如创建64位的自增id:
首先,创建一个表:

CREATE TABLE `uid_sequence` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM;

SELECT * from uid_sequence 输出:
+-------------------+------+
| id | stub |
+-------------------+------+
| 72157623227190423 | a |

如果我需要一个全局的唯一的64位uid,则执行:

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

说明:

这里flickr使用两台数据库(也可以更多)作为自增序列生成,通过这两台机器做主备和负载均衡。

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

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

优点:

缺点:

4、Twitter Snowflake

twitter利用zookeeper实现了一个全局ID生成的服务Snowflake:https://github.com/twitter/snowflake

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

一共 63 bits (最高位是 0)

unique ID 生成过程:

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

Twitter官方提供的snowflake是使用Scala编写的,本人使用Java语言重写了,链接:https://github.com/TiFG/id-generator/tree/master/snowflake-java

5、Instagram的做法

instagram参考了flickr的方案,再结合twitter的经验,利用Postgre数据库的特性,实现了一个更简单可靠的ID生成服务。链接:http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram


instagram unique ID 的组成:

以instagram举的例子为说明:
假定时间是September 9th, 2011, at 5:00pm,则毫秒数是1387263000(直接使用系统得到的从1970年开始的毫秒数)。那么先把时间数据放到ID里:
id = 1387263000 << (64-41)
再把分片ID放到时间里,假定用户ID是31341,有2000个逻辑分片,则分片ID是31341 % 2000 -> 1341:
id |= 1341 << (64-41-13)
最后,把自增序列放ID里,假定前一个序列是5000,则新的序列是5001:
id |= (5001 % 1024)
这样就得到了一个全局的分片ID。

我们可以通过INSERT语句的RETURNING 关键字,将ID返回给应用程序;
这里是the PL/PGSQL的完整例子(例子的schema :insta5):

CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$ 
DECLARE 
    our_epoch bigint := 1314220021721; 
    seq_id bigint; 
    now_millis bigint; 
    shard_id int := 5; 
BEGIN 
    SELECT nextval('insta5.table_id_seq') %% 1024 INTO seq_id;

    SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis; 
    result := (now_millis - our_epoch) << 23; 
    result := result | (shard_id << 10); 
    result := result | (seq_id); 
END; 
$$ LANGUAGE PLPGSQL; 
And when creating the table, we do:

CREATE TABLE insta5.our_table ( 
    "id" bigint NOT NULL DEFAULT insta5.next_id(), 
    ...rest of table schema... 
)

6、其他方案

例如:MongoDB的ObjectId,采用12个字节的长度,并且将时间戳进行编码。链接:https://docs.mongodb.com/manual/reference/method/ObjectId/

参考资料

分布式唯一主键生成器

上一篇 下一篇

猜你喜欢

热点阅读