Total Pageviews

Monday, 16 July 2012

数据唯一标识的生成方法



在之前的一次内部技术讨论会上,大家对于如何生成一个能够在多个IDC之间不重复、尽量 保持顺序、长度尽量短小的消息ID进行了深入的讨论。基本达成初步意见:
1,为了能够在多个IDC之间不进行同步通讯的前提下,生成基本顺序的ID,则ID首部必须为时间。
2,为了区分多个IDC,则ID必须包含IDC的标识。
3,为了在同一个IDC之内保持唯一,必须局部(IDC内部)保持唯一的机制(比如自增序列)。

简单的方案一:
4四节的时间戳 + 2字节的IDC标识 + 2字节的局部自增序列 = 8字节的唯一ID。

以上方案中,为了实现局部自增序列,实际部署时单独部署局部自增序列生成器,也就是俗称“发号器”。
为了去除对于“发号器”的依赖,我们可以将IDC标识改进为进程PID和主机HID的标识。

改进的方案二:
 4字节的时间戳 + 3字节的主机HID + 2字节的进程PID + 3字节的进程内部自增序列 = 12字节的唯一ID。

方案二是MongoDB生成其数据主键_id的主要算法。 方案二增加了4个字节的存储,但可以省掉“发号器”,每个应用进程内部即可自主生成唯一的、基本保持顺序的ID。 每个进程每秒钟可以生成大约1600万以上不重复的ID,足够一般应用使用了。

为了节省存储空间,可以再压榨一下各个字段的范围: 时间戳可以改为以分钟为单位,可以缩减为3个字节,大概可以使用30年。 通过精密控制,主机HID可以控制在1字节,可以容纳最多256台主机。 如果不进行系统级别的Hack,我目前无法对PID进行压缩。 进程内部自增序列可以缩减2个字节,每秒钟可以生成最多65536个唯一ID。

精简的方案三:
3字节时间戳 + 1字节主机HID + 2字节进程PID + 2字节进程内部自增序列 = 8字节唯一ID。

对于局部自增序列,也有多种实现方式,但需要满足自成体系、简单高效的原则。
对于PHP的环境,APC扩展模块提供的多个本地进程间共享一个自增序列的方法:apc_inc。 使用apc_inc可以在多个本地进程间维护一个自增序列,不依赖外部系统,不进行远程调用,可以满足要求。 这样的做法,实际上是在主机的层次提供了一个唯一的序列,所以以上方案中的进程PID与局部自增序列可以合并。

改进的方案四:
4字节的时间戳 + 2字节的主机HID + 2字节的主机内部自增序列 = 8字节全局唯一ID。
这个方案可以容纳65536台主机,每台主机每秒钟可以生成6万左右的唯一ID。

综上所述,我认为方案四可以满足大部分业务的需求,方案二适用于部署超大规模的系统。两种方案均无需单独部署“发号器”。

-----------------------------

 对于HID维护的问题,经过我的分析,我提出以下方案:
1,维护一份 IP地址 -- 主机HID 的对应表。
2,将对应表以配置文件的方式,推送到各个服务器。
3,应用获取本机的IP地址,然后通过读取配置文件,获取自己的主机HID。

我认为此方案可行的主要原因:
1,配置文件只有一份,所有(同一应用范围)的服务器使用同一份配置文件。
2,配置文件简单明了,HID以递增方式排列,并且可以使用程序来进行唯一性检查,出错(HID重复)的几率大大降低。
3,推送机制成熟,有很多种方案.