為了標識一段數據，通常我們會為其指定一個唯一id，比如利用MySQL資料庫中的自增主鍵。但是當數據量非常大時，僅靠資料庫的自增主鍵是遠遠不夠的，並且對於分散式資料庫只依賴MySQL的自增id無法滿足全局唯一的需求。因此，產生了多種解決方案，如UUID，SnowFlake等。下文將介紹Vitess是... ...

為了標識一段數據，通常我們會為其指定一個唯一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值，增加本地緩存數量的方式來調節。

作者：京東零售金越

來源：京東雲開發者社區轉載請註明來源

Vitess全局唯一ID生成的實現方案

Vitess全局唯一id生成

VtDriver實現方式

事務+鎖表 or CAS ？