分布式ID生成解决方式

      在分布式系统中经常遇到需要获取唯一ID的情况,在保证唯一的前提下一定要高性能,并且要相对占用很少的空间。本章将介绍常用的ID生成方式,并通过代码实现:

  一、基于数据库发号器

       这种方式比较常用,每一次都请求数据库,通过数据库的自增ID来获取全局唯一ID,对于小系统来说,这是一个简单有效的方案,不过也就不符合讨论情形中的高并发的场景。首先,数据库自增ID需要锁表 而且,这种的生成方式强依赖于数据库,每次获取ID都需要经过一次数据库的调用,性能损耗很大(但可以基于步长方式来补偿,这样会导致Client出现宕机获取其他原因,会丢失这些步长,使至ID不连贯)。

     优点:ID连贯、服务稳定

     缺点:基于数据库性能有瓶颈, 随者业务发展,需要对原有的数据进行重新分库分表的时候,可能会产生主键冲突,这影响了系统的平滑扩容.

     我们公司现有的方案就是基于这种方式来实现的:

 

blob.png

     实现方式:如参考Hibernate TableGenerator 类实现方式:

     将当前主键的值单独保存到一个数据库的表中,主键的值每次都是从指定的表中查询来获得,这种生成主键的方式也是很常用的。这种方法生成主键的策略可以适用于任何的数据库,不必担心不同数据库不兼容造成的问题。 

CREATE TABLE  tb_generator (
  id int(20) unsigned NOT NULL auto_increment,
  gen_name varchar(255) NOT NULL,
  gen_value int(20) NOT NULL,
  PRIMARY KEY  (id)
)
INSERT INTO tb_generator ( gen_name ,gen_value ) VALUES ( 'CUSTOMER_PK',1);
INSERT INTO tb_generator ( gen_name ,gen_value ) VALUES ( 'CONTACT_PK',100);

    现在有另外两个表customer和contact,它们每次新建记录时生成主键的值分别“CUSTOMER_PK”所对应的value值加 1,“CONTACT_PK”所对应的value值加1。

  下面就来具体看一下如何来配置主键的生成策略,以配置“customer”表为例,步骤如下。

  (1)在Entity标记主键的位置,指定主键生成策略为“GenerationType.TABLE”,具体设置如下。

@Entity
@Table(name = "customer")
public final class CustomerEO implements java.io.Serializable {
         private Integer id;
         @Id
         @GeneratedValue(strategy = GenerationType.TABLE)
         public Integer getId() {
                   return this.id;
         }
         public void setId(Integer id) {
                   this.id = id;
         }
}

  (2)指定生成主键策略的名称,例如这里命名为“customer_gen”。

   @Id
         @GeneratedValue(strategy = GenerationType.TABLE,generator="customer_gen")
         public Integer getId() {
                   return this.id;
         }

    (3)使用@ TableGenerator标记定义表生成策略的具体设置,代码如下所示。

 @Id
         @GeneratedValue(strategy = GenerationType.TABLE,generator="customer_gen")
         @TableGenerator(name = "customer_gen",
                            table="tb_generator",
                            pkColumnName="gen_name",
                            valueColumnName="gen_value",
                            pkColumnValue="CUSTOMER_PK",
                            allocationSize=1 //步长
         )
         public Integer getId() {
                   return this.id;
         }

 实现方式二:通过数据库函数来实现ID取号服务:

     1、创建tb_sequence表:

blob.png

– name sequence名称

– current_value 当前value

– increment 增长步长! 可理解为mycat在数据库中一次读取多少个sequence. 当这些用完后, 下次再从数据库中读取.

    2、创建数据库Function函数:

CREATE FUNCTION `seq_nextval`(seq_name VARCHAR(50)) RETURNS VARCHAR(64) CHARSET latin1
    DETERMINISTIC
BEGIN
    DECLARE retval VARCHAR(64);
    DECLARE val BIGINT;
    DECLARE inc INT;
    DECLARE seq_lock INT;
    SET val = -1;
    SET inc = 0;
    SET seq_lock = -1;
    SELECT GET_LOCK(seq_name, 15) INTO seq_lock;
    IF seq_lock = 1 THEN
      SELECT current_value + increment, increment INTO val, inc FROM tb_sequence 
      WHERE NAME = seq_name FOR UPDATE;
      IF val != -1 THEN
          UPDATE tb_sequence SET current_value = val WHERE NAME = seq_name;
      END IF;
      SELECT RELEASE_LOCK(seq_name) INTO seq_lock;
    END IF;
    SELECT CAST((val - inc + 1) AS CHAR) INTO retval;
    RETURN retval;
END$$

   3、SQL 语句执行;

insert into user_test (id, name, age, address)
values (seq_nextval('user_sequence'), Tony, 12,'广州');

    这个方式可以参考MyCat的ID生成策略;

二、UUID 方式:

     UUID生成的是length=32的16进制格式的字符串,如果回退为byte数组共16个byte元素,即UUID是一个128bit长的数字,

     一般用16进制表示。

      算法的核心思想是结合机器的网卡、当地时间、一个随即数来生成UUID。

     从理论上讲,如果一台机器每秒产生10000000个GUID,则可以保证(概率意义上)3240年不重复

优点:

    1)简单,代码方便。

    2)生成ID性能非常好,基本不会有性能问题。

    3)全球唯一,在遇见数据迁移,系统数据合并,或者数据库变更等情况下,可以从容应对。

缺点:

    1)没有排序,无法保证趋势递增。

    2)UUID往往是使用字符串存储,查询的效率比较低。

    3)存储空间比较大,如果是海量数据库,就需要考虑存储量的问题。

    4)传输数据量大

三、基于redis的分布式ID生成器

      采用redis+lua的id generato算法,可以非常方便的实现一个ID生成服务。

     利用redis的lua脚本执行功能,在每个节点上通过lua脚本生成唯一ID。 生成的ID是64位的:

使用41 bit来存放时间,精确到毫秒,可以使用41年。

使用12 bit来存放逻辑分片ID,最大分片ID是4095

使用10 bit来存放自增长ID,意味着每个节点,每毫秒最多可以生成1024个ID

比如GTM时间 Fri Mar 13 10:00:00 CST 2015 ,它的距1970年的毫秒数是 1426212000000,假定分片ID是53,自增长序列是4,则生成的ID是:

       5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 4

       redis提供了TIME命令,可以取得redis服务器上的秒数和微秒数。因些lua脚本返回的是一个四元组。

second, microSecond, partition, seq

客户端要自己处理,生成最终ID。

((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq;

      在redis-client里采用预取技术,可以保证ID的连续性,如果redis-client实例经常会重启,更甚者,可以将使用的ID dump成文件,方便重启时不必浪费ID。

blob.png

优点:速度极快,ID连续性较高

缺点:单点问题,存在不一致问题。如果主redis挂机,备redis切换成主redis。这个过程可能ID会有不一致。

资料参考:

https://github.com/hengyunabc/redis-id-generator?spm=5176.100239.blogcont6063.4.9KKxMK

四、Flicker的解决方案

      因为MySQL本身支持auto_increment操作,很自然地,我们会想到借助这个特性来实现这个功能。Flicker在解决全局ID生成方案里就采用了MySQL自增长ID的机制(auto_increment + replace into + MyISAM)。一个生成64位ID方案具体就是这样的:  

The Tickets64 schema looks like:
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

SELECT * from Tickets64 returns a single row that looks something like:
+-------------------+------+
| id                | stub |
+-------------------+------+
| 72157623227190423 |    a |
+-------------------+------+

  在我们的应用端需要做下面这两个操作,在一个事务会话里提交:

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

这样我们就能拿到不断增长且不重复的ID了。 

     到上面为止,我们只是在单台数据库上生成ID,从高可用角度考虑,接下来就要解决单点故障问题:Flicker启用了两台数据库服务器来生成ID,通过区分auto_increment的起始值和步长来生成奇偶数的ID。

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

优点:充分借助数据库的自增ID机制,提供高可靠性,生成的ID有序。

缺点:占用两个独立的MySQL实例,有些浪费资源,成本较高。

 资料参考:http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

注:之前的待的一家海淘公司的前期的ID生成方案就是参考这种方式自研的,上述TicketServer1 、 TicketServer2应用可以基于Zookeeper 来实现服务的高可用

之前的设计图:

{7DB2BA32-1CD3-411B-9E03-E9F4F4C2C9EF}.png 0.png

五、基于Snowflake  ID生成服务:

https://github.com/twitter/snowflake

1 41位的时间序列(精确到毫秒,41位的长度可以使用69年)

2 10位的机器标识(10位的长度最多支持部署1024个节点) 

3 12位的计数顺序号(12位的计数顺序号支持每个节点每毫秒产生4096个ID序号) 最高位是符号位,始终为0。

      优点:高性能,低延迟;独立的应用;按时间有序。 缺点:需要独立的开发和部署,开发的复杂度会上升,维护成本增加。

      原理

blob.png

代码思路:

/**
 * tweeter的snowflake 移植到Java:
 *   (a) id构成: 42位的时间前缀 + 10位的节点标识 + 12位的sequence避免并发的数字(12位不够用时强制得到新的时间前缀)
 *       注意这里进行了小改动: snowkflake是5位的datacenter加5位的机器id; 这里变成使用10位的机器id
 *   (b) 对系统时间的依赖性非常强,需关闭ntp的时间同步功能。当检测到ntp时间调整后,将会拒绝分配id
 */
public class IdWorker {
    private final static Logger logger = LoggerFactory.getLogger(IdWorker.class);
    private final long workerId;
    private final long epoch = 1403854494756L;   // 时间起始标记点,作为基准,一般取系统的最近时间
    private final long workerIdBits = 10L;      // 机器标识位数
    private final long maxWorkerId = -1L ^ -1L << this.workerIdBits;// 机器ID最大值: 1023
    private long sequence = 0L;                   // 0,并发控制
    private final long sequenceBits = 12L;      //毫秒内自增位
    private final long workerIdShift = this.sequenceBits;                             // 12
    private final long timestampLeftShift = this.sequenceBits + this.workerIdBits;// 22
    private final long sequenceMask = -1L ^ -1L << this.sequenceBits;                 // 4095,111111111111,12位
    private long lastTimestamp = -1L;
    private IdWorker(long workerId) {
        if (workerId > this.maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", this.maxWorkerId));
        }
        this.workerId = workerId;
    }
    public synchronized long nextId() throws Exception {
        long timestamp = this.timeGen();
        if (this.lastTimestamp == timestamp) { // 如果上一个timestamp与新产生的相等,则sequence加一(0-4095循环); 
        对新的timestamp,sequence从0开始
            this.sequence = this.sequence + 1 & this.sequenceMask;
            if (this.sequence == 0) {
                timestamp = this.tilNextMillis(this.lastTimestamp);// 重新生成timestamp
            }
        } else {
            this.sequence = 0;
        }
        if (timestamp < this.lastTimestamp) {
            logger.error(String.format("clock moved backwards.Refusing to generate id for %d milliseconds",
             (this.lastTimestamp - timestamp)));
            throw new Exception(String.format("clock moved backwards.Refusing to generate id for %d milliseconds",
             (this.lastTimestamp - timestamp)));
        }
        this.lastTimestamp = timestamp;
        return timestamp - this.epoch << this.timestampLeftShift | this.workerId << this.workerIdShift | this.sequence;
    }
    private static IdWorker flowIdWorker = new IdWorker(1);
    public static IdWorker getFlowIdWorkerInstance() {
        return flowIdWorker;
    }
    /**
     * 等待下一个毫秒的到来, 保证返回的毫秒数在参数lastTimestamp之后
     */
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = this.timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = this.timeGen();
        }
        return timestamp;
    }
    /**
     * 获得系统当前毫秒数
     */
    private static long timeGen() {
        return System.currentTimeMillis();
    }
    public static void main(String[] args) throws Exception {
        System.out.println(timeGen());
        IdWorker idWorker = IdWorker.getFlowIdWorkerInstance();
        // System.out.println(Long.toBinaryString(idWorker.nextId()));
        System.out.println(idWorker.nextId());
        System.out.println(idWorker.nextId());
    }
}

资料参考:https://github.com/yuck0419/snowflake4j

六、基于Zookeeper方式

     zookeeper主要通过其znode数据版本来生成序列号,可以生成32位和64位的数据版本号,客户端可以使用这个版本号来作为唯一的序列号。不过zk更应该用在读多写少的场景下。

扩展阅读:

 http://calvin1978.blogcn.com/articles/uuid.html

发表评论