id 生成器介紹_ZenDei技術網路在線

背景介紹在一般的業務場景中, 初始的時候簡單的自增數(比如MySQL 自增鍵)就可以很好的滿足需求, 不過隨著業務的發展和驅動, 尤其是在分散式的場景中, 如何生成全局的唯一 id 便成了需要慎重考慮的事情. 業務之間如何協調, 生成的序列是否還有其它需求等都需要重新設計, 下文則介紹生成唯一 i ...

背景介紹

在一般的業務場景中, 初始的時候簡單的自增數(比如MySQL 自增鍵)就可以很好的滿足需求, 不過隨著業務的發展和驅動, 尤其是在分散式的場景中, 如何生成全局的唯一 id 便成了需要慎重考慮的事情. 業務之間如何協調, 生成的序列是否還有其它需求等都需要重新設計, 下文則介紹生成唯一 id 的不同方式以及各自適用的場景.

1. twitter Snowflake 介紹

原文見: announcing-snowflake twitter 碰到的問題 twitter 使用 MySQL 存儲線上的數據, 不過隨著業務的發展, 現在已經成為了很大的資料庫集群. 由於種種原因, 在一些細節方面, twitter 使用分散式資料庫 Cassandra 或水平拆分 MySQL 來更好的服務全局的博文及帖子. Cassandra 並沒有內置類似 MySQL 自增主鍵的功能, 這也意味著隨著業務的擴張, 使用 Cassandra 很難在序列 id 方面提供一個通用的解決方案(one-size-fits-all solution), 這個問題在水平拆分 MySQL 的架構中也同樣存在. 基於這些問題, twitter 提出了以下需求:

1. 每秒生成上萬的 id 號, 並且能以高可用方式提供服務;
2. 由於業務的關係只能選擇非協調(業務無關)的方式生成 id 號;
3. id 號大致上要能排序, 這意味著同時發表 A 和 B 兩篇文章, 他們的 id 號應該是相近的.
4. id 號應該是 64 位大小.

可選的解決方案 twitter 也考慮了幾種方式來滿足上述的需求:

1. 基於 MySQL 的服務;
2. UUID 方式;
3. zookeeper sequential nodes;

基於 MySQL-based ticket servers 本質上通過自增 id 來實現, 不過這種方式在程式不重構的情況下很難保證 id 號按順序生成, 也不能按照時間排序; 而 UUID 則是 128 位的, 也有概率發生衝突, 同樣也沒有時間戳; 而 zookeeper 的時序節點則難以滿足上萬每秒的性能. twitter 的解決方案 為了生成能夠大致上可以排序的 64 位 id 號, twitter 提出以三個欄位組合生成 id 號: 時間戳(timestamp), worker(工作號), 序列數(sequence number). 序列數和工作號是在每個線程連接 zookeeper 後就確定的, 詳細的代碼見: snowflake 這種方式有幾點好處, 首先, 開始部分都是時間戳, 可以很方便的建立索引; 其次, 同一個線程下發表的文章或帖子可以進行排序, 而且 id 號臨近; 另外, 整體上看 id 號是近似排序的. id 號實現 twitter 的 id 號以如下部分組合實現, 構成63位的整數, 最高位為0:

id is composed of:
   time - 41 bits (millisecond precision w/ a custom epoch gives us 69 years)
   configured machine id - 10 bits - gives us up to 1024 machines
   sequence number - 12 bits - rolls over every 4096 per machine (with protection to avoid rollover in the same ms)

機器 id 共占 10 bit(5 bit 數據中心id, 5 bit 工作id), 最大即為 1024; 時間戳精確到毫秒, 占 41 bit(比如1490842567501 精確到了毫秒), 每次生成新的 id 的時候需要獲取當前的系統時間, 再分兩種情況生成 sequence number:

如果當前的時間和前一個已生成的時間相同(同一毫秒), 就用前一個 id 的 `sequence number + 1` 作為新的 sequence number; 如果本毫秒的 id 用完就等到下一毫秒繼續(等待過長中不能分配新的id);

如果當前的時間比前一個 id 的時間大, 隨機生成一個初始的 sequence number 作為本毫秒內的第一個 sequence number;

整個過程中, 只在 worker 啟動的時候會對外部有依賴(從 zookeeper 獲取 worker 號), 以後就可以獨立工作, 做到了去中心化; 另外如果是異常情況下:

獲取的當前時間小於上一個 id 的時間, twitter 的做法則是繼續獲取當前機器的時間直到獲取到更大的時間才能繼續工作(等待的過程中不能分配新的 id);

從這點看如果機器的時鐘偏差較大, 整個系統則不能正常工作, snowflake 文檔中也做了相應的提示, 使用 ntp 同步系統時鐘, 同時將 ntp 配置成不會向後調整的模式, 詳見: Time_synchronization

System Clock Dependency

 You should use NTP to keep your system clock accurate.  Snowflake protects from non-monotonic clocks, i.e. clocks that run
 backwards.  If your clock is running fast and NTP tells it to repeat a few milliseconds, snowflake will refuse to generate ids
 until a time that is after the last time we generated an id. Even better, run in a mode where ntp won't move the clock
 backwards. See http://wiki.dovecot.org/TimeMovedBackwards#Time_synchronization for tips on how to do this.

參見: Unique-ID

2. last_insert_id 方式

詳見: flickr 如果使用 MySQL 作為序列號的服務, 就不能使用 uuid, 這個問題同 snowflake 中介紹的, 也不能使用 md5, guid 等, 這些太散列, 不利於索引的創建和查找; flickr 的文章的介紹了使用 MySQL 自增id 的方式實現序列號的生成. 這種方式也是很多中小業務使用的方式, 不過很多都使用了 InnoDB 引擎: 創建 ticket 相關表:

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

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

replace 語句在存在唯一鍵或主鍵衝突的時候, 會加一個互斥的 next-key 鎖, 以免在查詢或索引掃描的時候出現幻讀的現象, 詳見: innodb-locks-set 但是這也會引來一個問題, 多個線程併發更新的時候容易產生死鎖, MyISAM 引擎的效果較好, 但不利於 innobackupex 線上備份, 記錄很少的情況下可以改為 MyISAM 引擎. 單一業務使用這種方式是個很好的解決方案. 如果需要更好的性能可以採用雙主的架構, 不過需要設置好各自的自增鍵的偏移值和步長.

3. MariaDB Sequence 介紹

MariaDB 10.0.3 版本引入了新的引擎: Sequence , 不同於 postgresql, MariaDB 的 sequence 比較特殊, 它是一個虛擬的, 臨時的自增序列, 會話結束後序列便消失, 沒有持久化功能, 也不能被其它表像自增主鍵那樣引用. sequence 根據表的名字確定邊界和自增值. 如何使用

邊界和自增值由表名決定, 生成 1 ~ 5 的序列

SELECT * FROM seq_1_to_5;
+-----+
| seq |
+-----+
|   1 |
|   2 |
|   3 |
|   4 |
|   5 |
+-----+

以 3 為步長生成 1 ~ 15 的序列

SELECT * FROM seq_1_to_15_step_3;
+-----+
| seq |
+-----+
|   1 |
|   4 |
|   7 |
|  10 |
|  13 |
+-----+

遞減生成序列

SELECT * FROM seq_5_to_1_step_2;
+-----+
| seq |
+-----+
|   5 |
|   3 |
|   1 |
+-----+

note: 如果啟用了 sequence 引擎, 新建的表名不能和序列的表名衝突, 臨時表可以和序列表名一樣 MariaDB sequence 誤區 MariaDB sequence 引擎不像 PostgreSQL 和 FirebirdSQL 的序列生成器, 生存期僅為當前語句的執行時間, 沒有持久化功能, 也沒有 nextval 相關的功能. sequence 也不能生成負數序列, 在達到最大/最小邊界的時候不能輪詢(類似 PostgreSQL 序列生成器的 CYCLE 選項). MariaDB sequence 使用場景 詳細使用參見 mariadbs-sequence

1. 找出列中的空洞行
2. 生成組合數
3. 生成兩個數的公約數
4. 生成排序的字元
5. 生成排序的日期時間等

4. postgresql 序列生成器

postgresql 自帶的序列生成器能夠很好的實現序列數的需求, 類似 MySQL 的 last_insert_id 方式. 不過 postgresql 的序列包含以下特性:

1. 序列可以用於表中的多個欄位;
2. 序列可以被多個表共用;

創建序列見: sql-createsequence 語法較豐富, 支持很多參數, 可以設置序列的起始值, 上限值, cache 和是否迴圈等. 序列函數見: functions-sequence 操作序列的函數包括

currval(regclass)                 bigint   返回最近一次用 nextval 獲取的指定序列的數值
lastval()                         bigint   返回最近一次用 nextval 獲取的任何序列的數值
nextval(regclass)                 bigint   遞增序列並返回新值
setval(regclass, bigint)          bigint   設置序列的當前數值
setval(regclass, bigint, boolean) bigint  設置序列的當前數值及 is_called 標誌

程式調用 currval 函數之前, 都需要執行過 nextval 函數.如果 setval 的 is_called 為 false, 則下次調用 nextval 函數將範圍其聲明的值, 再次調用 nextval 才會開始遞增序列. regclass 類型為相關函數的參數, 這裡即序列的名稱. 如下所示:

cztest=# create sequence seq1;
CREATE SEQUENCE
cztest=# select nextval('seq1');
 nextval 
---------
       1
(1 row)

cztest=# select nextval('seq1');
 nextval 
---------
       2
(1 row)

cztest=# select currval('seq1');
 currval 
---------
       2
(1 row)

cztest=# select setval('seq1', 1, false);
 setval 
--------
      1
(1 row)

cztest=# select nextval('seq1');
 nextval 
---------
       1
(1 row)

cztest=# select nextval('seq1');
 nextval 
---------
       2
(1 row)

使用序列生成器經常碰到的問題

事務回滾後, 序列不會回滾
序列的範圍基於 bigint 運算, 其範圍不超過 8 位元組的整數範圍.一些老的系統不支持 8 位元組的編譯器則採用普通的 4 位元組 int 運算.
序列達到上限後, 預設不加 CYCLE 選項, 則會報錯, 不允許生成序列, 如果加了 CYCLE 選擇, 則從開始值重新生成.
如果 cache 大於 1, 意味著該會話一次取多個序列, 每次訪問序列對象的過程中都將分配並緩存隨後的序列值, 並且相應的增加序列對象的 last_value. 從這點看 cache 越大意味著序列的性能越高. 不過同一個事務中隨後的 cache - 1 次 nextval 將只返回預先分配的值, 在會話結束前沒有使用剩下的值, 會導致序列里出現空洞(不連續). 另外如果有多個會話併發操作同一個序列生成器, 在業務層面來看可能會產生無序的問題, 在 cache 大於 1 的時候, 只能保證 nextval 值唯一, 不能保證順序生成; 最後, 如果在序列上執行 setval, 則其它會話不會發覺, 直到用光緩存的數為止.

總結

在上述介紹的四種 id 生成方式中, MariaDB 的 sequence 不適合序列生成器的需求. 很多中小業務使用的都是基於 MySQL 的 last_insert_id 方式. 這種方式在單一業務中使用方便, 有多少業務就創建多少對應的表, 不太使用具有分散式特性的業務. 另外很多開源的工具, 如 idgo 就是基於該方式, 只是提供了 redis 協議相容的介面, 創建多個序列及意味著映射了多個 MySQL 表, 在併發較大的場景下不能避免死鎖的發生. 而 PostgreSQL 的序列生成器則是內置的功能, 有很豐富的操作函數, 併發方面比起 MySQL 方式有較好的性能, 比較流行的開源工具 postgrest 和 prest 都提供了 http 介面, 已有的程式改造起來也比較輕鬆方便. snowflake 方式則比較適合分散式場景的業務, 對時間依賴較強的業務也可以使用該方式, 另外這種方式在性能方面應該是最好的. 已有的開源工具如 sony 或 goSnowFlake 都做了比較好的實現, 以 http 介面對外服務, 程式改造起來也比較方便. 不過與上述的兩種方式相比, 開源的工具並未實現持久化和高可用的功能, 在服務中斷的情況下難以繼續生成相應的序列, 需要我們做相應的二次開發.