193 阿裏雲技術社區[雲棲]

分片(Sharding)的全局ID生成

這裏最後redis生成ID的文章已經過時，新的請參考： https://blog.csdn.net/hengyunabc/article/details/44244951

前言

數據在分片時，典型的是分庫分表，就有一個全局ID生成的問題。單純的生成全局ID並不是什麼難題，但是生成的ID通常要滿足分片的一些要求：

不能有單點故障。
以時間為序，或者ID裏包含時間。這樣一是可以少一個索引，二是冷熱數據容易分離。
可以控製ShardingId。比如某一個用戶的文章要放在同一個分片內，這樣查詢效率高，修改也容易。
不要太長，最好64bit。使用long比較好操作，如果是96bit，那就要各種移位相當的不方便，還有可能有些組件不能支持這麼大的ID。

先來看看老外的做法，以時間順序：

flickr

flickr巧妙地使用了mysql的自增ID，及replace into語法，十分簡潔地實現了分片ID生成功能。

首先，創建一個表：

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

使用上麵的sql可以得到一個ID：

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

因為使用了replace into的語法，實際上，Tickets64這個表裏的數據永遠都是這樣的：

+-------------------+------+
| id                | stub |
+-------------------+------+
| 72157623227190423 |    a |
+-------------------+------+

那麼如何解決單點故障呢？

很簡單，利用mysql的自增ID即可。比如有兩台ID生成服務器，設置成下麵即可：

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

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

優點：

簡單可靠。

缺點：

ID隻是一個ID，沒有帶入時間，shardingId等信息。

twitter

twitter利用zookeeper實現了一個全局ID生成的服務snowflake，https://github.com/twitter/snowflake，可以生成全局唯一的64bit ID。

生成的ID的構成：

時間--用前麵41 bit來表示時間，精確到毫秒，可以表示69年的數據
機器ID--用10 bit來表示，也就是說可以部署1024台機器
序列數--用12 bit來表示，意味著每台機器，每毫秒最多可以生成4096個ID

優點：

充分把信息保存到ID裏。

缺點：

結構略複雜，要依賴zookeeper。

分片ID不能靈活生成。

instagram

instagram參考了flickr的方案，再結合twitter的經驗，利用Postgres數據庫的特性，實現了一個更簡單可靠的ID生成服務。

instagram是這樣設計它們的ID的：

使用41 bit來存放時間，精確到毫秒，可以使用41年。
使用13 bit來存放邏輯分片ID。
使用10 bit來存放自增長ID，意味著每台機器，每毫秒最多可以生成1024個ID

以instagram舉的例子為說明：
假定時間是September 9th, 2011, at 5:00pm，則毫秒數是1387263000（直接使用係統得到的從1970年開始的毫秒數）。那麼先把時間數據放到ID裏：
id = 1387263000 << (64-41)
再把分片ID放到時間裏，假定用戶ID是31341，有2000個邏輯分片，則分片ID是31341 % 2000 -> 1341：
id |= 1341 << (64-41-13)
最後，把自增序列放ID裏，假定前一個序列是5000,則新的序列是5001：
id |= (5001 % 1024)
這樣就得到了一個全局的分片ID。

下麵列出instagram使用的Postgres schema的sql：

REATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$
DECLARE
    our_epoch bigint := 1314220021721;
    seq_id bigint;
    now_millis bigint;
    shard_id int := 5;
BEGIN
    SELECT nextval('insta5.table_id_seq') %% 1024 INTO seq_id;

    SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis;
    result := (now_millis - our_epoch) << 23;
    result := result | (shard_id << 10);
    result := result | (seq_id);
END;
$$ LANGUAGE PLPGSQL;

則在插入新數據時，直接用類似下麵的SQL即可（連請求生成ID的步驟都省略了！）：

CREATE TABLE insta5.our_table (
    "id" bigint NOT NULL DEFAULT insta5.next_id(),
    ...rest of table schema...
)

即使是不懂Postgres數據庫，也能從上麵的SQL看出個大概。把這個移植到mysql上應該也不是什麼難事。

缺點：

貌似真的沒啥缺點。

優點：

充分把信息保存到ID裏。

充分利用數據庫自身的機製，程序完全不用額外處理，直接插入到對應的分片的表即可。

使用redis的方案

站在前人的肩膀上，我想到了一個利用redis + lua的方案。

首先，lua內置的時間函數不能精確到毫秒，因此先要修改下redis的代碼，增加currentMiliseconds函數，我偷懶，直接加到math模塊裏了。

修改redis代碼下的scripting.c文件，加入下麵的內容：

#include <sys/time.h>

int redis_math_currentMiliseconds (lua_State *L);

void scriptingInit(void) {
    ...
    lua_pushstring(lua,"currentMiliseconds");
    lua_pushcfunction(lua,redis_math_currentMiliseconds);
    lua_settable(lua,-3);

    lua_setglobal(lua,"math");
    ...
}

int redis_math_currentMiliseconds(lua_State *L) {
    struct timeval now;
    gettimeofday(&now, NULL);
    lua_pushnumber(L, now.tv_sec*1000 + now.tv_usec/1000);
    return 1;
}

這個方案直接返回三元組（時間，分片ID，增長序列），當然Lua腳本是非常靈活的，可以自己隨意修改。

時間：redis服務器上的毫秒數
分片ID：由傳遞進來的參數KEYS[1]%1024得到。
增長序列：由redis上"idgenerator_next_" 為前綴，接分片ID的Key用incrby命令得到。

例如，用戶發一個文章，要生成一個文章ID，假定用戶ID是14532，則

time <-- math.currentMiliseconds();
shardindId  <-- 14532 % 1024;     //即196
articleId <-- incrby idgenerator_next_196 1  //1是增長的步長

用lua腳本表示是：

local step = redis.call('GET', 'idgenerator_step');
local shardId = KEYS[1] % 1024;
local next = redis.call('INCRBY', 'idgenerator_next_' .. shardId, step);
return {math.currentMiliseconds(), shardId, next};

“idgenerator_step"這個key用來存放增長的步長。

客戶端用eval執行上麵的腳本，得到三元組之後，可以自由組合成64bit的全局ID。

上麵隻是一個服務器，那麼如何解決單點問題呢？

上麵的“idgenerator_step"的作用就體現出來了。

比如，要部署三台redis做為ID生成服務器，分別是A,B,C。那麼在啟動時設置redis-A下麵的鍵值：

idgenerator_step = 3
idgenerator_next_1, idgenerator_next_2, idgenerator_next_3 ... idgenerator_next_1024 = 1

設置redis-B下麵的鍵值：

idgenerator_step = 3
idgenerator_next_1, idgenerator_next_2, idgenerator_next_3 ... idgenerator_next_1024 = 2

設置redis-C下麵的鍵值：

idgenerator_step = 3
idgenerator_next_1, idgenerator_next_2, idgenerator_next_3 ... idgenerator_next_1024 = 3

那麼上麵三台ID生成服務器之間就是完全獨立的，而且平等關係的。任意一台服務器掛掉都不影響，客戶端隻要隨機選擇一台去用eval命令得到三元組即可。

我測試了下單台的redis服務器每秒可以生成3萬個ID。那麼部署三台ID服務器足以支持任何的應用了。

測試程序見這裏：

https://gist.github.com/hengyunabc/9032295

缺點：

如果不熟悉lua腳本，可能定製自己的ID規則等比較麻煩。

注意機器時間不能設置為自動同步的，否則可能會因為時間同步，而導致ID重複了。

優點：

非常的快，而且可以線性部署。

可以隨意定製自己的Lua腳本，生成各種業務的ID。

其它的東東：

MongoDB的Objectid，這個實在是太長了要12個字節：

ObjectId is a 12-byte BSON type, constructed using:

a 4-byte value representing the seconds since the Unix epoch,
a 3-byte machine identifier,
a 2-byte process id, and
a 3-byte counter, starting with a random value.

總結：

生成全局ID並不很難實現的東東，不過從各個網絡的做法，及演進還是可以學到很多東東。有時候一些簡單現成的組件就可以解決問題，隻是缺少思路而已。

參考：

https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

https://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram

https://github.com/twitter/snowflake/

https://docs.mongodb.org/manual/reference/object-id/

https://www.redisdoc.com/en/latest/script/eval.html redis腳本參考

最後更新：2017-04-03 12:55:06

分片(Sharding)的全局ID生成

這裏最後redis生成ID的文章已經過時，新的請參考： https://blog.csdn.net/hengyunabc/article/details/44244951

前言

flickr

twitter

instagram

使用redis的方案

其它的東東：

總結：

參考：

上一篇： Git 合並遠程分支

下一篇：設計模式之建造者模式與工廠方法模式

相關內容

熱門內容

最新內容

分片(Sharding)的全局ID生成

這裏最後redis生成ID的文章已經過時，新的請參考： https://blog.csdn.net/hengyunabc/article/details/44244951

前言

flickr

twitter

instagram

使用redis的方案

其它的東東：

總結：

參考：

上一篇： Git 合並遠程分支

下一篇： 設計模式之建造者模式與工廠方法模式

相關內容

熱門內容

最新內容

下一篇：設計模式之建造者模式與工廠方法模式