深入分布式缓存：从原理到实践最新章节_于君泽著

2.5　分布式系统设计实践

有分布式理论指导，遵循分布式系统的设计策略，具体而言也可以总结一些常见的分析系统设计实践。本小节主要讨论几个通用性问题：

·全局ID生成；

·哈希取模分配；

·路由表；

·一致性哈希；

·数据拆分。

2.5.1　全局ID生成

目前TDDL（Taobao Distribute Data Layer）提供的id生成主要还是依托数据库来进行的，oracle可以直接使用sequence来完成id生成，MySQL则需要DBA建立一个表专门用于生成id。

首先得思考一下，为什么存在全局ID这个问题？在分布式环境下，数据库是可以拆分（sharding）的，一张表的自增机制（比如MySQL）只能保证该表唯一，在数据合并到历史库，迁移或者查询，如果出现id冲突无异于噩梦。

另外，由于数据库访问是高成本操作，也要避免每次INSERT都要到id生成器作DB层面的查询。我们来看看业界的一些方案。

1.UUID

UUID由以下几部分的组合：

1）当前日期和时间，UUID的第一个部分与时间有关，如果你在生成一个UUID之后，过几秒又生成一个UUID，则第一个部分不同，其余相同。

2）时钟序列。

3）全局唯一的IEEE机器识别号，如果有网卡，从网卡MAC地址获得，没有网卡以其他方式获得。

优势：API简单、易用。

不足：占用空间大、字符串本身无法加工，可读性不强。

2.ID生成表模式

使用id生成表，比较经典的是Flicker的案例，Flicker在解决全局ID生成方案里就采用了MySQL自增长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

在我们的应用端需要做下面这两个操作，在一个事务会话里提交：

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

这样我们就能拿到不断增长且不重复的ID了，到上面为止，我们只是在单台数据库上生成ID，从高可用角度考虑，要解决单点故障问题，Flicker的方案是启用两台数据库服务器来生成ID，通过区分auto_increment的起始值和步长来生成奇偶数的ID。

这个方案优势简单易用，也有一定的高可用方案，不足是使用了mysql数据库的独特语法REPLACE INTO。

3.Snowflake

Twitter在把存储系统从MySQL迁移到Cassandra的过程中由于Cassandra没有顺序ID生成机制，于是自己开发了一套全局唯一ID生成服务：Snowflake。GitHub地址： https://github.com/twitter/snowflake 。根据twitter的业务需求，snowflake系统生成64位的ID。由3部分组成：

·41位的时间序列（精确到毫秒，41位的长度可以使用69年）

·10位的机器标识（10位的长度最多支持部署1024个节点）

·12位的计数顺序号（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）

优点：高性能，低延迟；独立的应用；按时间有序。

缺点：需要独立的开发和部署。

4.结合缓存方案

如图2-36所示，可以采取ID生成表模式成批获取id比如1000放到本地缓存（Local cache），这样在client使用的时候可进一步提升性能。

图2-36　批量获取ID示意图

优点：高性能，低延迟。

缺点：ID不连贯。

2.5.2　哈希取模

哈希方式是最常见的数据分布方式，实现方式是通过可以描述记录的业务的id或key，通过Hash函数的计算求余。余数作为处理该数据的服务器索引编号处理。如图2-37所示：

图2-37　路由示意图

这样的好处是只需要通过计算就可以映射出数据和处理节点的关系，不需要存储映射。难点就是如果id分布不均匀可能出现计算、存储倾斜的问题，在某个节点上分布过重。另外在调整数据存储，比如把2个库扩展成4个库，数据迁移是一个比较麻烦的事情。

以分布式缓存和拆分数据库的情况分别做一下说明。

分布式缓存，假设有3台server提供缓存服务，假设数据基本均衡，则每台机器缓存1/3的数据，如图2-38所示。

图2-38　hash分布示意

如果增加2台服务器则算法变成为Hash（key）/5，大部分数据都会出现不能命中的情况，如图2-39所示：

图2-39　增加到5个节点的分布式缓存

拆分数据库也存在扩容的问题，解决方法是先预设足够大的逻辑库，比如100个库，随着物理负载的增加，把对应的逻辑库迁移到新增的物理库上即可，对于应用透明，相当于在应用和物理数据库之间增加了一层映射关系。

2.5.3　一致性哈希

一致性哈希算法是在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法。主要解决单调性（Monotonicity）和分散性（Spread）的问题。单调性简单描述是哈希的结果应能够保证原有已分配的内容可以被映射到原有缓冲中去，避免在节点增减过程中导致不能命中。

按照常用的hash算法来将对应的key哈希到一个具有2^32次方个桶的空间中，即0~（2^32）-1的数字空间中。现在我们可以将这些数字头尾相连，想象成一个闭合的环形。如图2-40所示。

图2-40　圆形空间对应哈希

在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其他不会受到影响，如图2-41所示。

图2-41　一致性哈希示意

一致性哈希的优点在于可以任意动态添加、删除节点，每次添加、删除一个节点仅影响一致性哈希环上相邻的节点。为了尽可能均匀地分布节点和数据，一种常见的改进算法是引入虚节点的概念，系统会创建许多虚拟节点，个数远大于当前节点的个数，均匀分布到一致性哈希值域环上。这种增强型方案主要解决平衡性问题，所谓平衡性（Balance）是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

2.5.4　路由表

什么情况下走到路由表模式，一般在于需要全局计算的节点。比如说如图2-42所示的场景，用户去抽奖，那么抽奖背后是有预算的。由于在高并发环境下比较单行记录热点，则对预算进行了拆分，并且拆分到不同逻辑数据库中去。那么如何知道，某些记录预算使用完没有呢，使用完的就不路由了。可以由子预算的服务更新后异步通知给预算。

图2-42　预算场景下的路由

采用路由表存在一个风险，就是数据是集中式管理的，存在单点风险。如果数据规模小，而数据库本身有备份机制或者failover能力，是可行的。

2.5.5　数据拆分

Cobar是一个著名的阿里巴巴开源的分布式数据库中间件。解决数据规模增加对于应用这层proxy的问题，Cobar支持的数据库结构（schema）的层次关系具有较强的灵活性，用户可以将表自由放置不同的datanode，也可将不同的datasource放置在同一MySQL实例上。如图2-43所示。在实际应用中，我们需要通过配置文件（schema.xml）来定义我们需要的数据库服务器和表的分布策略。

图2-43　数据库拆分示意

路由函数定义，应用在路由规则的算法定义中，路由函数可以自定义扩展。如下示例，我们可以看出分表的规则是，按照id字段把某表中的数据分配到db1和db2两个分区中，其中id小于1024的数据会被放到db2库的分区中

<function name="func1"
class="com.alibaba.cobar.route.function.PartitionByLong">  
    <property name="partitionCount">2</property>  
<property name="partitionLength">1024</property>  
</function>

当当开源了sharding-jdbc，架构图如图2-44所示。

图2-44　sharding-jdbc架构图

2.5 分布式系统设计实践

2.5.1 全局ID生成