《大型网站技术架构：核心原理与案例分析》读书笔记
索引
1、网站架构的伸缩性设计
网站的伸缩性设计可分为两类：
- 根据功能进行物理分离实现伸缩，纵向分离和横向分离
- 单一功能通过集群实现伸，将相同服务器部署在多台服务器上构成一个集群整体对外提供服务
2、应用服务器集群的伸缩性设计
服务器应设计成无状态的，即应用服务器不存储请求上下文信息，如果将部署有相同应用的服务器组成一个集群，每次用户请求都可以发送到集群中任意一台服务器上去处理，任何一台服务器的处理结果都是相同的。这样只能将用户请求按照某种规则（负载均衡）分发到集群的不同服务器上，就可以构成一个应用服务器集群，每个用户的每个请求都可以落在不同的服务器上。
2.1 负载均衡
负载均衡服务器的实现可以分成两部分：
- 根据负载均衡算法和 Web 服务器列表计算得到集群中一台 Web 服务器的地址
- 将请求数据发送到该地址对应的 Web 服务器上
2.1.1 HTTP 重定向负载均衡
HTTP 重定向服务器是一台普通的应用服务器，其唯一的功能就是根据用户的 HTTP 请求计算一台真实的 Web 服务器的地址，并将该 Web 服务器地址写入 HTTP 重定向响应中返回给用户浏览器。
优点是简单，缺点是浏览器需要两次请求服务器才能完成一次访问，性能较差。
###2.1.2 DNS 域名解析负载均衡
每次域名解析请求都会根据负载均衡算法计算一个不同的IP地址返回。
优点：将负载均衡的工作转交给 DNS，省掉了网站管理维护负载均衡服务器的麻烦，并可以加快用户访问速度，改善性能。
缺点：目前的DNS是多级解析，每一级 DNS 都会有缓存记录，当某台服务器下线后，即使修改了缓存记录，生效也需要一段时间，这段时间，DNS 仍然会将域名解析到已经下线的服务器，导致用户访问失败。
2.1.3 反向代理负载均衡
反向代理服务器的请求转发是在 HTTP 协议层面，也叫做应用层负载均衡。由于反向代理服务器是所有请求和响应的中转站，因此其性能会成为瓶颈。
2.1.4 IP 负载均衡
IP 负载均衡是在内核进程完成数据分发，不需要用户进程处理。
2.1.5 数据链路层负载均衡
数据链路层负载均衡就是在通信协议的数据链路层修改 mac 地址进行负载均衡，负载均衡数据分发过程中不修改 IP 地址，只修改目的 mac 地址。
这种三角传输模式的链路层负载均衡是目前大型网站使用最广的一种负载均衡手段，LVS
2.1.6 负载均衡算法
轮询：所有请求被依次分发到每台应用服务器上，即每台服务器需要处理的请求数目相同
加权轮询：根据应用服务器硬件性能的情况，在轮询的基础上，按照配置的权重将请求分发到每个服务器
随机：请求被随机分配到各个应用服务器
最少连接：记录每个服务器正在处理的连接数，将新的请求分发到最少连接的服务器上
源地址散列：根据请求的 IP 地址进行 Hash 计算，得到应用服务器，这样来自同一个 IP 地址的请求总在同一个服务器上处理。
3、分布式缓存集群的伸缩性设计
分布式缓存集群伸缩性设计的最主要目标：新上线的缓存服务器对整个分布式缓存集群影响最小，也就是说新加入缓存服务器后使整个缓存服务器集群中已经缓存的数据尽可能还被访问到。
3.1 分布式缓存的一致性 Hash 算法
3.1.1 什么是路由算法
路由算法决定究竟该访问集群中的哪一台服务器，简单的路由算法可以使用余数 Hash：用服务器数目除缓存数据 Key 的 Hash 值，余数为服务器列表下标编号。由于 HashCode 具有随机性，因此使用余数 Hash 路由算法可保证缓存数据在整个服务器集群中比较均衡的分布。
3.1.2 路由算法存在什么问题
余数 Hash 几乎可以满足绝大多数的缓存路由需求，但是，假设由于业务发展，网站需要将 3 台缓存服务器增加到 4 台，更改服务器列表，仍然使用余数 Hash，用 4 除以 Beijing 的 Hash 值 490806430，余数为 2，对应服务器 NODE2，假设数据 <Beijing, Data> 缓存在 NODE1，对 NOTE2 的读缓存操作失败，缓存没有命中。
很容易可以看出，3 台服务器扩容至 4 台服务器，大约有 75% 被缓存了数据不能命中，随着服务器集群规模的增大，比例不断上升。
###3.1.3 一致性 Hash 算法
一致性 Hash 算法是通过一致性 Hash 环的数据结构实现 Key 到缓存服务器的 Hash 映射。
具体过程：先构造一个长度为 2^32 的整数环（一致性 Hash 环），根据节点名称的 Hash 值将缓存服务器的节点放置在这个 Hash 环上，然后根据需要缓存的数据的 Key 值计算得到其 Hash 值，然后在 Hash 环上顺时针查找距离这个 Key 的 Hash 值最近的缓存服务器节点，完成 Key 到服务器的 Hash 映射查找，如图中所示。
当缓存服务器需要扩容的时候，只需要将新加入的节点名称（NODE3）的 Hash 值放入一致性 Hash 环中，由于 Key 是顺时针查找距离其最近的节点，因此新加入的几点只影响整个环中的一小段，如下图所示。
加入新节点 NODE3 后，原来的 Key 大部分还能继续计算到原来的节点，只有 Key3、Key0 从原来的 NODE1 重新计算到 NODE3，这样就能保证大部分被缓存数据还可以命中。
具体实现：这个长度为 2^32 的一致性 Hash 环通常使用二叉查找树实现，Hash 查找的过程实际上是在二叉查找树中查找不小于查找数的最小值。（二叉树的最右边叶子节点和最左边叶子节点相连接，构成环）
3.1.3 Hash 环数据倾斜
新加入的节点 NODE3 只影响了原来的节点 NODE1，也就是说一部分原来需要访问 NODE1 的缓存数据现在需要访问 NODE3（概率上是 50%）但是原来的节点 NODE0 和 NODE2 不受影响，这就意味着 NODE0 和 NODE2 缓存数据量和负载压力是 NODE1 与 NODE3 的两倍。
为了解决这负载不均衡的问题，可以将每台物理缓存服务器虚拟为一组虚拟缓存服务器，将虚拟服务器的 Hash 值放置在 Hash 环上，Key 在环上先找到虚拟服务器节点，再得到物理服务器的信息，如下图所示：
这样新加入物理服务器节点时，是将一组虚拟节点加入环中，如果虚拟节点的数目足够多，这组虚拟节点将会影响同样多数目的已经存在环上的虚拟节点，而这些已经存在的虚拟节点又对应不同的物理节点。得到的最终结果是：新加入一台缓存服务器，将会较为均为地影响原来集群中已经存在的所有服务器，也就是说分摊原有缓存服务器集群中的所有服务器的一小部分负载，显然每个物理节点对应的虚拟节点越多，各个物理节点之间的负载越均衡，新加入物理服务器对原有的物理服务器的影响约保持一致。