为了标识一段数据，通常我们会为其指定一个唯一 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}
复制代码
从源码中可以看到：
Vitess 使用了事务内锁行（select for update）的方式保证了多线程下查询并更新序列表不会互相干扰。
如果 VtTablet 中自增序列值缓存不足或者号段耗尽后，从 sequence 表重新获取值，并更新序列表中 next_id 字段。
根据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);}
复制代码
在源码中可以看到：
在整个查询并更新序列表的过程中，没有出现 Vitess 实现中的开启事务以及产生锁表的情况，而是使用了 CAS 更新的方式。
利用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 值，增加本地缓存数量的方式来调节。
作者：京东零售 金越
来源：京东云开发者社区 转载请注明来源
评论