专栏首页IT技术精选文摘分布式系统中生成全局ID的总结与思考

分布式系统中生成全局ID的总结与思考

世间万物,都有自己唯一的标识,比如人,每个人都有自己的指纹(白夜追凶给我科普的,同卵双胞胎DNA一样,但指纹不一样)。又如中国人,每个中国人有自己的身份证。对于计算机,很多时候,也需要为每一份数据生成唯一的标识。在这里,数据的概念是非常宽泛的,比如数据量记录、文件、消息,而唯一的标识我们称之为id。

自增ID

使用过mysql的同学应该都知道,经常用自增id(auto increment)作为主键,这是一个为long的整数类型,每插入一条记录,该值就会增加1,这样每条记录都有了唯一的id。自增id应该是使用最广泛的id生成方式,其优点在于非常简单、对数据库索引友好、而且也能透露出一些信息,比如当前有多少条记录(当然,用户也可能通过id猜出总共有多少用户,这就不太好)。但自增ID也有一些缺点:第一,id携带的信息太少,只能起到一个标识作用;第二,现在啥都是分布式的,如果多个mysql组成一个逻辑上的‘mysql’(比如水平分库这种情况),每个物理mysql都使用自增id,局部来说是唯一的,但总体来说就不唯一了。

于是乎,我们需要为分布式系统生成全局唯一的id。最简单的办法,部署一个单点,比如单独的服务(mysql)专门负责生成id,所有需要id的应用都通过这个单点获取一个唯一的id,这样就能保证系统中id的全局唯一性。但是分布式系统中最怕的就是单点故障(single point of failure),单点故障是可靠性、可用性的头号天敌,因此即使是中心化服务(centralized service)也会搞成一个集群,比如zookeeper。按照这个思路,就有了Flicker的解决方案。

Flicker的解决办法叫《Ticket Servers: Distributed Unique Primary Keys on the Cheap》,文章篇幅不长,而且通俗易懂,这里也有中文翻译。简单来说,Flicker是用两组(多组)mysql来提供全局id的生成,多组mysql避免了单点,那么怎么保证多组mysql生成的id全局唯一呢,这就利用了mysql的自增id以及replace into语法。

大家都知道mysql的自增id,但是不一定知道其实可以设置自增id的初始值以及自增步长, Flicker中的示例中,两个mysql(ticketserver)初始值分别是1和2,自增步长都是2(而不是默认值1),这样,ticketserver1永远生成奇数的id,而ticketserver2永远生成偶数的id

TicketServer1: auto-increment-increment = 2 auto-increment-offset = 1 TicketServer2: auto-increment-increment = 2 auto-increment-offset = 2

那么怎么获取这个id呢,不可能每需要一个id的时候都插入一条记录,这个时候就用到了replace into语法。 replace是insert、update的结合体,对于一条待插入的记录,如果其主键或者唯一索引的值已经存在表中的话,那么会删除旧的那条记录,然后插入新的记录;如果不存在,那么直接插入记录。这个非常类似mongodb中的findandmodify语法。在Flicker中,是这么使用的,首先schema如下:

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

注意,id是主键,而stub是唯一索引,当需要产生一个id的时候,使用以下sql语句;

REPLACE INTO Tickets64 (stub) VALUES ('a'); SELECT LAST_INSERT_ID();

由于stub是唯一索引,当每次都插入‘a'的时候,会产生新的记录,而新记录的id是自增的(则增步长为2)

Flicker的解决办法通俗易懂,但还是没有解决id信息过少的问题,而且还是依赖单独的一组服务(mysql)来生成全局id。如果全局id的生成不依赖额外的服务,而且包含丰富的信息那就最好了。

携带时间与空间信息的ID

UUID

提到全局id,首先想到的肯定是UUID(Universally unique identifier),从名字就能看出,这个是专门用来生成全局id的。而UUID又分为多个版本,不同的语言,厂家都有自己的实现。本文对uuid的介绍主要参考rfc4122,如下图所示,一个uuid由一下部分组成:

可以看到,uuid包含128个bit、即16个字节,其中包含了时间信息、版本号信息、机器信息。uuid也不是说一定能保证不冲突,但其冲突的概率小到可以忽略不计。使用uuid就不用再使用额外的id生成服务了。但缺点也有明显:太长,16个字节!太长有什么问题呢,占用空间?问题不大。主要的问题,是太长且随机的id对索引的不友好。在《Are you designing Primary Keys and ID’s???Well think twice..》一文中,作者也许需要用uuid来代替自增id,作者指出:

  So what do we do change ID’s to UUID as well. Well no, that’s not a good idea because we will simply increase work for our database server. It will now have to index a random string of 128 bit. The data will be more fragmented and bigger to fit in memory. This will definitely bring down the performance of our system.

测试结果如下:

第一例是当前db中有多少条记录,第二列是使用uuid作为key时插入1 million条记录耗费的时间,第三列是使用64位的整形作为key时插入1 million条记录耗费的时间。从结果可以看出,随着数据规模增大,使用uuid时的插入速度远小于使用整形的情况。

既然uuid太长了,那后来者都是在uuid的基础上尽量缩短id的长度,使之更加实用。我认为,如果使用时间信息、机器信息来生成id的话,那么应该就是借鉴了uuid的做法,包含但不限于:twitter的snowflake,mongodb的ObjectId。下面以ObjectID为例详细介绍。关于snowflake,可以参考这篇和这篇文章。

MongoDB ObjectId

ObjectId is a 12-byte BSON type, constructed using:

  • a 4-byte value representing the seconds since the Unix epoch,
  • a 3-byte machine identifier,
  • a 2-byte process id, and
  • a 3-byte counter, starting with a random value.

objectid有12个字节,包含时间信息(4字节、秒为单位)、机器标识(3字节)、进程id(2字节)、计数器(3字节,初始值随机)。其中,时间位精度(秒或者毫秒)与序列位数,二者决定了单位时间内,对于同一个进程最多可产生多少唯一的ObjectId,在MongoDB中,那每秒就是2^24(16777216)。但是机器标识与进程id一定要保证是不重复的,否则极大概率上会产生重复的ObjectId。

在mongo.exe中,通过ObjectId.getTimestamp可以获取时间信息

mongos> x = ObjectId() ObjectId("59cf6033858d9d5a85caac02") mongos> x.getTimestamp() ISODate("2017-09-30T09:13:23Z")

MongoDb的各语言驱动都实现了ObjectId的生成算法,比如PyMongo,在bson.objectid.py里面。我们看看两个核心的函数,就知道是如何生成ObjectiD

def _machine_bytes():

"""Get the machine portion of an ObjectId.

"""

machine_hash = _md5func()

if PY3:

# gethostname() returns a unicode string in python 3.x

# while update() requires a byte string.

machine_hash.update(socket.gethostname().encode())

else:

# Calling encode() here will fail with non-ascii hostnames

machine_hash.update(socket.gethostname())

return machine_hash.digest()[0:3]

def __generate(self):

"""Generate a new value for this ObjectId.

"""

oid = EMPTY

# 4 bytes current time

oid += struct.pack(">i", int(time.time()))

# 3 bytes machine

oid += ObjectId._machine_bytes

# 2 bytes pid

oid += struct.pack(">H", os.getpid() % 0xFFFF)

# 3 bytes inc

ObjectId._inc_lock.acquire()

oid += struct.pack(">i", ObjectId._inc)[1:4]

ObjectId._inc = (ObjectId._inc + 1) % 0xFFFFFF

ObjectId._inc_lock.release()

self.__id = oid

_machine_bytes函数首先获取主机名,hash之后取前3个字节作为机器标识。核心在__generate函数,代码有清晰的注释。可以看到,oid的生成每次都获取当前时间,int取整到秒,然后加上机器标识、进程号,而计数器(_inc)通过加锁保证线程安全。

从代码可以看出两个问题:第一,即使在同一个机器同一个进程,也是可能产生相同的ObjectID的,因为_inc简单自增,且每次都直接通过time.time获取时间。第二,如果生成的机器标识相同,那么大大增加了产生相同ObjectId的概率。

与之对比,SnowFlake有对象的解决办法:

第一:生成ID的时候,获取并记录当前的时间戳。如果当前时间戳与上一次记录的时间戳相同,那么将计数器加一,如果计数器已满,那么会等到下一毫秒才会生成ID。如果当前时间戳大于上一次记录的时间戳,那么随机初始化计数器,并生成ID。

第二:使用zookeeper来生成唯一的workerid,workerid类似mongodb的机器标识+进程号,保证了workerid的唯一性。

SnowFlake的方案,虽然冲突概率更小,但是需要额外的服务zookeeper,而且指出的workerid受限。ObjectiD的生成是由驱动负责的,不是MongoDB负责,这样减轻了MongoDB负担,也达到了去中心化服务的目的。

结构化ID思考

这里的结构化ID,就是指按一定规则,用时间、空间(机器)信息生成的ID,上面介绍的UUID以及各种变种都属于结构化id。

结构化ID的优点在于充足的信息,最有用的肯定是时间信息,通过ID就能直接拿到数据的创建时间了;另外,天然起到了冷热数据的分离。当然,有利必有弊,比如在ID作为分片键的分片环境中,如果ID包含时间信息,那么很可能在短时间内生成的数据会落在同一个分片。在《带着问题学习分布式系统之数据分片》一文中,介绍了MongoDB分片的两种方式:“hash partition”与“range partition“,如果使用ObjectId作为sharding key,且sharding方式为range partition,那么批量导入数据的时候就会导致数据落在同一个shard,结果就是大量chunk的split和migration,这是不太好的。

TFS文件名

如果结构化ID中包含分片信息,那就更好了,这样就不会再维护数据与分片的信息,而是直接通过id找出对应的分片。我们来看看TFS的例子

TFS是淘宝研发的分布式文件存储系,其的结构一定程度上参考了GFS(HDFS),元数据服务器称之为Nameserver,实际的数据存储服务器称之为Dataserver。TFS将多个小文件合并成一个大文件,称之为block,block是真实的物理存储单元。因此,DataServer负责存储Block,而NameServer维护block与DataServer的映射。那么小文件与block的映射关系在哪里维护呢?要知道小文件的量是很大的

TFS的文件名由块号和文件号通过某种对应关系组成,最大长度为18字节。文件名固定以T开始,第二字节为该集群的编号(可以在配置项中指定,取值范围 1~9)。余下的字节由Block ID和File ID通过一定的编码方式得到。文件名由客户端程序进行编码和解码

如图所示:

从上图可以看到,最终的文件名是包含了block id信息的的,那么如何利用这个blockid信息呢,如下图所示:

当需要根据文件名获取文件内容的时候,TFS的客户端,首先通过文件名解析出Block id与File id,然后从NameServer上根据Block id查询block所在的DataServer。然后从DataServer上根据Block id拿到对应的block,在根据file id从block中找到对应的文件。

TFS用于存储淘宝大量的小文件,比如商品的各种尺寸的小图片,这个数量是非常大的,如果用单独的元数据服务器维护文件名与文件信息的映射,这个量是非常大的。而使用携带block id信息的文件名,很好规避了这个问题。但使用这种携带分区信息的ID时,需要考虑数据在分区之间的迁移情况,ID一般来说使不能变的,因此ID映射的应该是一个逻辑分区,而不是真正的物理分区。

总结

本文介绍了分布式系统中,全局唯一ID的生成方法。ID主要有两种类型,一种是数字自增ID,如flicker的解决方案;另一种是携带时间、机器信息的组合ID,如uuid。分布式系统中,好的全局ID生成算法首先是需要避免单点,如果不需要中心化服务的话更好;另外,携带时间信息、分片信息的ID更加实用。

本文分享自微信公众号 - IT技术精选文摘(ITHK01)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-10-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 面试题:分库分表之后,id 主键如何处理?

    其实这是分库分表之后你必然要面对的一个问题,就是 id 咋生成?因为要是分成多个表之后,每个表都是从 1 开始累加,那肯定不对啊,需要一个全局唯一的 id 来支...

    用户1263954
  • MySQL 内核深度优化

    用户1263954
  • Netty高性能之道

    1. 背景 1.1. 惊人的性能数据 最近一个圈内朋友通过私信告诉我,通过使用Netty4 + Thrift压缩二进制编解码技术,他们实现了10W TPS(1K...

    用户1263954
  • spring3+mbatis3开发实例

    最近一直在深入了解struts2,spring,hibernate以及mybatis框架,通过查看这些框架的源码和官方文档,发现自己对于这些框架的原理,使用有了...

    py3study
  • uniapp带参数跳转,新页面接收参数

    1:index.vue的页面,在按钮上绑定点击事件,将所要传递的参数放在点击事件的方法里面。

    祈澈菇凉
  • 那些可以绕过WAF的各种特性

    在攻防实战中,往往需要掌握一些特性,比如服务器、数据库、应用层、WAF层等,以便我们更灵活地去构造Payload,从而可以和各种WAF进行对抗,甚至绕过安全防御...

    Bypass
  • 记一次mysql优化

    今天在技术经理的现场优化中,把一条需要40000ms的sql语句优化到9ms左右,将近提高4500多倍的速度

    botkenni
  • MYSQL的索引优化 顶

    当一个表的数据量较大时,我们需要对这个表做优化,除了分表分库以外,最常见的就是索引优化了,那做索引优化的原则是什么呢?

    算法之名
  • 通过错误的sql来测试推理sql的解析过程(二) (r8笔记第7天)

    之前总结过一篇 通过错误的sql来测试推理sql的解析过程 也算是以毒攻毒,当然也分析出来一些有意思的内容来,让原本看起来枯燥的内容有了更多的实践意义。 ...

    jeanron100
  • myBatis实例

    用户1112962

扫码关注云+社区

领取腾讯云代金券