一、背景介绍
在大型互联网应用中，随着用户数的增加；为了提高应用的性能，我们经常需要对数据库进行分库分表操作。在单表时代我们可以完全依赖于数据库的自增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;
}
网友评论