架构：数据服务器集群的伸缩性设计。

分布式缓存集群的伸缩性设计

不同于应用服务器集群的伸缩性设计，分布式缓存集群的伸缩性不能使用简单地负载均衡手段来实现。
和所有服务器都部署相同应用的应用服务器集群不同，分布式缓存服务器集群中不同服务器中缓存的数据各不相同，缓存访问请求不可以在缓存服务器集群中的任意一台处理，必须先找到缓存有需要数据的服务器，然后才能访问这个特点会严重制约分布式缓存集群的伸缩性设计，因为新上线的缓存服务器没有缓存任何数据，而已下线的缓存服务器还缓存着网站的许多热点数据。
必须让新上线的缓存服务器对整个分布式缓存集群影响最小，也就是说新加入缓存服务器后应使整个缓存服务器集群中已经缓存的数据尽可能还被访问到，这是分布式缓存集群伸缩性设计的最主要目标。

Memcached分布式缓存集群的访问模型

以Memcached为代表的分布式缓存，访问模型如下图所示。

应用程序通过Memcached客户端访问Memcached服务器集群，Memcached客户端主要由一组API、Memcached服务器集群路由算法、Memcached服务器集群列表及通信模块构成。
其中路由算法负责根据应用程序输入的缓存数据KEY计算得到应该将数据写入到Memcached的哪台服务器（写缓存）或者应该从哪台服务器读数据（读缓存）。
一个典型的缓存写操作如上图中箭头所示路径。应用程序输入需要写缓存的数据<'BEIJING', DATA>，API将KEY('BEIJING')输入路由算法模块，路由算法根据KEY和Memcached集群服务器列表计算得到一台服务编号（NODE1），进而得到该机器的IP地址和端口（10.0.0.0:91000）。API调用通信模块和编号为NODE1的服务器通信，将数据<'BEIJING',DATA>写入该服务器。完成一次分布式缓存的写操作。
读缓存的过程和写缓存一样，由于使用同样的路由算法和服务器列表，只要应用程序提供相同的KEY('BEIJING')，Memcached客户端总是访问相同的服务器（NODE1）去读取数据。只要服务器还缓存着该数据，就能保证缓存命中。

Memcached分布式缓存集群的伸缩性挑战

由上述讨论可得知，在Memcached分布式缓存系统中，对于服务器集群的管理，路由算法至关重要，和负载均衡算法一样，决定着究竟该访问集群中的哪台服务器。
简单的路由算法可以使用余数Hash：用服务器数目除以缓存数据KEY的Hash值，余数为服务器列表下标编号。假设上图中'BEIJING'的Hash值是490806430（Java中的HashCode()返回值），用服务器数目3除以该值，得到余数1，对应节点NODE1。由于HashCode具有随机性，因此使用余数Hash路由算法可保证缓存数据在整个Memcached服务器集群中比较均衡的分布。
对余数Hash路由算法稍加改进，就可以实现和负载均衡算法中加权负载均衡一样的加权路由。事实上，如果不需要考虑缓存服务器集群伸缩性，余数Hash几乎可以满足绝大多数的缓存路由需求。
但是，当分布式缓存集群需要扩容的时候，事情就变得棘手了。
假设由于业务发展，网站需要将3台缓存服务器扩容至4台。更改服务器列表，仍旧使用余数Hash，用4除以'BEIJING'的Hash值490806430,余数为2，对应服务器NODE2。由于数据<'BEIJING',DATA>缓存在NODE1，对NODE2的读缓存操作失败，缓存没有命中。
很容易就可以计算出，3台服务器扩容至4台服务器，大约有75%(3/4)被缓存了的数据不能正确命中，随着服务器集群规模的增大，这个比例线性上升。当100台服务器的集群中加入一台新服务器，不能命中的概率是99%（N/(N+1)）。
这个结果显然是不能接受的，在网站业务中，大部分的业务数据读操作请求事实上是通过缓存获取的，只有少量读操作请求会访问数据库，因此数据库的负载能力是以有缓存为前提而设计的。当大部分被缓存了的数据因为服务器扩容而不能正确读取时，这些数据访问的压力就落到了数据库的身上，这将大大超过数据库的负载能力，严重的可能会导致数据库宕机（这种情况下，不能简单重启数据库，网站也需要较长时间才能逐渐恢复正常）。

本来加入新的缓存服务器是为了降低数据库的负载压力，但是才做不当却导致了数据库的崩溃。如果不对问题和解决方案有透彻了解，网站技术总有想不到的陷阱让架构师一脚踩空。遇到这种情况，用某网站一位资深架构师的话说，就是“一股寒气从脚底板窜到了脑门心”。

一种解决办法是在网站访问量最少的时候扩容缓存服务器集群，这时候对数据库的负载冲击最小。然后通过模拟请求的方法逐渐预热缓存，使缓存服务器中的数据重新发布。但是这种方案对业务场景有要求，还需要技术团队通宵加班（网站访问低谷通常是在半夜）。
能不能通过改进路由算法，使得新加入的服务器不影响大部分缓存数据的正确命中呢？目前比较流行的算法是一致性Hash算法。

分布式缓存的一致性Hash算法

一致性Hash算法通过一个叫做一致性Hash环的数据结构实现KEY到缓存服务器的Hash映射，如下图所示。

具体算法过程为：先构造一个长度为0~2的32次方的整数环（这个环被称作一致性Hash环），根据节点名称的Hash值（其分布范围同样为0~2的32次方）将缓存服务器节点放置在这个Hash环上。然后根据需要缓存的数据的KEY值计算得到其Hash值（其分布范围也同样为0~2的32次方），然后在Hash环上顺时针查找举例这个KEY的Hash值最近的缓存服务器节点，完成KEY到服务器的Hash映射查找。
在上图中，假设NODE1的Hash值为3,594,963,423，NODE2的Hash值为1,845,328,979，而KEY0的HASH值为2,534,256,785，那么KEY0在环上顺时针查找，找到的最近的节点就是NODE1。
当缓存服务器集群需要扩容的时候，只需要将新加入的节点名称（NODE3）的Hash值放入一致性Hash环中，由于KEY是顺时针查找距离其最近的节点，因此新加入的节点只影响整个环中的一小段，如下图中深色一段。

假设NODE3的Hash值是2,790,324,235，那么加入NODE3后，KEY0（Hash值2,534,256,785）顺时针查找得到的节点就是NODE3。
上图中，加入新节点NODE3后，原来的KEY大部分还能继续计算到原来的节点，只有KEY3、KEY0从原来的NODE1重新计算到NODE3。这样就能保证大部分被缓存的数据还可以继续命中。3台服务器扩容至4台服务器，可以继续命中原有缓存数据的概率是75%，远高于余数Hash的25%，而且随着集群规模越大，继续命中原有缓存数据的概率也逐渐增大，100台服务器扩容增加1台服务器，继续命中的概率是99%。虽然仍有小部分数据缓存在服务器中不能被读到，但是这个比例足够小，通过访问数据库获取也不会对数据库造成致命的负载压力。
具体应用中，这个长度2的32次方的一致性Hash环通常使用二叉查找树实现，Hash查找过程实际上是在二叉查找树中查找不小于查找树的最小数值。当然这个二叉树的最右边叶子节点和最左边的叶子节点相连接，构成环。
但是，上面描述的算法过程还存在一个小小的问题。
新加入的节点NODE3只影响了原来的节点NODE1，也就是说一部分原来需要访问NODE1的缓存数据现在需要访问NODE3（概率上是50%）。但是原来的节点NODE0和NODE2不受影响，这就意味着NODE0和NODE2缓存数据量和负载压力是NODE1与NODE3的两倍。如果4台机器的性能是一样，那么这种结果显然不是我们需要的。
怎么办？
计算机领域有句话：计算机的任何问题都可以通过增加一个虚拟层来解决。计算机硬件、计算机网络、计算机软件都莫不如此。计算机网络的7层协议，每一层都可以看作是下一层的虚拟层；计算机操作系统可以看作是计算机硬件的虚拟层；Java虚拟机可以看作是操作系统的虚拟层；分层的计算机软件架构事实上也是利用虚拟层的概念。
解决上述一致性Hash算法带来的负载不均衡问题，也可以通过使用虚拟层的手段：将每台物理缓存服务器虚拟为一组虚拟缓存服务器，将虚拟服务器的Hash值放置在Hash环上，KEY在环上先找到虚拟服务器节点，再得到物理服务器的信息。
这样新加入物理服务器节点时，是将一组虚拟节点加入环中，如果虚拟节点的数目足够多，这组虚拟节点将会影响同样多数目的已经在环上存在的虚拟节点，这样已经存在的虚拟节点又对应不同的物理节点。最终的结果是：新加入一台缓存服务器，将会较为均匀的影响原来集群中已经存在的所有服务器，也就是说分摊原有缓存服务器集群中所有服务器的一小部分负载，其总的影响范围和上面讨论过的相同。如下图所示。

在上图中，新加入节点NODE3对应的一组虚拟节点为V30，V31，V32，加入到一致性Hash环上后，影响V01，V12，V22三个虚拟节点，而这三个虚拟节点分别对应NODE0，NODE1，NODE2三个物理节点。最终Memcached集群中加入一个节点，但是同时影响到集群中已存在的三个物理节点，在理想情况下，每个物理节点受影响的数据量（还在缓存中，但是不能被访问到数据）为其节点缓存数据量的1/4(X/(N+X)，N为原有物理节点数，X为新加入物理节点数)，也就是说集群中已经被缓存的数据有75%可以被继续名汇总，和未使用虚拟节点的一致性Hash算法结果相同。
显然每个物理节点对应的虚拟节点越多，各个物理节点之间的负载越均衡，新加入物理服务器对原有的物理服务器的影响越保持一致（这就是一致性Hash这个名称的由来）。那么在实践中，一台物理服务器虚拟为多少个虚拟服务器节点合适呢？太多会影响性能，太少又会导致负载不均衡，一般说来，经验值是150，当然根据集群规模和负载均衡的精度需求，这个值应该根据具体情况具体对待。

数据存储服务器集群的伸缩性设计

和缓存服务器集群的伸缩性设计不同，数据存储服务器集群的伸缩性对数据的持久性和可用性提出了更高的要求。
缓存的目的是加速数据读取的速度并减轻数据存储服务器的负载压力，因此部分缓存数据的丢失不影响业务的正常处理，因为数据还可以从数据库等存储服务器获取。
而数据存储服务器必须保证数据的可靠存储，任何情况下都必须保证数据的可用性和正确性。因此缓存服务器集群的伸缩性架构方案不能直接适用于数据库等存储服务器。存储服务器集群的伸缩性设计相对更复杂一些，具体说来，又可分为关系数据库集群的伸缩性设计和NoSQL数据库的伸缩性设计。

关系数据库集群的伸缩性设计

关系数据库凭借其简单强大的SQL和众多程数的商业数据库产品，占据了从企业应用到网站系统的大部分业务数据存储服务。市场上主要的关系数据都支持复制功能，使用这个功能可以对数据库进行简单伸缩。。下图为使用数据复制的MySQL集群伸缩性方案。

在这种架构中，虽然多台服务器部署MySQL实例，但是他们的角色有主从之分，数据写操作都在主服务上，由主服务器将数据同步到集群中其他从服务器，数据读操作及数据分析等离线操作在从服务器上进行。
除了数据库主从读写分离，业务分割模式也可以用在数据库，不同业务数据表部署在不同的数据库集群上，即俗称的数据分库。这种方式的制约条件是跨库的表不能进行Join操作。
在大型网站的实际应用中，即使进行了分库和主从复制，对一些单表数据仍然很大的表，比如Facebook的用户数据库，淘宝的商品数据库，还需要进行分片，将一张表拆开分别存储在多个数据库中。
目前网站在线业务应用中比较成熟的支持数据分片的分布式关系数据库产品主要有开源的Amoeba和Cobar。这两个产品有相似的架构设计，以Cobar为例，部署模型如下图所示。

Cobar是一个分布式关系数据库访问代理，介于应用服务器和数据库服务器之间（Cobar也支持非独立部署，以lib的方式和应用程序部署在一起）。应用程序通过JDBC驱动访问Cobar集群，Cobar服务器根据SQL和分库规则分解SQL，分发到MySQL集群不同的数据库实例上执行（每个MySQL实例都部署为主/从结构，保证数据高可用）。
Cobar系统组件模型如下图所示。

前端通信模块负责和应用程序通信，接收到SQL请求（select * from users where userid in (12,22,23)）后转交给SQL解析模块，SQL解析模块解析获得SQL中的路由规则查询条件（userid in (12,22,23)）再转交给SQL路由模块，SQL路由模块根据路由规则配置（userId为偶数路由至数据库A，userId为奇数路由至数据库B）将应用程序提交的SQL分解成两条SQL（select * from users wehre userid in (12,22);select * from users where userid in (23);）转交给SQL执行代理模块，发送至数据库A和数据库B分别执行。
数据库A和数据库B的执行结果返回至SQL执行模块，通过结果合并模块将两个返回结果集合并成一个结果集，最终返回给应用程序，完成在分布式数据库中的一次访问请求。
那么Cobar如何做集群的伸缩呢？
Cobar的伸缩有两种：Cobar服务器集群的伸缩和MySQL服务器集群的伸缩。
Cobar服务器可以看作是无状态的应用服务器，因此其集群伸缩可以简单使用负载均衡的手段实现。而MySQL中存储着数据，要想保证集群扩容后数据一致负载均衡，必须要做数据迁移，将集群中原来机器中的数据迁移到新添加的机器中，如下图所示。

具体迁移哪些数据可以利用一致性Hash算法（即路由模块使用一致性Hash算法进行路由），尽量使需要迁移的数据最少。但是迁移数据需要遍历数据库中每条记录（的索引），重新进行路由计算确定其是否需要迁移，这会对数据库访问造成一定压力。并且需要解决迁移过程中数据的一致性、可访问性、迁移过程中服务器宕机时的可用性等诸多问题。
实践中，Cobar利用了MySQL的数据同步功能进行数据迁移。数据迁移不是以数据为单位，而是以Schema为单位。在Cobar集群初始化时，在每个MySQL实例创建多个Schema（根据业务愿景规划未来集群规模，如集群最大规模为1000台数据库服务器，那么总的初始Schema数≥1000）。集群扩容的时候，从每个服务器中迁移部分Schema到新机器中，由于迁移以Schema为单位，迁移过程可以使用MySQL的同步机制，如下图所示。

同步完成时，即新机器中的Schema数据和原机器中Schema数据一致的时候，修改Cobar服务器的路由配置，将这些Schema的IP修改为新机器的IP，然后删除原机器中的相关Schema，完成MySQL集群扩容。
在整个分布式关系数据库的访问请求过程中，Cobar服务器处理消耗的时间是很少的，时间花费主要还是在MySQL数据库端，因此应用程序通过Cobar访问分布式关系数据库，性能基本和直接访问关系数据库相当，可以满足网站在线业务的实时处理需求。事实上由于Cobar代替应用程序连接数据库，数据库只需要维护更少的连接，减少不必要的资源消耗，改善性能。
但由于Cobar路由后只能在单一数据库实例上处理查询请求，因此无法执行跨库的JOIN操作，当然更不能执行跨库的事务处理。
相比关系数据库本身功能上的优雅强大，目前各类分布式关系数据库解决方案都显得非常简陋，限制了关系数据库某些功能的使用。但是当网站业务面临不停增长的海量业务数据存储压力时，又不得不利用分布式关系数据库的集群伸缩能力，这时就必须从业务行回避分布式关系数据库的各种缺点：避免事务或利用事务补偿机制代替数据库事务；分解数据访问逻辑避免JOIN操作等。
除了上面提到的分布式数据库，还有一类分布式数据库可以支持JOIN操作执行复杂的SQL查询，如GreenPlum。但是这类数据库的访问延迟比较大（可以想象，JOIN操作需要在服务器间传输大量的数据），因此一般使用在数据仓库等非实时业务中。

NoSQL数据库的伸缩性设计

在计算机数据存储领域，一直是关系数据库（Relation Database）的天下，以至传统企业应用领域，许多应用系统设计都是面向数据库设计——先设计数据库然后设计程序，从而导致关系模型绑架对象模型，并由此引申出旷日持久的业务对象贫血模型与充血模型之争。业界为了解决关系数据库的不足，提出了诸多方案，比较有名的是对象数据库，但是这些数据库的出现只是进一步证明关系数据库的优越而已。直到大型网站遇到了关系数据库难以克服的缺陷——糟糕的海量数据处理能力及僵硬的设计约束，局面才有所改善。为了解决上述问题，NoSQL这一概念被提了出来，以弥补关系数据库的不足。
NoSQL，主要指非关系的、分布式的数据库设计模式。也有许多专家将NoSQL解读为Not Only SQL，表示NoSQL只是关系数据库的补充，而不是替代方案。一般而言，NoSQL数据库产品都放弃了关系数据库的两大重要基础：以关系代数为基础的结构化查询语言（SQL）和事务一致性保证(ACID)。而强化其他一些大型网站更关心的特性：高可用性和可伸缩性。
开源社区有各种NoSQL产品，其支持的数据结构和伸缩特性也各不相同，目前看来应用最广泛的是Apache HBase。
HBase为可伸缩海量数据存储而设计，实现面向在线业务的实时数据访问延迟。HBase的伸缩性主要依赖其可分裂的HRegion及可伸缩的分布式文件系统HDFS实现。
HBase的整体架构如下图所示。Hbase中，数据以HRegion为单位进行管理，也就是说应用程序如果想要访问一个数据，必须先找到HRegion，然后将数据读写操作提交给HRegion，由HRegion完成存储层面的数据操作。每个HRegion中存储一段Key值区间[key1,key2]的数据，HRegionServer是物理服务器，每个HRegionServer上可以启动多个HRegion实例。当一个HRegion中写入的数据太多，达到配置的阈值时，HRegion会分裂成两个HRegion，并将HRegion在整个集群中进行迁移，以使HRegionServer的负载均衡。

所有HRegion的信息（存储的Key值区间、所在HRegionServer地址、访问端口号等）都记录在HMaster服务器上，为了保证高可用，HBase启动多个HMaster，并通过Zookeeper（一个支持分布式一致性的数据管理服务）选举出一个主服务器，应用程序通过Zookeeper获得主Hmaster的地址，输入Key值获得这个Key所在的HRegionServer地址，然后请求HRegionServer上的HRegion，获得需要的数据。调用时序如下图所示。

数据写入过程也是一样，需要先得到HRegion才能继续操作，HRegion会把数据存储在若干个叫做HFile格式的文件中，这些文件使用HDFS分布式文件系统存储。在整个集群内分布并高可用。当一个HRegion中数据量太多时，HRegion（连同HFile）会分裂成两个HRegion，并根据集群中服务器负载进行迁移，如果集群中有新加入的服务器，也就是说有了新的HRegionServer，由于其负载较低，也会把HRegion迁移过去并记录到HMaster，从而实现Hbase的线性伸缩。