前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >UniqGenerator - 生成唯一ID技术方案

UniqGenerator - 生成唯一ID技术方案

作者头像
一见
发布2018-08-10 17:48:52
9630
发布2018-08-10 17:48:52
举报
文章被收录于专栏:蓝天

UniqGenerator.pdf

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

代码语言:javascript
复制
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

代码语言:javascript
复制
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

代码语言:javascript
复制
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(); 
				
				
					}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015/04/15 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 前言
    • 1.1. 目的
      • 1.2. 背景
      • 2. 分析思路
      • 3. 协议结构
        • 3.1. 令牌和租约
          • 3.2. 唯一性
            • 3.3. 结构
              • 3.3.1. 固定长度的字符串
              • 3.3.2. 有状态数字型
              • 3.3.3. 无状态数字型
          • 4. 序列号持久化
            • 4.1. 文件结构
              • 4.2. serial_file.h
              • 5. 系统架构
                • 5.1. 分布式结构
                  • 5.1.1. Master
                  • 5.1.2. Agent
                • 5.2. Agent结构
                  • 5.3. Master结构
                    • 5.3.1. 租约接口lease.thrift
                • 6. 实现结构
                • 7. 编程接口
                  • 7.1. uniq_generator.h
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档