分布式架构技术
RPC

分布式-全局一致性id

全局ID的要求

  • 全局唯一性
  • 有序的递增性
  • 高可用性
  • 时间上的特性

全局ID的实现方式

  • UUID，32个字符， 4个横线
1
8 - 4-4-4- 12

​ UUID.randomUUID.toString();

​ 基于时间的UUID(time & MAC)

​ UUID(time&POSIX UID或GID)

​ 随机数的UUID

​ UUID(SHA1)

  • 数据库
1
2
3
4
create table sequence(
   id int auto_increment,
   b_id  int  unique_key
)
1
2
3
4
begin
 replace into sequence(b_id) values();
 select LAST_INSERT_ID();
commit;

  • redis/mongdb

    increBy / incr

    ObjectId

3. 雪花算法

3.1 介绍

使用64位长整型表示id

雪花算法

  1. 1bit，不用，因为二进制中最高位是符号位，1表示负数，0表示正数。生成的id一般都是用整数，所以最高位固定为0。
  2. 41bit-时间戳，用来记录时间戳，毫秒级。
    • 41位可以表 2^{41}-1 个数字
    • 如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至 2^{41}-1，减1是因为可表示的数值范围是从0开始算的，而不是1。
    • 也就是说41位可以表示2^{41}-1个毫秒的值，转化成单位年则是(2^{41}-1) / (1000 60 60 24 365) = 69年
  3. 10bit-工作机器id，用来记录工作机器id。
    • 可以部署在 2^{10} = 1024 个节点，包括5位datacenterId和5位workerId
    • 5位（bit）可以表示的最大正整数是2^{5}-1 = 31，即可以用0、1、2、3、….31这32个数字，来表示不同的datecenterId或workerId
  4. 12bit-序列号，序列号，用来记录同毫秒内产生的不同id。
    • 12位（bit）可以表示的最大正整数是2^{12}-1 = 4095，即可以用0、1、2、3、….4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号。

由于在Java中64bit的整数是long类型，所以在Java中SnowFlake算法生成的id就是long来存储的。

SnowFlake可以保证：

  1. 所有生成的id按时间趋势递增
  2. 整个分布式系统内不会产生重复id（因为有datacenterId和workerId来做区分）

3.2 实现

4. 美团leaf算法

4.1 leaf-snowflake

  • snowflake算法：改造时钟回拨的问题

4.2 leaf-segment

每次取优化为批量取

为了防止网络抖动，使用双buffer存储号段

5. 百度UIDGenerator

snowflake算法(改造版本)