分片(Sharding)的全局ID生成

骑猪看日落 2022-07-17 03:20 191阅读 0赞

转自http://blog.csdn.net/hengyunabc/article/details/19025973

### 前言 ###

数据在分片时，典型的是分库分表，就有一个全局ID生成的问题。单纯的生成全局ID并不是什么难题，但是生成的ID通常要满足分片的一些要求：

*  不能有单点故障。
 *  以时间为序，或者ID里包含时间。这样一是可以少一个索引，二是冷热数据容易分离。
 *  可以控制ShardingId。比如某一个用户的文章要放在同一个分片内，这样查询效率高，修改也容易。
 *  不要太长，最好64bit。使用long比较好操作，如果是96bit，那就要各种移位相当的不方便，还有可能有些组件不能支持这么大的ID。

先来看看老外的做法，以时间顺序：

### flickr ###

flickr巧妙地使用了mysql的自增ID，及replace into语法，十分简洁地实现了分片ID生成功能。

首先，创建一个表：

**\[sql\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **CREATE** **TABLE** \`Tickets64\` (  
2.    \`id\` **bigint**(20) unsigned NOT NULL auto\_increment,  
3.    \`stub\` **char**(1) NOT NULL **default** '',  
4.    **PRIMARY** **KEY**  (\`id\`),  
5.    **UNIQUE** **KEY** \`stub\` (\`stub\`)  
6.  ) ENGINE=MyISAM

使用上面的sql可以得到一个ID：

**\[sql\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  REPLACE **INTO** Tickets64 (stub) **VALUES** ('a');  
2.  **SELECT** LAST\_INSERT\_ID();

因为使用了replace into的语法，实际上，Tickets64这个表里的数据永远都是这样的：

**\[plain\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  \+-------------------+------+  
2.  | id                | stub |  
3.  \+-------------------+------+  
4.  | 72157623227190423 |    a |  
5.  \+-------------------+------+

那么如何解决单点故障呢？

很简单，利用mysql的自增ID即可。比如有两台ID生成服务器，设置成下面即可：

**\[plain\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  TicketServer1:  
2.  auto-increment-increment = 2  
3.  auto-increment-offset = 1  
4.    
5.  TicketServer2:  
6.  auto-increment-increment = 2  
7.  auto-increment-offset = 2

优点：

简单可靠。

**缺点：**

ID只是一个ID，没有带入时间，shardingId等信息。

### twitter ###

twitter利用zookeeper实现了一个全局ID生成的服务snowflake，https://github.com/twitter/snowflake，可以生成全局唯一的64bit ID。

生成的ID的构成：

**\[plain\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  时间--用前面41 bit来表示时间，精确到毫秒，可以表示69年的数据  
2.  机器ID--用10 bit来表示，也就是说可以部署1024台机器  
3.  序列数--用12 bit来表示，意味着每台机器，每毫秒最多可以生成4096个ID

优点：

充分把信息保存到ID里。

**缺点：**

结构略复杂，要依赖zookeeper。

分片ID不能灵活生成。

### instagram ###

instagram参考了flickr的方案，再结合twitter的经验，利用Postgres数据库的特性，实现了一个更简单可靠的ID生成服务。

instagram是这样设计它们的ID的：

**\[plain\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  使用41 bit来存放时间，精确到毫秒，可以使用41年。  
2.  使用13 bit来存放逻辑分片ID。  
3.  使用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：

**\[sql\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1. REATE OR REPLACE **FUNCTION** insta5.next\_id(**OUT** result **bigint**) **AS** $$  
2. **DECLARE**  
3.     our\_epoch **bigint** := 1314220021721;  
4.     seq\_id **bigint**;  
5.     now\_millis **bigint**;  
6.     shard\_id **int** := 5;  
7. **BEGIN**  
8.     **SELECT** nextval('insta5.table\_id\_seq') %% 1024 **INTO** seq\_id;  
9.   
10.     **SELECT** FLOOR(EXTRACT(EPOCH **FROM** clock\_timestamp()) \* 1000) **INTO** now\_millis;  
11.     result := (now\_millis - our\_epoch) << 23;  
12.     result := result | (shard\_id << 10);  
13.     result := result | (seq\_id);  
14. **END**;  
15. $$ LANGUAGE PLPGSQL;

则在插入新数据时，直接用类似下面的SQL即可（ 连请求生成ID的步骤都省略了！ ）：

**\[sql\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **CREATE** **TABLE** insta5.our\_table (  
2.      "id" **bigint** NOT NULL **DEFAULT** insta5.next\_id(),  
3.      ...rest **of** **table** **schema**...  
4.  )

即使是不懂Postgres数据库，也能从上面的SQL看出个大概。把这个移植到mysql上应该也不是什么难事。

**缺点：**

貌似真的没啥缺点。

**优点：**

充分把信息保存到ID里。

充分利用数据库自身的机制，程序完全不用额外处理，直接插入到对应的分片的表即可。

**Redis实现分片的分局ID**

## 项目地址 ##

[https://github.com/hengyunabc/redis-id-generator][https_github.com_hengyunabc_redis-id-generator]

基于redis的分布式ID生成器。

## 准备 ##

首先，要知道redis的EVAL，EVALSHA命令：

[http://redis.readthedocs.org/en/latest/script/eval.html][http_redis.readthedocs.org_en_latest_script_eval.html]

[http://redis.readthedocs.org/en/latest/script/evalsha.html][http_redis.readthedocs.org_en_latest_script_evalsha.html]

## 原理 ##

利用redis的lua脚本执行功能，在每个节点上通过lua脚本生成唯一ID。   
生成的ID是64位的：

*  使用41 bit来存放时间，精确到毫秒，可以使用41年。
 *  使用12 bit来存放逻辑分片ID，最大分片ID是4095
 *  使用10 bit来存放自增长ID，意味着每个节点，每毫秒最多可以生成1024个ID

比如GTM时间 `Fri Mar 13 10:00:00 CST 2015` ，它的距1970年的毫秒数是 `1426212000000`，假定分片ID是53，自增长序列是4，则生成的ID是：

redis提供了[TIME][]命令，可以取得redis服务器上的秒数和微秒数。因些lua脚本返回的是一个四元组。

客户端要自己处理，生成最终ID。

<code class="hljs lisp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq;</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li></ul>

### 集群实现原理 ###

假定集群里有3个节点，则节点1返回的seq是：

节点2返回的seq是

节点3返回的seq是

这样每个节点返回的数据都是唯一的。

## 单个节点部署 ##

下载redis-script-node1.lua，并把它load到redis上。

获取lua脚本的sha1值，可能是：

在代码里，通过EVALSHA命令，传递这个sha1值，就可以得到生成的ID。

比如，通过命令行执行：

结果可能是：

<code class="hljs livecodeserver has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">1) (integer) 1426238286
 2) (integer) 130532
 3) (integer) 277
 4) (integer) 4</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li></ul>

## 集群部署 ##

假定集群是3个节点，则分别对三个节点执行：

<code class="language-bash hljs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">./redis-cli -host node1 -p 6379 script load "$(cat redis-script-node1.lua)" 
 ./redis-cli -host node2 -p 7379 script load "$(cat redis-script-node2.lua)" 
 ./redis-cli -host node3 -p 8379 script load "$(cat redis-script-node3.lua)" </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li></ul>

## 性能 ##

redis默认配置。

<code class="hljs css has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">单节点，单线程：
 time:0:00:00.959
 speed:10427.52867570386
 单节点，20线程：
 time:0:00:06.710
 speed:29806.259314456034</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li></ul>

结论：   
\- 单节点，qps约3w   
\- 可以线性扩展，3个结点足以满足绝大部分的应用

## java客户端封装 ##

在redis-id-generator-java目录下，有example和benchmark代码。

在调用时，要传入两个参数   
\- tag，即为哪一类服务生成ID   
\- shardId，即分片由哪个ID生成，比如一个用户的订单，则分片ID应该由userId来生成

<code class="language-java hljs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">public class Example {
 
 public static void main(String[] args) {
 String tab = "order";
 long userId = 123456789;
 
 IdGenerator idGenerator = IdGenerator.builder()
 .addHost("127.0.0.1", 6379, "fce3758b2e0af6cbf8fea4d42b379cd0dc374418")
 // .addHost("127.0.0.1", 7379, "1abc55928f37176cb934fc7a65069bf32282d817")
 // .addHost("127.0.0.1", 8379, "b056d20feb3f89483b10c81027440cbf6920f74f")
 .build();
 
 long id = idGenerator.next(tab, userId);
 
 System.out.println("id:" + id);
 List<Long> result = IdGenerator.parseId(id);
 
 System.out.println("miliSeconds:" + result.get(0) + ", partition:"
 + result.get(1) + ", seq:" + result.get(2));
 }
 }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li></ul>

## 多语言客户端 ##

只要支持redis evalsha命令就可以了。

[view plain]: http://blog.csdn.net/hengyunabc/article/details/19025973#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/190295
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/190295/fork
[https_github.com_hengyunabc_redis-id-generator]: https://github.com/hengyunabc/redis-id-generator
[http_redis.readthedocs.org_en_latest_script_eval.html]: http://redis.readthedocs.org/en/latest/script/eval.html
[http_redis.readthedocs.org_en_latest_script_evalsha.html]: http://redis.readthedocs.org/en/latest/script/evalsha.html
[TIME]: http://redis.readthedocs.org/en/latest/server/time.html