在分布式系统中,为了适应可能有多台主(写)服务器,任何时刻都可能有服务器加进来或者去掉这种情况,就不能用传统的数据库自增ID方案。这篇文章介绍几个在分布式系统中用的ID生成方案。

业务服务器

业务服务器指的是我们写的后端服务器。这里的着重点是自己生成id,不需要数据库自己给出一个自增id。

自增

自增ID是最简单的方案,数据库自己提供了这个功能。但是一旦有多台写服务器就不能适用了。而且自增ID会影响写性能,在数据库的写性能是整个系统性能瓶颈的情况下,能减轻一点压力都是好的。

有序uuid

uuid是一个32位的字符串ID,在服务器本地生成,可以保证单机生成的ID在整个系统中独立。原始版本的uuid是无序的,这在数据库取出一系列有序数据时非常影响性能。幸好现在已经有了可以生成有序uuid的算法,比如 Laravel 的 Str::orderedUuid()。但是由于uuid是32位字符串,依然影响性能。

snowflake

之前的文章大型服务器的架构中描述了蚂蚁金服的id生成方案,即是一种类snowflake结构。原始的snowflake结构是

41位时间+10位机器编号+12位自增序列号

因为id中包含了机器号,所以能保证绝对不会和其他服务器生成的id重复。但是这要求机器自己知道自己的id,比如在初始化的时候从管理服务处获得,或者有一个独立的id生成服务器。

参考资料[1]介绍了一种 php 的 snowflake id 生成算法。

资源服务器

资源服务器指的是数据库或者缓存。这里的着重点是如何分布式存储数据,即每台服务器内容不同。

取模

获得业务服务器生成的id后,为了存储在不同的服务器,可以将id取模。比如我们有4台服务器,那么 id%4 的到的余数就是我们要的机器id,然后就可以存储到对应的数据库了。但是如果服务器数量增加或者减少,取模后的到的余数就不能对应到原来的机器id,原来的数据也就不能正常取出了。

一致性哈希算法

简单的来说,一致性哈希算法就是把数据 id 和 服务器 id 进行相同的哈希,然后存储在一个被分成 2^32 部分的圆中,存取的时候找到离数据右边最近的服务器。比如服务器id “S1”, “S2” 哈希后投射到圆上的两个点,把这两个点中间的所有点取出来,就是下面这段

S1——————-S2

这时有个数据id,哈希后的值落在 S1 S2 之间,会被存储在 S2 里。这时增加服务器 S3

S1———S3———-S2

这时数据id哈希后落在 S1S3 会存储在S3中,S3S2 会存储在S2中。这里需要手动把S2里面应该落在S3的数据(永久缓存)手动转移到S3中。

参考资料[3][4]介绍了一种 php 的一致性哈希算法。

算法最佳实践

一般用time33 和 crc32 作为哈希算法。但是由于我们起的原始ID不够离散,很容易只落在几个服务器上,所以建议在哈希之前再加一层md5。下面是time32的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function time33($str) {
// hash(i) = hash(i-1) * 33 + str[i]
$hash = 0;
$s = md5($str); //让id更加离散
$seed = 5;
$len = 32;
for ($i = 0; $i < $len; $i++) {
// (hash << 5) + hash 相当于 hash * 33
//$hash = sprintf("%u", $hash * 33) + ord($s{$i});
//$hash = ($hash * 33 + ord($s{$i})) & 0x7FFFFFFF;
$hash = ($hash << $seed) + $hash + ord($s{$i});
}

return $hash & 0x7FFFFFFF;
}

//echo myHash("却道天凉好个秋~");
echo "key1: " . myHash("key1") . "\n";

业务最佳实践

另一个业务上的最佳实践是,不一定按照ID进行哈希。比如我们有一个论坛,访问量最大的就是按板块分的帖子页,即需要一次性取出一个板块里面的一批帖子。我们希望这些帖子是在一台服务器上的,那么就不能按照帖子id哈希,而要按照板块id哈希。

如果这时我们有其他列表业务,比如一个用户的所有帖子。我的建议是缓存一个用户的前1000个帖子id到 redis。

对外混淆

对于对外接口,要将ID混淆,避免关键信息暴露,这种情况可以使用 hashids。这个库可以将数字id可逆的转成字符串。


参考资料:
[1]https://huoding.com/2016/11/03/552
[2]https://blog.csdn.net/bntX2jSQfEHy7/article/details/79549368
[3]https://blog.csdn.net/jt521xlg/article/details/49360895
[4]http://www.cnblogs.com/phpfans/p/4641490.html