一、背景介绍

在大型互联网应用中，随着用户数的增加；为了提高应用的性能，我们经常需要对数据库进行分库分表操作。在单表时代我们可以完全依赖于数据库的自增ID来唯一标识一个条数据。但是当我们对数据库进行了分库分表之后，就不能依赖于每个表的自增ID来全局唯一标识这些数据了。因为自增的ID不能在分库分表的场景下准确的路由到正确的数据。

因此我们需要提供一个全局唯一的ID生成策略来支持分库分表的应用环境；
这个系统必须满足以下需求：

全局唯一：不能出现重复的ID；
高可用： ID生成系统属于基础服务，同时被许多关键系统调用，一旦宕机，会造成严重影响；

二、经典方案介绍

1. UUID

UUID是Universally Unique Identifier的缩写，它是在一定范围内（从特定的名字空间到全球）唯一的机器生成的标识符，UUID是16字节128位长的数字，通常以36字节的字符串表示；比如：

UUID经由一定的算法机器生成，为了保证UUID的唯一性，规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素，以及从这些元素生成UUID的算法。UUID的复杂特性在保证了其唯一性的同时，意味着只能由计算机生成。

优点：

本地生成ID，不需要远程调用、低延时、性能高；

缺点：

UUID过长，16字节128位，很多场景不适用；比如用UUID做数据库的索引时，插入数据时数据量越大，插入性能越低；
UUID不是有序的，无法保证趋势递增；

2. Flicker方案

该方案主要的思路是采用了MySQL自增长的ID的机制（auto_increment + replace into）

--- 数据表
CREATE TABLE Tickets64 (
  id     bigint(20) unsigned NOT NULL auto_increment,
  stub char(1)     NOT NULL                default '',
  PRIMARY KEY (id),
  UNIQUE KEY   stub (stub)
)ENGINE=MyISAM;

--- 每次业务使用下列sql读写MySQL得到ID号
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

replace into跟insert功能类似，不同之处在于： replace into 首先尝试插入数据到表中，如果发现表中已经有此行数据则先删除此行数据，然后插入新的数据，否则直接插入新数据；

优点：

充分借助数据库的自增ID机制，可靠性高，生成有序ID

缺点：

ID生成性能依赖单台数据库读写性能；
依赖数据库，当数据库异常时整个系统不可用。

3. Twitter-Snowflake方案

Twitter-Snowflake算法产生的背景相当简单，是为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户排序），并且在分布式系统中不同机器产生的id必须不同。

Snowflake算法核心

把时间戳、工作机器Id、序列号组合在一起。

Snowflake核心算法

除了最高位bit标记为不可用以外，其余三组bit占位均可浮动，具体看业务需求而定。默认情况下：

41bit的时间戳可以支持该算法使用到2082年；
10bit的工作机器id可以支持1023台机器，
序列号支持1毫秒产生4095个自增序列id。

Snowflake - 时间戳

在这里，时间戳的粒度为毫秒级，具体代码如下：

uint64_t generateStamp() {
  timeval tv;
  gettimeofday(&tv, 0);
  return (uint64_t)tv.tv_sec * 1000 + (uint64_t)tv.tv_usec / 1000;
}

默认情况下有41个bit可以使用，那么(1 << 41) / (3600 * 24 * 365 * 1000) = 69.7年

Snowflake - 工作机器Id

严格意义来说工作机器Id可以是进程级的, 机器级的话可以使用MAC地址来唯一标示工作机器，工作进程级可以使用IP + Path来区分工作进程。如果工作机器比较少，可以使用配置文件来设置这个id是一个不错的选择，如果机器过多配置文件来维护则是一件灾难性的事情。

Snowflake - 序列号

序列号就是一系列的自增Id,为了处理在同一毫秒内需要给多条消息分配id，若同一毫秒把序列号用完了，则“等待至下一毫秒”

uint64_t waitNextMs(uint64_t lastStamp){
  uint64_t cur = 0;
  do {
    cur = generateStamp();
  } while (cur <= lastStamp);
  return cur;
}

Snowflake参数资料 https://github.com/twitter/snowflake

分布式唯一ID服务架构