UniqGenerator - 生成唯一ID技术方案
1. 前言
1.1. 目的
UniqGenerator提供一个简单、可靠、高效的、可支撑大容量和大并发的取绝对唯一ID（可以是数字型的，也可以是字符串型的）的通用机制，这里讲的“绝对”是指在同一系统内部的绝对唯一，有别于UUID（通用唯一识别码，Universally Unique Identifier）。
1.2. 背景
在很多应用场景中有着取唯一ID的需求，比如淘宝交易单号、中国人保保单号等，它们的特点是一长串数字或字母和数字混合的长字符串，而最关键的一点是必须绝对唯一，1000万中存在1个重复也不允许。
要满足这样的一个需求，最简单的方法是由单独的一台机器分配ID，然后供应其它机器使用，但是这种方法有两个问题：一是整个系统对这台机器产生了强依赖；二是这台机器可能会成为瓶颈。
2. 分析思路
分析思路可归纳为两点：一是对需求分类；二是针对需求以类举的方式提出解决方法。
3. 协议结构
3.1. 令牌和租约
参与分配唯一ID的机器都需要取得一个令牌，这是它能分配唯一ID的先决条件。令牌是一种有限的资源，获取令牌的方式是租约。
租期以天为单位，在一个令牌的租期未满之前，租用它的机器独占它，直到租期满1天后，即假设租期为7天，则8天后其它机器都可以租用该令牌。在租期的基础上延后1天是为保证令牌的绝对安全，防止同一个令牌在超过1台的机器上存活。
1台机器租用一个令牌后，可以对这个令牌不断续约，续约间隔时间以小时为单位。
3.2. 唯一性
怎么做到ID的唯一性？协议将根本下图所示的这样一个思路进行设计。
3.3. 结构
通过下图所示的结构，即可保证产生的ID在系统内部具有绝对的唯一性（本设计方案不能保证不同系统间的ID也能绝对唯一）：
针对不同需要，将结构划分成3种类型（但可以根据需求继续扩充）：
3.3.1. 固定长度的字符串
固定长度的字符串经常被用于定义各种订单号、交易流水号等，如中国人保（PICC）的保单号，微信的交易单号。
为满足不同的需求，令牌和序列号两者的字符个数是可以配置的。而日期、业务识别码和业务自定义部分需要应用自己以参数方式传入。
为了保证序列号的唯一性，须对序列号进行持久化记录，以便在时间范围内UniqGenerator进程重启或机器重启后，仍不会产生重复的序列号。
但如果仅这样，当这个序列号的记录文件被删除时，则会产生问题。为降低这个风险，UniqGenerator进程在启动时主动检查这个文件是否存在，如果不存在则直接启动失败。通过UniqGenerator的format参数可以生成这个文件，在首次启动时需要做一下这项工作，UniqGenerator不自动做的原因是为一定程序上保证安全性。
3.3.2. 有状态数字型
当需要为第一条留言或评论分配一个唯一的ID时，则可以使用有状态的数字型ID，一个8字节的无符号整数，程序处理起来也非常便利。调用程序可不关心Uniq64的内部结构，而直接将它当作整数使用。
由于只使用了8字节，时间部分无法精确到秒，所以序列号也需要持久化。
3.3.3. 无状态数字型
无状态数字型和有状态数字型的区别在于，无状态的不需要持久化记录序列号，因为它的时候精确到了秒，UniqGenerator进程每次启动时会延迟1秒钟，以错过时间来保证唯一性。也因此，它比有状态的多了4字节，程序中不能直接当作整数使用。
4. 序列号持久化
4.1. 文件结构
4.2. serial_file.h
namespace cpp uniq_generator.master
// Token类型定义
// 一台机器对于同一种类型的Token，只能租用一个
enum TokenType
{
TOKEN_STRING2_INCLUDE_LETTER = 2, // 2个字符，可包含A-Z字母
TOKEN_STRING3_INCLUDE_LETTER = 3, // 3个字符，可包含A-Z字母
TOKEN_STRING2_ONLY_NUMBER = 12, // 2个字符，纯数字
TOKEN_STRING3_ONLY_NUMBER = 13, // 3个字符，纯数字
TOKEN_UINT1 = 21, // 1个字节的无符号整数
TOKEN_UINT2 = 22 // 2个字节的无符号整数
}
// 租用结果
enum RentingResult
{
RR_SUCCESS = 0, // 租用成功
RR_RENTED = 1, // 已被其它租用
RR_UNRENTED = 2 // 未被租用
}
// 令牌
struct Token
{
1: TokenType token_type; // Token类型
2: string token; // Token
}
// 租约结构
struct TokenInfo
{
1: TokenType token_type; // Token类型
2: string token; // Token
3: i64 create_time; // 租约创建时间
4: i64 modification_time; // 最近续约时间
}
// 面向Agent的租约服务（心跳）
service LeaseService
{
// 申请一个Token租约
// 成功租约到返回非空字符串
// 租约过程中如果遇到错误，则抛出异常
string request_token(1: TokenType token_type);
// 续租
// tokens 被续约的Token
// 续租过程中如果遇到错误，则抛出异常
RentingResult rent_token(1: Token token);
// 获取已取得的所有Tokens
// 获取过程中如果遇到错误，则抛出异常
list list_tokens();
// 解约一个Token
// 解约过程中如果遇到错误，则抛出异常
void terminate_token(1: TokenType token_type, 2: string token);
// 心跳一下，啥都不做
void heartbeat();
}5. 系统架构
5.1. 分布式结构
UniqGenerator采用弱主从分布式架构。不同于一般的主从架构，这里的两个Master地位均等，可同时提供读和写。
两个Master间互发心跳，心跳间隔时间以秒为单位，两者间需要做数据同步。
Agent发也往Master发心跳，心跳间隔时间以小时为单位，通过心跳的方式续约Token。
5.1.1. Master
Master负责对Token的租约管理，并以心跳方式对Agent进行弱监控。
为防止Master单点的数据安全和服务可用性，需要部署两个Master实例。为规避主从Master切换问题，这两个Master地位均等，同时提供租约和续租服务。
续租可认为是读事件，租约可认为是写事件。对于写事件必须得到两个Master的共同确认，对于读事件则只需其中一个确认即可。
租期满时，就需要解约，这也是一个写事件，需要两个Master共同确认，满期的租约不能被续租。
需要两个Master共同确认，是为防止数据的不一致。一个Master重启后，需要先从另一Master同步数据，同步完成之前不提供服务。如果两个Master刚好都重启了，则相互同步，任何一个同步完成，即可提供读服务。
5.1.2. Agent
唯一ID由Agent产生，并提供多种形式的获取接口（如HTTP取唯一ID、RPC取唯一ID等）。Agent在产生唯一ID之前，需要先从Master成功租约到一个Token，Master保证同一个Token只会被一个Agent租用。
租期最少1天，最多可达30天，系统默认配置为7天。Master保证在租期内其它Agent不会租用到这个Token，但租期后可租给其它机器，因此Agent需要不断的向Master续租。过租期后，则只能重新租用新的Token。
5.2. Agent结构
Agent设计为单进程双线程结构：
1) SerialThread
响应取唯一ID请求，生成唯一ID，然后返回给请求者。
2) HeartbeatThread
专职向Master发送续约心跳，当不能正常与Master心跳时，则连接另一个Master，如果同任何一个Master都不能正常心跳，则轮询重试，直到心跳正常。
5.3. Master结构
在第一个版本中，Agent和Master的心跳基于Thrift RPC实现。但考虑到性能容量等因素，如果Thrift RPC不能胜任时，则可以引入基于UDP的实现。
Master是一个单进程多线程结构：
1) RPC Thread
为Agent和另一个Master提供RPC服务，实际上基于Thrift的实现，面向Agent和另一Master的RPC将是互相独立的RPC线程。
2) Lease Thread
租约线程，负责管理租约，如对租约满期的处理等。
3) HeartbeatThread
专职向另一个Master发心跳的线程，心跳也用于同步两者间的数据。
Master提供白名单机制，限制只有在白名单中的AGENT才可以申请租约，并提供一个Web界面管理租约。允许人为的强制解除租约和人工续约。
5.3.1. 租约接口lease.thrift
namespace cpp uniq_generator.master
// Token类型定义
// 一台机器对于同一种类型的Token，只能租用一个
enum TokenType
{
TOKEN_STRING2_INCLUDE_LETTER = 2, // 2个字符，可包含A-Z字母
TOKEN_STRING3_INCLUDE_LETTER = 3, // 3个字符，可包含A-Z字母
TOKEN_STRING2_ONLY_NUMBER = 12, // 2个字符，纯数字
TOKEN_STRING3_ONLY_NUMBER = 13, // 3个字符，纯数字
TOKEN_UINT1 = 21, // 1个字节的无符号整数
TOKEN_UINT2 = 22 // 2个字节的无符号整数
}
// 租用结果
enum RentingResult
{
RR_SUCCESS = 0, // 租用成功
RR_RENTED = 1, // 已被其它租用
RR_UNRENTED = 2 // 未被租用
}
// 令牌
struct Token
{
1: TokenType token_type; // Token类型
2: string token; // Token
}
// 租约结构
struct TokenInfo
{
1: TokenType token_type; // Token类型
2: string token; // Token
3: i64 create_time; // 租约创建时间
4: i64 modification_time; // 最近续约时间
}
// 面向Agent的租约服务（心跳）
service LeaseService
{
// 申请一个Token租约
// 成功租约到返回非空字符串
// 租约过程中如果遇到错误，则抛出异常
string request_token(1: TokenType token_type);
// 续租
// tokens 被续约的Token
// 续租过程中如果遇到错误，则抛出异常
RentingResult rent_token(1: Token token);
// 获取已取得的所有Tokens
// 获取过程中如果遇到错误，则抛出异常
list list_tokens();
// 解约一个Token
// 解约过程中如果遇到错误，则抛出异常
void terminate_token(1: TokenType token_type, 2: string token);
// 心跳一下，啥都不做
void heartbeat();
}6. 实现结构
UniqGenerator的实现充分利用了开源，以期大幅度提升开发效率：
1) Thrift
Agent和Master间，以及两个Master间的网络通讯使用的都是Thrift，使用RPC的好处是分布式编程变得简单快捷，同时Thrift支持丰富的语言，使得前后台交互也变得简单。
2) Boost
UniqGenerator使用著名的准C++标准库Boost作为基础类库，以帮助提升开发效率。同时，Thrift也需要Boost。
3) gflags
由Google出品的命令行参数解析器，使用得基于命令行参数的处理变得非常简单好用。
4) glog
由Google出品的写日志类库，流式的写日志，无类型安全问题。
7. 编程接口
7.1. uniq_generator.h
namespace cpp uniq_generator.master
// Token类型定义
// 一台机器对于同一种类型的Token，只能租用一个
enum TokenType
{
TOKEN_STRING2_INCLUDE_LETTER = 2, // 2个字符，可包含A-Z字母
TOKEN_STRING3_INCLUDE_LETTER = 3, // 3个字符，可包含A-Z字母
TOKEN_STRING2_ONLY_NUMBER = 12, // 2个字符，纯数字
TOKEN_STRING3_ONLY_NUMBER = 13, // 3个字符，纯数字
TOKEN_UINT1 = 21, // 1个字节的无符号整数
TOKEN_UINT2 = 22 // 2个字节的无符号整数
}
// 租用结果
enum RentingResult
{
RR_SUCCESS = 0, // 租用成功
RR_RENTED = 1, // 已被其它租用
RR_UNRENTED = 2 // 未被租用
}
// 令牌
struct Token
{
1: TokenType token_type; // Token类型
2: string token; // Token
}
// 租约结构
struct TokenInfo
{
1: TokenType token_type; // Token类型
2: string token; // Token
3: i64 create_time; // 租约创建时间
4: i64 modification_time; // 最近续约时间
}
// 面向Agent的租约服务（心跳）
service LeaseService
{
// 申请一个Token租约
// 成功租约到返回非空字符串
// 租约过程中如果遇到错误，则抛出异常
string request_token(1: TokenType token_type);
// 续租
// tokens 被续约的Token
// 续租过程中如果遇到错误，则抛出异常
RentingResult rent_token(1: Token token);
// 获取已取得的所有Tokens
// 获取过程中如果遇到错误，则抛出异常
list list_tokens();
// 解约一个Token
// 解约过程中如果遇到错误，则抛出异常
void terminate_token(1: TokenType token_type, 2: string token);
// 心跳一下，啥都不做
void heartbeat();
}腾讯云开发者
