分布式唯一ID生成方案浅谈

见贤思齐

作者：shmilychen，腾讯IEG后台开发工程师1.分布式唯一ID特性在业务开发中，会存在大量的场景都需要唯一ID来进行标识。比如，用户需要唯一身份标识；商品需要唯一标识；消息需要唯一标识；事件需要唯一标识等等。尤其是在分布式场景下，业务会更加依赖唯一ID。分布式唯一ID的特性如下：全局唯一：必须保证生成的ID是全局性唯一的，这是分布式ID的基本要求；有序性：生成的ID需要按照某种规则有序，便于数据库的写入和排序操作；可用性：需要保证高并发下的可用性。除了对ID号码自身的要求，业务还对ID生成系统的可用性要求极高；自主性：分布式环境下不依赖中心认证即可自行生成ID；安全性：不暴露系统和业务的信息。在一些业务场景下，会需要ID无规则或者不规则。2.常用分布式唯一ID生成方案2.1.UUIDUUID（UniversallyUniqueIdentifier，即通用唯一标识码）算法的目的是生成某种形式的全局唯一ID来标识系统中的任一元素，尤其是在分布式环境下，UUID可以不依赖中心认证即可自动生成全局唯一ID。UUID的标准形式为32个十六进制数组成的字符串，且分割为五个部分，例如：467e8542-2275-4163-95d6-7adc205580a9。基于使用场景的不同，会存在以下几个不同版本的UUID以供使用，如下所示：基于时间的UUID：主要依赖当前的时间戳和机器mac地址。优势是能基本保证全球唯一性，缺点是由于使用了mac地址，会暴露mac地址和生成时间；分布式安全的UUID：将基于时间的UUID算法中的时间戳前四位替换为POSIX的UID或GID。优势是能保证全球唯一性，缺点是很少使用，常用库基本没有实现；基于随机数的UUID：基于随机数或伪随机数生成。优势是实现简单，缺点是重复几率可计算；基于名字空间的UUID（MD5版）：基于指定的名字空间/名字生成MD5散列值得到。优势是不同名字空间/名字下的UUID是唯一的，缺点是MD5碰撞问题，只用于向后兼容；基于名字空间的UUID（SHA1版）：将基于名字空间的UUID（MD5版）中国的散列算法修改为SHA1。优势是不同名字空间/名字下的UUID是唯一的，缺点是SHA1计算相对耗时。UUID的优势是性能非常高，由于是本地生成，没有网络消耗。而其也存在一些缺陷，包括不易于存储，UUID太长，16字节128位，通常以36长度的字符串表示；信息不安全，基于时间的UUID可能会造成机器的mac地址泄露；ID作为DB主键时在特定的场景下会存在一些问题。2.2.数据库自增ID数据库自增ID是最常见的一种生成ID方式。利用数据库本身来进行设置，在全数据库内保持唯一。优势是使用简单，满足基本业务需求，天然有序；缺点是强依赖DB，会由于数据库部署的一些特性而存在单点故障、数据一致性等问题。针对上面介绍的数据库自增ID的缺陷，会存在以下两种优化方案：数据库水平拆分，设置不同的初始值和相同的步长。这样可以有效的生成集群中的唯一ID，也大大降低ID生成数据库操作的负载。批量生成一批ID。这样可以将数据库的压力减小到先前的N分之一，且数据库故障后仍可继续使用一段时间。此种方法详见下面的数据库号段模式介绍。数据库自增ID方案的优势是非常简单，可利用现有数据库系统的功能实现；ID号单调自增。其缺陷包括强依赖DB，当DB异常时整个系统将处于不可用的状态；ID号的生成速率取决于所使用数据库的读写性能。2.3.Redis生成ID当使用数据库来生成ID性能不够的时候，可以尝试使用Redis来生成ID。主要使用Redis的原子操作INCR和INCRBY来实现。优势是不依赖于数据库，使用灵活，性能也优于数据库；而缺点则是可能要引入新的组件Redis，如果Redis出现单点故障问题，则会影响序号服务的可用性。2.4.Zookeeper生成ID主要是利用Zookeeper的znode数据版本来生成序列号，可以生成32位和64位的数据版本号，客户端可以使用这个版本号来作为唯一的序列号。由于需要依赖zookeeper，并且是多步调用API，如果在竞争较大的情况下，可能需要考虑使用分布式锁，故此种生成唯一ID的方法的性能在高并发的分布式环境下不甚理想。2.5.Snowflake算法snowflake(雪花算法)是一个开源的分布式ID生成算法，结果是一个long型的ID。snowflake算法将64bit划分为多段，分开来标识机器、时间等信息，具体组成结构如下图所示：snowflake算法的核心思想是使用41bit作为毫秒数，10bit作为机器的ID（比如其中5个bit可作为数据中心，5个bit作为机器ID）,12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生4096个ID），最后还有一个符号位，永远是0。snowflake算法可以根据自身业务的需求进行一定的调整。比如估算未来的数据中心个数，每个数据中心内的机器数，以及统一毫秒内的并发数来调整在算法中所需要的bit数。snowflake算法的优势是稳定性高，不依赖于数据库等第三方系统；使用灵活方便，可以根据业务需求的特性来调整算法中的bit位；单机上ID单调自增，毫秒数在高位，自增序列在低位，整个ID是趋势递增的。而其也存在一定的缺陷，包括强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务处于不可用状态；ID可能不是全局递增，虽然ID在单机上是递增的，但是由于涉及到分布式环境下的每个机器节点上的时钟，可能会出现不是全局递增的场景。3.数据库号段模式3.1.号段模式介绍号段模式是当下分布式ID生成器的主流实现方式之一，号段模式可以理解成从数据库批量获取ID，然后将ID缓存在本地，以此来提高业务获取ID的效率。例如，每次从数据库获取ID时，获取一个号段，如(1,1000]，这个范围表示1000个ID，业务应用在请求获取ID时，只需要在本地从1开始自增并返回，而不用每次去请求数据库，一直到本地自增到1000时，才去数据库重新获取新的号段，后续流程循环往复。3.2.美团Leaf-segment方案Leaf-segment号段模式是对直接用数据库自增ID充当分布式ID的一种优化，减少对数据库的访问频率。相当于每次从数据库批量的获取自增ID。Leaf-server采用了预分发的方式生成ID，即可以在DB之上挂N个Server，每个Server启动时，都会去DB拿固定长度的IDList。这样就做到了完全基于分布式的架构，同时因为ID是由内存分发，所以也可以做到很高效。接下来是数据持久化问题，Leaf每次去DB拿固定长度的IDList，然后把最大的ID持久化下来，也就是并非每个ID都做持久化，仅仅持久化一批ID中最大的那一个。其流程如下图所示：Leaf-server中缓存的号段耗尽之后再去数据库获取新的号段，可以大大地减轻数据库的压力。对max_id字段做一次update操作，updatemax_id=max_id+step，update成功则说明新号段获取成功，新的号段范围为(max_id,max_id+step]。为了解决从数据库获取新的号段阻塞业务获取ID的流程的问题，Leaf-server中采用了异步更新的策略，同时通过双buffer的方式，如下图所示。通过这样一种机制可以保证无论何时DB出现问题，都能有一个buffer的号段可以正常对外提供服务，只有DB在一个buffer的下发周期内恢复，都不会影响这个Leaf集群的可用性。3.3.滴滴Tingid方案Tinyid方案是在Leaf-segment的算法基础上升级而来，不仅支持了数据库多主节点模式，还提供了tinyid-client客户端的接入方式，使用起来更加方便。Tinyid会将可用号段加载到内存中，并在内存中生成ID，可用号段在首次获取ID时加载，如当前号段使用达到一定比例时，系统会异步的去加载下一个可用号段，以此保证内存中始终有可用号段，以便在发号服务宕机后一段时间内还有可用ID。实现原理如下所示：3.4.微信序列号生成方案微信序列号跟用户uin绑定，具有以下性质：递增的64位整形；使用每个用户独立的64位sequence的体系，而不是用一个全局的64位（或更高位）sequence，很大原因是全局唯一的sequence会有非常严重的申请互斥问题，不容易去实现一个高性能高可靠的架构。其实现方式包含如下两个关键点：1）步进式持久化：增加一个缓存中间层，内存中缓存最近一个分配出现的sequence：cur_seq，以及分配上限：max_seq；分配sequence时，将cur_seq++，与分配上限max_seq比较，如果cur_seq>max_seq，将分配上限提升一个步长max_seq+=step，并持久化max_seq；重启时，读出持久化的max_seq，赋值给cur_seq。此种处理方式可以降低持久化的硬盘IO次数，可以系统的整体吞吐量。2）分号段共享存储：引入号段section的概念，uin相邻的一段用户属于一个号段，共享一个max_seq。该处理方式可以大幅减少max_seq数据的大小，同时可以进一步地降低IO次数。微信序列号服务的系统架构图如下图所示：4.雪花模式4.1.雪花模式介绍雪花模式实现方式详见上面介绍的snowflake算法。由于雪花算法强依赖于机器时间，如果时间上的时钟发生回拨，则可能引起生成的id冲突的问题。解决该问题的方案如下所示：将ID生成交给少量服务器，然后关闭这些服务器的时钟回拨能力；当遇到时钟回拨问题时直接报错，交给上层业务来处理；如果回拨时间较短，在耗时要求范围内，比如5ms，等待回拨时长后在生成id返回给业务侧；如果回拨时间很长，无法等待，可以匀出少量位作为回拨位，一旦时间回拨，将回拨位加1，可得到不一样的ID，2位回拨可允许标记三次时钟较长时间的回拨，基本够使用。如果超过回拨次数，可以再选择报错或抛出异常。4.2.美团Leaf-snowflake方案Leaf-snowflake方案沿用snowflake方案的bit位设计，即”1+41+10+12“的方式组装ID号（正数位（占1比特）+时间戳（占41比特）+机器ID（占5比特）+机房ID（占5比特）+自增值（占12比特）），如下图所示：对于workerID的分配，当服务集群较小时，通过配置即可；当服务集群较大时，基于zookeeper持久顺序节点的特性引入zookeeper组件配置workerID。部署架构如下图所示：Leaf-snowflake方案在处理时钟回拨问题的策略如下所示：1）服务启动时在服务启动时，首先检查自己是否写过zookeeperleaf_forever节点；如果写过，则用自身系统时间与leaf_forever/${self}节点记录时间做比较，若小于则认为机器时间发生了大步长回拨，服务启动失败并告警；如果没有写过，直接创建持久节点leaf_forever/${self}，并写入自身系统时间；然后取leaf_temporary下的所有临时节点(所有运行中的Leaf-snowflake节点)的服务IP：Port，然后通过RPC请求得到所有节点的系统时间，计算sum(time)/nodeSize；如果若abs(系统时间-sum(time)/nodeSize)