<small id='oilCK0Fsw'></small> <noframes id='ij0c'>

  • <tfoot id='hRLb51lCy'></tfoot>

      <legend id='otazRQHw'><style id='buM5Y8qo'><dir id='rwCoEznTil'><q id='l9aKmQLT'></q></dir></style></legend>
      <i id='Nwf7'><tr id='KYbhM'><dt id='osvn'><q id='GlFDYwIi'><span id='npNlRkMtE'><b id='eI0DfCSH'><form id='0HCyq1'><ins id='YP6w3nA5u'></ins><ul id='jSNm'></ul><sub id='ZwKtWT'></sub></form><legend id='r9exUsJFPp'></legend><bdo id='Ik6gO5n0'><pre id='7R2Tz8pPW'><center id='jTe58NI2X'></center></pre></bdo></b><th id='OVFQ8h'></th></span></q></dt></tr></i><div id='TK1su'><tfoot id='Ktvq'></tfoot><dl id='mdNG4gLIT0'><fieldset id='ncC2bm'></fieldset></dl></div>

          <bdo id='57n9qRUJj4'></bdo><ul id='4p6iVH2o'></ul>

          1. <li id='EIzR'></li>
            登陆

            一号站平台官网-仅有ID生成算法分析,看看这篇就够了

            admin 2019-12-22 225人围观 ,发现0个评论

            本文转载自腾讯技术工程

            在业务开发中,大量场景需要唯一ID来进行标识:用户需要唯一身份标识;商品需要唯一标识;消息需要唯一标识;事件需要唯一标识…等等,都需要全局唯一ID,尤其是分布式场景下。

            唯一ID有哪些特性或者说要求呢?按照我的分析有以下特性:

            • 唯一性:生成的ID全局唯一,在特定范围内冲突概率极小

            • 有序性:生成的ID按某种规则有序,便于数据库插入及排序

            • 可用性:可保证高并发下的可用性

            • 自主性:分布式环境下不依赖中心认证即可自行生成ID

            • 安全性:不暴露系统和业务的信息

            一般来说,常用的唯一ID生成方法有这些:

            UUID:

            • 基于时间戳&时钟序列生成

            • 基于名字空间/名字的散列值 (MD5/SHA1) 生成

            • 基于随机数生成

            数据库自增ID:

            • 多台机器不同初始值、同步长自增

            • 批量缓存自增ID

            雪花算法

            • 时钟回拨解决方案

            • 本文便分别对这些算法进行讲解及分析。

            UUID

            UUID全称为:Universally Unique IDentifier(通用唯一识别码),有的地方也称作GUID(Globally Unique IDentifier),实际上GUID指微软对于UUID标准的实现的实现。

            UUID算法的目的是为了生成某种形式的全局唯一ID来标识系统中的任一元素,尤其在分布式环境下,该ID需要不依赖中心认证即可自动生成全局唯一ID。

            其优势有:

            • 无需网络,单机自行生成

            • 速度快,QPS高(支持100ns级并发)

            • 各语言均有相应实现库供直接使用

            而缺点为:

            • String存储,占空间,DB查询及索引效率低

            • 无序,可读性差

            • 根据实现方式不同可能泄露信息

            1.UUID的格式

            UUID的标准形式为32个十六进制数组成的字符串,且分隔为五个部分,如:

            467e8542-2275-4163-95d6-7adc205580a9

            各部分的数字个数为:8-4-4-4-12

            2.UUID版本

            根据需要不同,标准提供了不同的UUID版本以供使用,分别对应于不同的UUID生成规则:

            • 版本1 - 基于时间的UUID:主要依赖当前的时间戳及机器mac地址,因此可以保证全球唯一性

            • 版本2 - 分布式安全的UUID:将版本1的时间戳前四位换为POSIX的UID或GID,很少使用

            • 版本3 - 基于名字空间的UUID(MD5版):基于指定的名字空间/名字生成MD5散列值得到,标准不推荐

            • 版本4 - 基于随机数的UUID:基于随机数或伪随机数生成,

            • 版本一号站平台官网-仅有ID生成算法分析,看看这篇就够了5 - 基于名字空间的UUID(SHA1版):将版本3的散列算法改为SHA1

            3.UUID各版本优缺点

            版本1 - 基于时间的UUID:

            • 优点:能基本保证全球唯一性

            • 缺点:使用了Mac地址,因此会暴露Mac地址和生成时间

            版本2 - 分布式安全的UUID:

            • 优点:能保证全球唯一性

            • 缺点:很少使用,常用库基本没有实现

            版本3 - 基于名字空间的UUID(MD5版):

            • 优点:不同名字空间或名字下的UUID是唯一的;相同名字空间及名字下得到的UUID保持重复。

            • 缺点:MD5碰撞问题,只用于向后兼容,后续不再使用

            版本4 - 基于随机数的UUID:

            • 优点:实现简单

            • 缺点:重复几率可计算

            版本5 - 基于名字空间的UUID(SHA1版):

            • 优点:不同名字空间或名字下的UUID是唯一的;相同名字空间及名字下得到的UUID保持重复。

            • 缺点:SH一号站平台官网-仅有ID生成算法分析,看看这篇就够了A1计算相对耗时

            总得来说:

            • 版本 1/2 适用于需要高度唯一性且无需重复的场景;

            • 版本 3/5 适用于一定范围内唯一且需要或可能会重复生成UUID的环境下;

            • 版本 4 适用于对唯一性要求不太严格且追求简单的场景。

            4.UUID结构及生成规则

            以版本1 - 基于时间的UUID为例先梳理UUID的结构:

            UUID为32位的十六机制数,因此实际上是16-byte (128-bit),各位分别为:

            时间值:在基于时间的UUID中,时间值是一个60位的整型值,对应UTC的100ns时间间隔计数,因此其支持支持一台机器每秒生成10M次。在UUID中,将这60位放置到了15~08这8-byte中(除了09位有4-bit的版本号内容)。

            版本号:版本号即上文所说的五个版本,在五个版本的UUID中,都总是在该位置标识版本,占据 4-bit,分别以下列数字表示:

            因此版本号这一位的取值只会是1,2,3,4,5

            变体值:表明所依赖的标准(X表示可以是任意值):

            时钟序列:在基于时间的UUID中,时钟序列占据了07~06位的14-bit。不同于时间值,时钟序列实际上是表示一种逻辑序列,用于标识事件发生的顺序。在此,如果前一时钟序列已知,则可以通过自增来实现时钟序列值的改变;否则,通过(伪)随机数来设置。主要用于避免因时间值向未来设置或节点值改变可能导致的UUID重复问题。

            节点值:在基于时间的UUID中,节点值占据了05~00的48-bit,由机器的MAC地址构成。如果机器有多个MAC地址,则随机选其中一个;如果机器没有MAC地址,则采用(伪)随机数。

            了解了基于时间的UUID结构及生成规则后,再看看其他版本的UUID生成规则:

            • 版本2 - 分布式安全的UUID:

            将基于时间的UUID中时间戳前四位换为POSIX的UID或GID,其余保持一致。

            • 版本3/5 - 基于名字空间的UUID (MD5/SHA1):

            1. 将命名空间 (如DNS、URL、OID等) 及名字转换为字节序列;

            2. 通过MD5/SHA1散列算法将上述字节序列转换为16字节哈希值 (MD5散列不再推荐,SHA1散列的20位只使用其15~00位);

            3. 将哈希值的 3~0 字节置于UUID的15~12位;

            4. 将哈希值的 5~4 字节置于UUID的11~10位;

            5. 将哈希值的 7~6 字节置于UUID的09~08位,并用相应版本号覆盖第9位的高4位 (同版本1位置);

            6. 将哈希值的 8 字节置于UUID的07位,并用相应变体值覆盖其高2位 (同版本1位置);

            7. 将哈希值的 9 字节置于UUID的06位 (原时钟序列位置);

            8. 将哈希值的 15~10 字节置于UUID的05~00位 (原节点值位置)。

            • 版本4 - 基于随机数的UUID:

            1. 生成16byte随机值填充UUID。重复机率与随机数产生器的质量有关。若要避免重复率提高,必须要使用基于密码学上的假随机数产生器来生成值才行;

            2. 将变体值及版本号填到相应位置。

            5.多版本伪码

            // 版本 1 - 基于时间的UUID:gen_uuid { struct uuid uu;
            // 获取时间戳 get_time(&clock_mid, &uu.time_low); uu.time_mid = (uint16_t) clock_mid; // 时间中间位 uu.time_hi_and_version = ((clock_mid >> 16) & 0x0FFF) | 0x1000; // 时间高位 & 版本号
            // 获取时钟序列。在libuuid中,尝试取时钟序列+1,取不到则随机;在python中直接使用随机 get_clock(&uu.clock_seq);// 时钟序列+1 或 随机数 uu.clock_seq |= 0x8000;// 时钟序列位 & 变体值
            // 节点值 char node_id[6]; get_node_id(node_id);// 根据mac地址等获取节点i一号站平台官网-仅有ID生成算法分析,看看这篇就够了d uu.node = node_id; return uu;}
            // 版本4 - 基于随机数的UUID:gen_uuid { struct uuid uu; uuid_t buf;
            random_get_bytes(buf, sizeof(buf));// 获取随机出来的uuid,如libuuid根据进程id、当日时间戳等进行srand随机
            uu.clock_seq = (uu.clock_seq & 0x3FFF) | 0x8000;// 变体值覆盖 uu.time_hi_and_version = (uu.time_hi_and_version & 0x0FFF) | 0x4000;// 版本号覆盖 return uu;}
            // 版本5 - 基于名字空间的UUID(SHA1版):gen_uuid(name) { struct uuid uu; uuid_t buf;
            sha_get_bytes(name, buf, sizeof(buf));// 获取name的sha1散列出来的uuid
            uu.clock_seq = (uu.clock_seq & 0x3FFF) | 0x8000;// 变体值覆盖 uu.time_hi_and_version = (uu.time_hi_and_version & 0x0FFF) | 0x5000;// 版本号覆盖 return uu;}

            (左滑查看完整代码)

            数据库自增ID

            数据库自增ID可能是大家最熟悉的一种唯一ID生成方式,其具有使用简单,满足基本需求,天然有序的优点,但也有缺陷:

            • 并发性不好

            • 数据库写压力大

            • 数据库故障一号站平台官网-仅有ID生成算法分析,看看这篇就够了后不可使用

            • 存在数量泄露风险

            因此这里给出两种优化方案。

            1. 数据库水平拆分,设置不同的初始值和相同的步长

            如图所示,可保证每台数据库生成的ID是不冲突的,但这种固定步长的方式也会带来扩容的问题,很容易想到当扩容时会出现无ID初始值可分的窘境,解决方案有:

            • 根据扩容考虑决定步长

            • 增加其他位标记区分扩容

            这其实都是在需求与方案间的权衡,根据需求来选择最适合的方式。

            2.批量生成一批ID

            如果要使用单台机器做ID生成,避免固定步长带来的扩容问题,可以每次批量生成一批ID给不同的机器去慢慢消费,这样数据库的压力也会减小到N分之一,且故障后可坚持一段一号站平台官网-仅有ID生成算法分析,看看这篇就够了时间。

            如图所示,但这种做法的缺点是服务器重启、单点故障会造成ID不连续。还是那句话,没有最好的方案,只有最适合的方案。

            雪花算法

            定义一个64bit的数,对指定机器 & 同一时刻 & 某一并发序列,是唯一的,其极限QPS约为400w/s。其格式为:

            64 bit分为了四部分。其中时间戳有时间上限(69年)。机器id只有10位,能记录1024台机器,常用前几位表示数据中心id,后几位表示数据中心内的机器id。序列号用来对同一个毫秒之内的操作产生不同的ID,最多4095个。

            这种结构是雪花算法提出者Twitter的分法,但实际上这种算法使用可以很灵活,根据自身业务的并发情况、机器分布、使用年限等,可以自由地重新决定各部分的位数,从而增加或减少某部分的量级。比如百度的UidGenerator、美团的Leaf等,都是基于雪花算法做一些适合自身业务的变化。

            由于雪花算法是强依赖于时间的,在分布式环境下,如果发生时钟回拨,很可能会引起id冲突的问题。解决方案有:

            • 将ID生成交给少量服务器,并关闭时钟同步。

            • 直接报错,交给上层业务处理。

            • 如果回拨时间较短,在耗时要求内,比如5ms,那么等待回拨时长后再进行生成。

            • 如果回拨时间很长,那么无法等待,可以匀出少量位(1~2位)作为回拨位,一旦时钟回拨,将回拨位加1,可得到不一样的ID,2位回拨位允许标记三次时钟回拨,基本够使用。如果超出了,可以再选择抛出异常。

            方案对比

            可以发现,常用的分布式唯一ID生thursday成思路基本是利用一个长串数字或字符串,将其分割成多个部分,分别记录时间信息、机器/名字信息、随机信息、序列信息等。时间信息部分决定了该策略能使用的时长,机器一号站平台官网-仅有ID生成算法分析,看看这篇就够了/名字信息支持了分布式环境下的独自生成唯一ID与识别能力,序列信息保证了事件的顺序记录以及同一时间单位下的并发数,而随机信息则加大了ID整体的不可识别性。

            实际上如果现有的方法依然不能满足,我们完全可以依据自身业务和发展需求,来自行决定使用何种策略生成唯一ID。各种方案都有其优缺点,技术的使用没有绝对的好坏之分,主要在于是否适合使用场景:

            • 要求生成全局唯一且不会重复ID,不关心顺序 —— 使用基于时间的UUID(如游戏聊天室中不同用户的身份ID)

            • 要求生成唯一ID,具有名称不可变性,可重复生成 —— 使用基于名称哈希的UUID(如基于不可变信息生成的用户ID,若不小心删除,仍可根据信息重新生成同一ID)

            • 要求生成有序且自然增长的ID —— 使用数据库自增ID(如各业务操作流水ID,高并发下可参考优化方案)

            • 要求生成数值型无序定长ID —— 使用雪花算法(如对存储空间、查询效率、传输数据量等有较高要求的场景)

            对于最初我们定义的唯一ID特性,各方案的对比如下:

            从冲突率、QPS和算法时间复杂度来比较的话:

            参考

            UUID算法分析

            关于UUID的二三

            UUID百度百科

            UUID唯一资源命名空间的来龙去脉

            UUID是如何保证唯一性的?

            如果再有人问你分布式 ID,这篇文章丢给他

            分布式唯一ID的几种生成方案

            UidGenerator-百度

            Leaf——美团点评分布式ID生成系统

            分布式系统:Lamport 逻辑时钟

            QQ群二维码如下,个人微信号:jeanron100, 添加请注明:姓名+地区+职位,否则不予通过

            请关注微信公众号
            微信二维码
            不容错过
            Powered By Z-BlogPHP