推荐: blog.csdn.net/aquester https://github.com/eyjian https://www.cnblogs.com/aquester http://blog.chinaunix.net/uid/20682147.html
全部博文（595）
分类： 架构设计与优化
2015-04-15 18:34:16
UniqGenerator提供一个简单、可靠、高效的、可支撑大容量和大并发的取绝对唯一ID（可以是数字型的，也可以是字符串型的）的通用机制，这里讲的“绝对”是指在同一系统内部的绝对唯一，有别于UUID（通用唯一识别码，Universally Unique Identifier）。
在很多应用场景中有着取唯一ID的需求，比如淘宝交易单号、中国人保保单号等，它们的特点是一长串数字或字母和数字混合的长字符串，而最关键的一点是必须绝对唯一，1000万中存在1个重复也不允许。
要满足这样的一个需求，最简单的方法是由单独的一台机器分配ID，然后供应其它机器使用，但是这种方法有两个问题：一是整个系统对这台机器产生了强依赖；二是这台机器可能会成为瓶颈。
分析思路可归纳为两点：一是对需求分类；二是针对需求以类举的方式提出解决方法。
参与分配唯一ID的机器都需要取得一个令牌，这是它能分配唯一ID的先决条件。令牌是一种有限的资源，获取令牌的方式是租约。
租期以天为单位，在一个令牌的租期未满之前，租用它的机器独占它，直到租期满1天后，即假设租期为7天，则8天后其它机器都可以租用该令牌。在租期的基础上延后1天是为保证令牌的绝对安全，防止同一个令牌在超过1台的机器上存活。
1台机器租用一个令牌后，可以对这个令牌不断续约，续约间隔时间以小时为单位。
怎么做到ID的唯一性？协议将根本下图所示的这样一个思路进行设计。
通过下图所示的结构，即可保证产生的ID在系统内部具有绝对的唯一性（本设计方案不能保证不同系统间的ID也能绝对唯一）：
针对不同需要，将结构划分成3种类型（但可以根据需求继续扩充）：
固定长度的字符串经常被用于定义各种订单号、交易流水号等，如中国人保（PICC）的保单号，微信的交易单号。
为满足不同的需求，令牌和序列号两者的字符个数是可以配置的。而日期、业务识别码和业务自定义部分需要应用自己以参数方式传入。
为了保证序列号的唯一性，须对序列号进行持久化记录，以便在时间范围内UniqGenerator进程重启或机器重启后，仍不会产生重复的序列号。
但如果仅这样，当这个序列号的记录文件被删除时，则会产生问题。为降低这个风险，UniqGenerator进程在启动时主动检查这个文件是否存在，如果不存在则直接启动失败。通过UniqGenerator的format参数可以生成这个文件，在首次启动时需要做一下这项工作，UniqGenerator不自动做的原因是为一定程序上保证安全性。
当需要为第一条留言或评论分配一个唯一的ID时，则可以使用有状态的数字型ID，一个8字节的无符号整数，程序处理起来也非常便利。调用程序可不关心Uniq64的内部结构，而直接将它当作整数使用。
由于只使用了8字节，时间部分无法精确到秒，所以序列号也需要持久化。
无状态数字型和有状态数字型的区别在于，无状态的不需要持久化记录序列号，因为它的时候精确到了秒，UniqGenerator进程每次启动时会延迟1秒钟，以错过时间来保证唯一性。也因此，它比有状态的多了4字节，程序中不能直接当作整数使用。
|
#ifndef SERIAL_FILE_H #define SERIAL_FILE_H
#include namespace uniq_generator {
// 运行：uniq_generator --format，格式化生成序列号文件 // 如果uniq_generator启动时检测不到文件存在，则启动不成功。
#pragma pack(4)
// 序列号文件头结构 struct SerialFileHeader { uint32_t version; // 版本号 uint32_t num_blocks; // 块数（默认100） uint64_t padding1; // 预留 uint64_t padding2; // 预留 uint64_t padding3; // 预留 uint64_t padding4; // 预留 uint64_t padding5; // 预留 uint64_t padding6; // 预留 uint64_t padding7; // 预留 uint64_t padding8; // 预留 struct SerialBlock blocks[0]; };
// 序列号块结构 // 对于Uniq96类型，它不需要持久化 struct SerialBlock { char name[16]; // 名称，如果一个块未被使用，则名称为空，要求最后一个字符为结尾符 int64_t create_time; // 创建时间 int64_t modification_time; // 最后更新时间
union { uint32_t flags; // 标志字段 struct { uint32_t everyday_reset: 1; // 每天是否重置 uint32_t padding: 31; // 预留 }; };
uint32_t padding1; // 预留 uint64_t padding2; // 预留 uint64_t padding3; // 预留 uint64_t serial; // 序列号 uint32_t step; // 更新步大小 };
#pragma pack()
} // namespace uniq_generator #endif // SERIAL_FILE_H |
UniqGenerator采用弱主从分布式架构。不同于一般的主从架构，这里的两个Master地位均等，可同时提供读和写。
两个Master间互发心跳，心跳间隔时间以秒为单位，两者间需要做数据同步。
Agent发也往Master发心跳，心跳间隔时间以小时为单位，通过心跳的方式续约Token。
Master负责对Token的租约管理，并以心跳方式对Agent进行弱监控。
为防止Master单点的数据安全和服务可用性，需要部署两个Master实例。为规避主从Master切换问题，这两个Master地位均等，同时提供租约和续租服务。
续租可认为是读事件，租约可认为是写事件。对于写事件必须得到两个Master的共同确认，对于读事件则只需其中一个确认即可。
租期满时，就需要解约，这也是一个写事件，需要两个Master共同确认，满期的租约不能被续租。
需要两个Master共同确认，是为防止数据的不一致。一个Master重启后，需要先从另一Master同步数据，同步完成之前不提供服务。如果两个Master刚好都重启了，则相互同步，任何一个同步完成，即可提供读服务。
唯一ID由Agent产生，并提供多种形式的获取接口（如HTTP取唯一ID、RPC取唯一ID等）。Agent在产生唯一ID之前，需要先从Master成功租约到一个Token，Master保证同一个Token只会被一个Agent租用。
租期最少1天，最多可达30天，系统默认配置为7天。Master保证在租期内其它Agent不会租用到这个Token，但租期后可租给其它机器，因此Agent需要不断的向Master续租。过租期后，则只能重新租用新的Token。
Agent设计为单进程双线程结构：
1) SerialThread
响应取唯一ID请求，生成唯一ID，然后返回给请求者。
2) HeartbeatThread
专职向Master发送续约心跳，当不能正常与Master心跳时，则连接另一个Master，如果同任何一个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界面管理租约。允许人为的强制解除租约和人工续约。
|
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
// 解约一个Token // 解约过程中如果遇到错误，则抛出异常 void terminate_token(1: TokenType token_type, 2: string token);
// 心跳一下，啥都不做 void heartbeat(); } |
UniqGenerator的实现充分利用了开源，以期大幅度提升开发效率：
1) Thrift
Agent和Master间，以及两个Master间的网络通讯使用的都是Thrift，使用RPC的好处是分布式编程变得简单快捷，同时Thrift支持丰富的语言，使得前后台交互也变得简单。
2) Boost
UniqGenerator使用著名的准C++标准库Boost作为基础类库，以帮助提升开发效率。同时，Thrift也需要Boost。
3) gflags
由Google出品的命令行参数解析器，使用得基于命令行参数的处理变得非常简单好用。
4) glog
由Google出品的写日志类库，流式的写日志，无类型安全问题。
|
#ifndef UNIQ_GENERATOR_H #define UNIQ_GENERATOR_H
#include
#include
#include namespace uniq_generator {
// 64位的唯一数 // Uniq64的优点是可以直接做64位无符号整数使用 // 它的特点是时间精确到小时，无论是同一台机器还是不同台机器，不同小时产生的值均不会相同 struct Uniq64 { union { uint64_t value;
struct { uint64_t year: 7; // 当前年份减2000后的值，如2015为15，2115为115，最多支持到2127年 uint64_t month: 4; // 当前的月份 uint64_t day: 5; // 当前日期的月份天 uint64_t hour: 5; // 当前时间的小时
uint64_t token: 12; // 每台机器独占的，用来做机器间的区分 uint64_t serial: 31; // 递增的序列号，一天内不重复，单台机器一天最大到2147483648 }; };
std::string str() const { std::stringstream result; result << value; return result.str(); }
std::string uri() const { std::stringstream result; result << "uniq64://" << year << "-" << month << "-" << day << "_" << hour << "/" << token << "/" << serial; return result.str(); } };
// 96位的唯一数 // Uniq96相比Uinq64，不能直接做整数值使用 // 它的特点是时间精确到秒，无论是同一台机器还是不同台机器，不同秒产生的值均不会相同 // 使用它时，建议进程启动时延迟一秒，以保证可以总是产生不同的值 struct Uniq96 { union { uint64_t value;
struct { uint64_t year: 12; // 当前年份减2000后的值，如2015为15，6096为4096，最多支持到6096年 uint64_t month: 4; // 当前日期的月份 uint64_t day: 5; // 当前日期的月份天 uint64_t hour: 5; // 当前时间的小时 uint64_t minute: 6; // 当前时间的分 uint64_t second: 6; // 当前时间的秒 uint64_t microsecond: 10; // 与当前时间的微秒数相关的值 uint64_t token: 16; // 每台机器独占的，用来做机器间的区分 }; };
uint32_t serial; // 递增的序列号
std::string str() const { std::stringstream result; result << value << serial; return result.str(); }
std::string uri() const { std::stringstream result; result << "uniq96://" << year << "-" << month << "-" << day << "_" << hour << ":" << minute << ":" << second << "_" << microsecond << "/" << token << "/" << serial; return result.str(); } };
class CUniqException: public std::exception { public: explicit CUniqException(int errcode, const char* errmsg, const char* file, int line) throw () { init(errcode, errmsg, file, line); }
explicit CUniqException(int errcode, const std::string& errmsg, const std::string& file, int line) throw() { init(errcode, errmsg.c_str(), file.c_str(), line); }
virtual const char* what() const throw() { return _errmsg.c_str(); }
int errcode() const throw() { return _errcode; }
const char* file() const throw() { return _file.c_str(); }
int line() const throw() { return _line; }
private: void init(int errcode, const char* errmsg, const char* file, int line) throw () { _errcode = errcode; if (errmsg != NULL) _errmsg = errmsg;
if (file != NULL) _file = file; _line = line; }
private: int _errcode; std::string _errmsg; std::string _file; int _line; };
// // 工厂方法 //
// 取得内置的UniqGenerator // 如果获取过程中遇到错误，则抛出CUniqException extern IUniqGenerator* get_uniq_generator() throw (CUniqException);
// 根据指定的名称创建一个UniqGenerator // 如果名字已存在则返回NULL // 如果创建过程中遇到错误，则抛出CUniqException extern IUniqGenerator* create_uniq_generator(const std::string& uniq_generator_name) throw (CUniqException);
// 取唯一数接口 class IUniqGenerator { public: virtual ~IUniqGenerator() throw () {}
virtual std::string get_uniq(size_t token_size) throw (CUniqException) = 0; virtual void get_uniq(Uniq64* uniq) throw (CUniqException) = 0; virtual void get_uniq(Uniq96* uniq) throw (CUniqException) = 0; };
} // namespace uniq_generator #endif // UNIQ_GENERATOR_H |
UniqGenerator.pdf