Vitess全局唯一ID生成的实现方案 | 京东云技术团队

京东云开发者
• 阅读 301

为了标识一段数据,通常我们会为其指定一个唯一id,比如利用MySQL数据库中的自增主键。 但是当数据量非常大时,仅靠数据库的自增主键是远远不够的,并且对于分布式数据库只依赖MySQL的自增id无法满足全局唯一的需求。因此,产生了多种解决方案,如UUID,SnowFlake等。下文将介绍Vitess是如何解决这个问题的。

Vitess全局唯一id生成

在Vitess实现方案中,每个设置了全局唯一列的表,都会对应一张sequence序列表。例如对于表user,会对应一张名为user_seq的序列表,原表与序列表的关联关系会记录在元数据中。user表以及user_seq这两张表元数据信息分别如下:

user表元数据:分片键为name列,分片算法为hash;全局唯一列为id列,依赖user_seq表生成具体的值。

{
    "tables": {
        "user": {
            "column_vindexes": [
                {
                    "column": "name",
                    "name": "hash"
                }
            ],
            "auto_increment": {
                "column": "id",
                "sequence": "user_seq"
            }
        }
    }
}

user_seq表元数据:表类型标识为sequence。

{
  "tables": {
    "user_seq": {
      "type": "sequence"
    }
  }
}

所有sequence表表结构相同,如下所示:

CREATE TABLE user_seq (
    id int,
    next_id bigint,
    cache bigint,
    PRIMARY KEY (id)
) COMMENT 'vitess_sequence';

且其中只有一条id为0的数据:

mysql> select * from user_seq;
+----+---------+-------+
| id | next_id | cache |
+----+---------+-------+
|  0 |    1000 |   100 |
+----+---------+-------+

sequence表可以认为是一个分号器,cache字段表示每次发放号段的个数,next_id列表示每次发放号段的起始值**。**Vitess每个分片在初始化时会从sequence根据next_id、cache获取号段保存在VtTablet(MySQL实例前的代理服务)的内存中,当内存中号段耗尽时,再次从sequence表中获取新号段。

我们深入代码看一下具体的实现逻辑:

// 获取sequence的方法
func (qre *QueryExecutor) execNextval() (*sqltypes.Result, error) {
    // 从plan中获取inc(为要获取的id数量)以及tableName
    inc, err := resolveNumber(qre.plan.NextCount, qre.bindVars)
    tableName := qre.plan.TableName()
    t := qre.plan.Table
    t.SequenceInfo.Lock()
    defer t.SequenceInfo.Unlock()
    if t.SequenceInfo.NextVal == 0 || t.SequenceInfo.NextVal+inc > t.SequenceInfo.LastVal {
        // 在事务中运行
        _, err := qre.execAsTransaction(func(conn *StatefulConnection) (*sqltypes.Result, error) {
            // 使用select for update锁住行数据以免在计算并更新新值期间被其他线程修改
            query := fmt.Sprintf("select next_id, cache from %s where id = 0 for update", sqlparser.String(tableName))
            qr, err := qre.execSQL(conn, query, false)
            nextID, err := evalengine.ToInt64(qr.Rows[0][0])

            if t.SequenceInfo.LastVal != nextID {
                // 如果从_seq表读取得到的id值小于tablet缓存中id,则将缓存中的值更新到_seq表中
                if nextID < t.SequenceInfo.LastVal {
                    log.Warningf("Sequence next ID value %v is below the currently cached max %v, updating it to max", nextID, t.SequenceInfo.LastVal)
                    nextID = t.SequenceInfo.LastVal
                }
                t.SequenceInfo.NextVal = nextID
                t.SequenceInfo.LastVal = nextID
            }
            cache, err := evalengine.ToInt64(qr.Rows[0][1])

            // 按照cache的倍数获取到大于inc量的缓存,计算出新newLast
            newLast := nextID + cache
            for newLast < t.SequenceInfo.NextVal+inc {
                newLast += cache
            }
            // 将新的边界值更新到_seq表中
            query = fmt.Sprintf("update %s set next_id = %d where id = 0", sqlparser.String(tableName), newLast)
            _, err = qre.execSQL(conn, query, false)
            t.SequenceInfo.LastVal = newLast
        })
    }
    // 返回获取的sequence值 更新SequenceInfo
    ret := t.SequenceInfo.NextVal
    t.SequenceInfo.NextVal += inc
    return ret
}

从源码中可以看到:

  1. Vitess使用了事务内锁行(select for update)的方式保证了多线程下查询并更新序列表不会互相干扰。

  2. 如果VtTablet中自增序列值缓存不足或者号段耗尽后,从sequence表重新获取值,并更新序列表中next_id字段。

  3. 根据inc的大小,即所需ID的数量,VtTablet会以cache为最小块,从序列表中获取n*cache个数量的id缓存在内存中。

补充说明:

1. sequence表为非拆分的表。

2. 全局唯一id生成无法保证连续性。

VtDriver实现方式

在Vitess的SDK客户端方案VtDriver中,sequence的生成逻辑被封装在了MySQL驱动包本身当中,与Vitess的方案类似,对于设置了全局自增的表,其sequence的生成同样依赖于对应的序列表,序列表的结构与Vitess的序列表相同(参上),但是读取并更新字段next_id的方式使用了CAS的方案:

public long[] querySequenceValue(Vcursor vCursor, ResolvedShard resolvedShard, String sequenceTableName) throws SQLException, InterruptedException {
    // cas 重试次数限制
    int retryTimes = DEFAULT_RETRY_TIMES;
    while (retryTimes > 0) {
        // 查询_seq表中的sequence设置,其中cache为本地缓存的大小
        String querySql = "select next_id, cache from " + sequenceTableName + " where id = 0";
        VtResultSet vtResultSet = (VtResultSet) vCursor.executeStandalone(querySql, new HashMap<>(), resolvedShard, false);
        long[] sequenceInfo = getVtResultValue(vtResultSet);
        long next = sequenceInfo[0];
        long cache = sequenceInfo[1];

        // 将计算出的next_id的值尝试更新到_seq表中,如果失败则重新读取并更新,直到成功为止
        String updateSql = "update " + sequenceTableName + " set next_id = " + (next + cache) + " where next_id =" + sequenceInfo[0];
        VtRowList vtRowList = vCursor.executeStandalone(updateSql, new HashMap<>(), resolvedShard, false);
        if (vtRowList.getRowsAffected() == 1) {
            sequenceInfo[0] = next;
            return sequenceInfo;
        }
        retryTimes--;
        Thread.sleep(ThreadLocalRandom.current().nextInt(1, 6));
    }
    throw new SQLException("Update sequence cache failed within retryTimes: " + DEFAULT_RETRY_TIMES);
}

在源码中可以看到:

  1. 在整个查询并更新序列表的过程中,没有出现Vitess实现中的开启事务以及产生锁表的情况,而是使用了CAS更新的方式。

  2. 利用update user_seq set next_id=? where next_id=?执行的返回值判断是否语句是否更新成功,如果失败则重新查询next_id的值,计算新值再尝试更新, 如果出现并发争抢的情况,Vtdriver中允许最多的重试次数DEFAULT_RETRY_TIMES为100次。

VtDriver中使用sequence的方式与MySQL自增键类似,如果设置了sequence的表在插入数据的过程中,自增列没有给定具体的值,会直接从本地缓存中获取自增ID,如果无缓存或者缓存不足时,才会路由到序列表所在MySQL服务获取sequence值

事务+锁表 or CAS ?

在Vitess实现sequence的源码当中,其更新序列表的过程为:开启事务时执行select for update,使用表锁,保证多线程安全。在现实往往充满了不确定性,我们可以想象一下:如果应用锁了数据库中的表后,由于自身的性能原因等而迟迟没有执行commit操作,或者应用节点出现了宕机的情况,此时:

应用宕机后,其持有的锁不会被释放!后续任何其他连接对于该表的任何SQL都会被持续阻塞!

​VtDriver作为Vitess的客户端方案,如果其sequence实现采用事务锁的方式,由于各个应用端都会与MySQL服务直连,即各个应用获取sequence的过程都会产生锁表的行为。此时,一旦应用端由于某些原因出现锁表时长增大,甚至于应用宕机的情况,则所有应用都会由于其锁表而产生非常明显的性能下降甚至死锁。采用cas的方式使得整个过程不需要显式的开启事务,不需要锁行,自然也不存在潜在的死锁风险。当然,CAS在并发高于一定程度时会出现各个线程互相争抢资源,此时会有更新失败不断重试的情况发生,给CPU带来一定的压力,而这可以通过设置更大的cache值,增加本地缓存数量的方式来调节。

作者:京东零售 金越

来源:京东云开发者社区 转载请注明来源

点赞
收藏
评论区
推荐文章
捉虫大师 捉虫大师
2年前
如何设计一款“高可用高性能”的发号器
本文已收录https://github.com/lkxiaolou/lkxiaolou欢迎star。背景在分布式场景中,很多地方需要生成全局唯一的id,如数据库分库分表后需要用唯一id代替单机版本的自增id。发号器的基本要求是全局唯一,无论如何都不能重复某些场景下还要求单调递增,如排序需求等。网上有很多介绍发号器的文章,比如美团的《Leaf——美团点
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
MySQL使用on duplicate key update时导致主键不连续自增
使用onduplicatekeyupdate语法有时是很方便,但是会有一个影响:默认情况下,每次更新都会更新该表的自增主键ID,如果更新频率很快,会导致主键ID自增的很快,过段时间就超过数字类型的的范围了解决这个问题,有两种方式:(实际我目前使用的方式是把自增主键ID设置为bigint,也有一部分操作先查询再选择插入OR更新)方法一:拆分成两个
Wesley13 Wesley13
2年前
mysql自增id获取
mysql自增id获取使用max函数:selectmax(id)fromtablename 优点:使用方便快捷。缺点:获取的不是真正的自增id,是表中最大的Id,如果有删除数据的话,那么该值和自增id相差比较大。如果有连表数据,有可能导致数据错乱。使用LAST\_INSERT\_ID
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
2年前
mysql关于自动编号问题 转载
MySql数据库唯一编号字段(自动编号字段)在数据库应用,我们经常要用到唯一编号,以标识记录。在MySQL中可通过数据列的AUTO\_INCREMENT属性来自动生成。MySQL支持多种数据表,每种数据表的自增属性都有差异,这里将介绍各种数据表里的数据列自增属性。ISAM表如果把一个NULL插入到一个AUTO\_INCREMEN
Wesley13 Wesley13
2年前
MySql 面试开发技术点汇总
表结构设计1、为什么一定要设一个主键?答:因为你不设主键的情况下,innodb也会帮你生成一个隐藏列,作为自增主键。所以啦,反正都要生成一个主键,那你还不如自己指定一个主键,在有些情况下,就能显式的用上主键索引,提高查询效率!2、你们主键是用自增还是UUID?答:肯定答自增啊。innod
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究