阿里面试宝典（七）：大数据与高并发（下）

问题导读：
1、什么是分布式事务？
2、什么是令牌桶算法？
3、域名解析负载均衡算法是怎样的？

上一篇：阿里面试宝典（七）：大数据与高并发（上）



七、阿里巴巴中文站商品信息如何存放

看看阿里巴巴中文网站首页 以女装/女包包为例



商品基本信息

名称、价格，出厂日期，生产厂商等

关系型数据库：mysql/oracle目前淘宝在去O化(也即拿掉Oracle)，注意，淘宝内部用的Mysql是里面的大牛自己改造过的

为什么去IOE

IBM小型机 廉价的PC机
oracle数据库 myql

EMC存储

集中式------>分布式



2008年，王坚加盟阿里巴巴成为集团首席架构师，即现在的首席技术官。这位前微软亚洲研究院常务副院长被马云定位为：将帮助阿里巴巴集团建立世界级的技术团队，并负责集团技术架构以及基础技术平台搭建。

在加入阿里后，带着技术基因和学者风范的王坚就在阿里巴巴集团提出了被称为“去IOE”（在IT建设过程中，去除IBM小型机、Oracle数据库及EMC存储设备）的想法，并开始把云计算的本质，植入阿里IT基因。

王坚这样概括“去IOE”运动和阿里云之间的关系：“去IOE”彻底改变了阿里集团IT架构的基础，是阿里拥抱云计算，产出计算服务的基础。“去IOE”的本质是分布化，让随处可以买到的Commodity PC架构成为可能，使云计算能够落地的首要条件。

推荐阅读：《阿里云这群疯子》



商品描述、详情、评价信息(多文字类)

多文字信息描述类，IO读写性能变差
文档数据库MongDB中

商品的图片

流媒体服务器
分布式的文件系统中
淘宝自己的TFS
Google的GFS

Hadoop的HDFS

商品的关键字

搜索引擎，淘宝内用
ISearch
扫地僧



商品的波段性的热点高频信息

内存数据库
Tair、Redis、Memcache

商品的交易、价格计算、积分累计

外部系统，外部第3方支付接口
支付宝

大型互联网应用(大数据、高并发、多样数据类型)的难点和解决方案

难点

数据类型多样性
数据源多样性和变化重构
数据源改造而数据服务平台不需要大面积重构

解决办法

阿里、淘宝干了什么？UDSL
是什么



什么样



映射



API



热点缓存



八、数据的水平拆分和垂直拆分

当我们使用读写分离、缓存后，数据库的压力还是很大的时候，这就需要使用到数据库拆分了。

数据库拆分简单来说，就是指通过某种特定的条件，按照某个维度，将我们存放在同一个数据库中的数据分散存放
到多个数据库（主机）上面以达到分散单库（主机）负载的效果。

切分模式： 垂直（纵向）拆分、水平拆分。

垂直拆分

一个数据库由很多表的构成，每个表对应着不同的业务，垂直切分是指按照业务将表进行分类，分布到不同的数据
库上面，这样也就将数据或者说压力分担到不同的库上面，如下图：



优点：

1. 拆分后业务清晰，拆分规则明确。
2. 系统之间整合或扩展容易。
3. 数据维护简单。

缺点：

1. 部分业务表无法join，只能通过接口方式解决，提高了系统复杂度。
2. 受每种业务不同的限制存在单库性能瓶颈，不易数据扩展跟性能提高。
3. 事务处理复杂。

水平拆分

垂直拆分后遇到单机瓶颈，可以使用水平拆分。相对于垂直拆分的区别是：垂直拆分是把不同的表拆到不同的数据
库中，而水平拆分是把同一个表拆到不同的数据库中。

相对于垂直拆分，水平拆分不是将表的数据做分类，而是按照某个字段的某种规则来分散到多个库之中，每个表中包含一部分数据。简单来说，我们可以将数据的水平切分理解为是按照数据行的切分，就是将表中 的某些行切分到一个数据库，而另外的某些行又切分到其他的数据库中，主要有分表，分库两种模式，如图：



优点：

1. 不存在单库大数据，高并发的性能瓶颈。
2. 对应用透明，应用端改造较少。
3. 按照合理拆分规则拆分，join操作基本避免跨库。
4. 提高了系统的稳定性跟负载能力。

缺点：

1. 拆分规则难以抽象。
2. 分片事务一致性难以解决。
3. 数据多次扩展难度跟维护量极大。
4. 跨库join性能较差。拆分的处理难点

两张方式共同缺点

1. 引入分布式事务的问题。
2. 跨节点Join 的问题。
3. 跨节点合并排序分页问题。

针对数据源管理，目前主要有两种思路：

A. 客户端模式，在每个应用程序模块中配置管理自己需要的一个（或者多个）数据源，直接访问各个 数据库，在模块内完成数据的整合。

优点：相对简单，无性能损耗。
缺点：不够通用，数据库连接的处理复杂，对业务不够透明，处理复杂。

B. 通过中间代理层来统一管理所有的数据源，后端数据库集群对前端应用程序透明；

优点：通用，对应用透明，改造少。
缺点：实现难度大，有二次转发性能损失。

拆分原则

1. 尽量不拆分，架构是进化而来，不是一蹴而就。(SOA)
2. 最大可能的找到最合适的切分维度。
3. 由于数据库中间件对数据Join 实现的优劣难以把握，而且实现高性能难度极大，业务读取 尽量少使用多表Join -尽量通过数据冗余，分组避免数据垮库多表join。
4. 尽量避免分布式事务。
5. 单表拆分到数据1000万以内。

切分方

范围、枚举、时间、取模、哈希、指定等

案例分析

场景一

建立一个历史his系统，将公司的一些历史个人游戏数据保存到这个his系统中，主要是写入，还有部分查询，读写比约为1:4；由于是所有数据的历史存取，所以并发要求比较高；

分析：

历史数据

写多都少

越近日期查询越频繁？

什么业务数据？用户游戏数据

有没有大规模分析查询？

数据量多大？

保留多久？

机器资源有多少？

方案1：按照日期每月一个分片


带来的问题：1.数据热点问题（压力不均匀）

方案2：按照用户取模， --by Jerome 就这个比较合适了带来的问题：后续扩容困难

方案3：按用户ID范围分片（1-1000万=分片1，xxx）带来的问题：用户活跃度无法掌握，可能存在热点问题场景二
建立一个商城订单系统，保存用户订单信息。

分析：

电商系统

一号店或京东类？淘宝或天猫？

实时性要求高

存在瞬时压力

基本不存在大规模分析

数据规模？

机器资源有多少？

维度？商品？用户？商户？

方案1：按照用户取模，

带来的问题：后续扩容困难

方案2：按用户ID范围分片（1-1000万=分片1，xxx）带来的问题：用户活跃度无法掌握，可能存在热点问题方案3：按省份地区或者商户取模
数据分配不一定均匀

场景3

上海公积金，养老金，社保系统

分析：

社保系统

实时性要求不高不存在瞬时压力

大规模分析？

数据规模大

数据重要不可丢失

偏于查询？

方案1：按照用户取模，

带来的问题：后续扩容困难

方案2：按用户ID范围分片（1-1000万=分片1，xxx）带来的问题：用户活跃度无法掌握，可能存在热点问题方案3：按省份区县地区枚举
数据分配不一定均匀

九、分布式事务

假如没有分布式事务

在一系列微服务系统当中，假如不存在分布式事务，会发生什么呢？让我们以互联网中常用的交易业务为例子：



上图中包含了库存和订单两个独立的微服务，每个微服务维护了自己的数据库。在交易系统的业务逻辑中，一个商
品在下单之前需要先调用库存服务，进行扣除库存，再调用订单服务，创建订单记录。

正常情况下，两个数据库各自更新成功，两边数据维持着一致性。



但是，在非正常情况下，有可能库存的扣减完成了，随后的订单记录却因为某些原因插入失败。这个时候，两边数
据就失去了应有的一致性。



什么是分布式事务？

分布式事务用于在分布式系统中保证不同节点之间的数据一致性。分布式事务的实现有很多种，最具有代表性的是
由Oracle Tuxedo系统提出的XA分布式事务协议。

XA协议包含两阶段提交（2PC）和三阶段提交（3PC）两种实现，这里我们重点介绍两阶段提交的具体过程。

XA两阶段提交（2PC）

在魔兽世界这款游戏中，副本组团打BOSS的时候，为了更方便队长与队员们之间的协作，队长可以发起一个“就位确认”的操作：



当队员收到就位确认提示后，如果已经就位，就选择“是”，如果还没就位，就选择“否”。



当队长收到了所有人的就位确认，就会向所有队员们发布消息，告诉他们开始打BOSS。



相应的，在队长发起就位确认的时候，有可能某些队员还并没有就位：





以上就是魔兽世界当中组团打BOSS的确认流程。这个流程和XA分布式事务协议的两阶段提交非常相似。

那么XA协议究竟是什么样子呢？在XA协议中包含着两个角色：事务协调者和事务参与者。让我们来看一看他们之间的交互流程：

第一阶段：



在XA分布式事务的第一阶段，作为事务协调者的节点会首先向所有的参与者节点发送Prepare请求。

在接到Prepare请求之后，每一个参与者节点会各自执行与事务有关的数据更新，写入Undo Log和Redo Log。如果参与者执行成功，暂时不提交事务，而是向事务协调节点返回“完成”消息。

当事务协调者接到了所有参与者的返回消息，整个分布式事务将会进入第二阶段。

第二阶段：



在XA分布式事务的第二阶段，如果事务协调节点在之前所收到都是正向返回，那么它将会向所有事务参与者发出Commit请求。

接到Commit请求之后，事务参与者节点会各自进行本地的事务提交，并释放锁资源。当本地事务完成提交后，将会向事务协调者返回“完成”消息。

当事务协调者接收到所有事务参与者的“完成”反馈，整个分布式事务完成。

以上所描述的是XA两阶段提交的正向流程，接下来我们看一看失败情况的处理流程：

第一阶段：



第二阶段：



在XA的第一阶段，如果某个事务参与者反馈失败消息，说明该节点的本地事务执行不成功，必须回滚。

于是在第二阶段，事务协调节点向所有的事务参与者发送Abort请求。接收到Abort请求之后，各个事务参与者节点需要在本地进行事务的回滚操作，回滚操作依照Undo Log来进行。

以上就是XA两阶段提交协议的详细过程。

XA两阶段提交的不足

XA两阶段提交究竟有哪些不足呢？

1.性能问题

XA协议遵循强一致性。在事务执行过程中，各个节点占用着数据库资源，只有当所有节点准备完毕，事务协调者才会通知提交，参与者提交后释放资源。这样的过程有着非常明显的性能问题。

2.协调者单点故障问题

事务协调者是整个XA模型的核心，一旦事务协调者节点挂掉，参与者收不到提交或是回滚通知，参与者会一直处于中间状态无法完成事务。

3.丢失消息导致的不一致问题。

在XA协议的第二个阶段，如果发生局部网络问题，一部分事务参与者收到了提交消息，另一部分事务参与者没收到提交消息，那么就导致了节点之间数据的不一致。

如果避免XA两阶段提交的种种问题呢？有许多其他的分布式事务方案可供选择：

XA三阶段提交（3PC）

XA三阶段提交在两阶段提交的基础上增加了CanCommit阶段，并且引入了超时机制。一旦事物参与者迟迟没有接到协调者的commit请求，会自动进行本地commit。这样有效解决了协调者单点故障的问题。但是性能问题和不一致的问题仍然没有根本解决。

MQ事务

利用消息中间件来异步完成事务的后一半更新，实现系统的最终一致性。这个方式避免了像XA协议那样的性能问题。

TCC事务

TCC事务是Try、Commit、Cancel三种指令的缩写，其逻辑模式类似于XA两阶段提交，但是实现方式是在代码层面来人为实现。




十、BitMap

Bit-map的基本思想

32位机器上，对于一个整型数，比如int a=1 在内存中占32bit位，这是为了方便计算机的运算。但是对于某些
应用场景而言，这属于一种巨大的浪费，因为我们可以用对应的32bit位对应存储十进制的0-31个数，而这就是Bit-

map的基本思想。Bit-map算法利用这种思想处理大量数据的排序、查询以及去重。    Bitmap在用户群做交集

和并集运算的时候也有极大的便利。

Bit-map应用之快速排序

假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）,我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，



对应位设置为1:



遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的，时间复杂度O(n)。   


优点：

运算效率高，不需要进行比较和移位；占用内存少，比如N=10000000；
只需占用内存为N/8=1250000Byte=1.25M。   


缺点：
所有的数据不能重复。即不可对重复的数据进行排序和查找。

Bit-map应用之快速去重

2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

首先，根据“内存空间不足以容纳这2.5亿个整数”我们可以快速的联想到Bit-map。下边关键的问题就是怎么设计我们的Bit-map来表示这2.5亿个数字的状态了。其实这个问题很简单，一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11。那我们大概需要存储空间几十兆左右。接下来的任务就是遍历一次这2.5亿个数字，如果对应的状态位为00，则将其变为01；如果对应的状态位为01，则将其变为11；如果为11，对应的转态位保持不变。最后，我们将状态位为01的进行统计，就得到了不重复的数字个数，时间复杂度为O(n)。

Bit-map应用之快速查询

同样，我们利用Bit-map也可以进行快速查询，这种情况下对于一个数字只需要一个bit位就可以了，0表示不存在，1表示存在。假设上述的题目改为，如何快速判断一个数字是够存在于上述的2.5亿个数字集合中。    同之前一样，首先我们先对所有的数字进行一次遍历，然后将相应的转态位改为1。遍历完以后就是查询，由于我们的Bit-map采取的是连续存储（整型数组形式，一个数组元素对应32bits），我们实际上是采用了一种分桶的思想。一个数组元素可以存储32个状态位，那将待查询的数字除以32，定位到对应的数组元素（桶），然后再求余（%32），就可以定位到相应的状态位。如果为1，则代表改数字存在；否则，该数字不存在。

Bit-map扩展——Bloom Filter(布隆过滤器)

当一个元素被加入集合中时,通过k各散列函数将这个元素映射成一个位数组中的k个点,并将这k个点全部置为1.
有一定的误判率--在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误判为属于这个集合.因此,它不适合那些"零误判"的应用场合.在能容忍低误判的应用场景下,布隆过滤器通过极少的误判换区了存储空间的极大节省.   




Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。   




在判断y是否属于这个集合时，对y应用k次哈希函数，若所有hi(y)的位置都是1（1≤i≤k），就认为y是集合中的元素，否则就认为y不是集合中的元素。



总结

使用Bit-map的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的操作。Bloom Fliter是Bit-map思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构。

应用

适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下   


基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码   


扩展：bloom filter可以看做是对bit-map的扩展

问题实例： 1、已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

8位最多99 999 999，大概需要99m个bit，大概10几M字节的内存即可。

2、在2.5亿个整数中找出不重复的整数，内存不足以容纳这2.5亿个整数。

方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存232*2bit=1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

十一、Bloom Filter

1.把第一个URL按照三种Hash算法，分别生成三个不同的Hash值。



2.把第二个URL也按照三种Hash算法，分别生成三个不同的Hash值。



3.依次比较每一个Hash结果，只有当全部结果都相等时，才判定两个URL相同。





具体怎样映射呢？流程如下：

1.创建一个空的Bitmap集合。



2.把第一个URL按照三种Hash算法，分别生成三个不同的Hash值。



3.分别判断5，17， 9 在Bitmap的对应位置是否为1，只要不同时为1，就认为该Url没有重复，于是把5，17，9的对应位置设置为1。



4.把第二个URL按照三种Hash算法，分别生成三个不同的Hash值。




5.分别判断10，12， 9 在Bitmap的对应位置是否为1，只要不同时为1，就认为该Url没有重复，于是把10，12， 9的对应位置设置为1。



6.把第三个URL按照三种Hash算法，分别生成三个不同的Hash值。



7.分别判断4，16， 11 在Bitmap的对应位置是否为1，只要不同时为1，就认为该Url没有重复，于是把4，16， 11的对应位置设置为1。



8.把第四个URL按照三种Hash算法，分别生成三个不同的Hash值。



9.分别判断5，17， 9 在Bitmap的对应位置是否为1。判断的结果是 5，17， 9 在Bitmap对应位置的值都是1，所以判定该Url是一个重复的Url。




  
1.URL按照三个Hash算法得到三个结果。




2.分别判断10，12， 17 在Bitmap的对应位置是否为1。判断的结果是 10，12， 17 在Bitmap对应位置的值都是1，所以判定该Url是一个重复的Url。







十二、常见的限流算法

计数器法

计数器法是限流算法里最简单也是最容易实现的一种算法。比如我们规定，对于A接口来说，我们1分钟的访问次数不能超过100个。那么我们可以这么做：在一开 始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个 请求的间隔时间还在1分钟之内，那么说明请求数过多；如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置counter，具体算法的示意图如下：



这个算法虽然简单，但是有一个十分致命的问题，那就是临界问题，我们看下图：



从上图中我们可以看到，假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。

聪明的朋友可能已经看出来了，刚才的问题其实是因为我们统计的精度太低。那么如何很好地处理这个问题呢？或
者说，如何将临界问题的影响降低呢？我们可以看下面的滑动窗口算法。

滑动窗口

滑动窗口，又称rolling window。为了解决这个问题，我们引入了滑动窗口算法。如果学过TCP网络协议的话，那么一定对滑动窗口这个名词不会陌生。下面这张图，很好地解释了滑动窗口算法：



在上图中，整个红色的矩形框表示一个时间窗口，在我们的例子中，一个时间窗口就是一分钟。然后我们将时间窗
口进行划分，比如图中，我们就将滑动窗口 划成了6格，所以每格代表的是10秒钟。每过10秒钟，我们的时间窗口
就会往右滑动一格。每一个格子都有自己独立的计数器counter，比如当一个请求 在0:35秒的时候到达，那么
0:30~0:39对应的counter就会加1。

那么滑动窗口怎么解决刚才的临界问题的呢？我们可以看上图，0:59到达的100个请求会落在灰色的格子中，而
1:00到达的请求会落在橘黄色的格 子中。当时间到达1:00时，我们的窗口会往右移动一格，那么此时时间窗口内的总请求数量一共是200个，超过了限定的100个，所以此时能够检测出来触 发了限流。

我再来回顾一下刚才的计数器算法，我们可以发现，计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做
进一步地划分，所以只有1格。

由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

漏桶算法

漏桶算法，又称leaky bucket。为了理解漏桶算法，我们看一下维基百科上的对于该算法的示意图：



从图中我们可以看到，整个算法其实十分简单。首先，我们有一个固定容量的桶，有水流进来，也有水流出去。对于流进来的水来说，我们无法预计一共有多 少水会流进来，也无法预计水流的速度。但是对于流出去的水来说，这个桶可以固定水流出的速率。而且，当桶满了之后，多余的水将会溢出。

我们将算法中的水换成实际应用中的请求，我们可以看到漏桶算法天生就限制了请求的速度。当使用了漏桶算法，
我们可以保证接口会以一个常速速率来处理请求。所以漏桶算法天生不会出现临界问题。

令牌桶算法

令牌桶算法，又称token bucket。为了理解该算法，我们再来看一下维基百科上对该算法的示意图：



从图中我们可以看到，令牌桶算法比漏桶算法稍显复杂。首先，我们有一个固定容量的桶，桶里存放着令牌
（token）。桶一开始是空的，token以 一个固定的速率r往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通 过。

令牌桶

令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送(百科)。



在秒杀活动中，用户的请求速率是不固定的，这里我们假定为10r/s，令牌按照5个每秒的速率放入令牌桶，桶中最多存放20个令牌。仔细想想，是不是总有那么一部分请求被丢弃。

计数器 VS 滑动窗口

计数器算法是最简单的算法，可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上需要更多的存储空间。也就是说，如果滑动窗口的精度越高，需要的存储空间就越大。

漏桶算法 VS 令牌桶算法

漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法，取走token是不需要耗费时间的，也就是说，假设桶内有100个token时，那么可以瞬间允许100个请求通过。

令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。当然我们需要具体情况
具体分析，只有最合适的算法，没有最优的算法。

十三、负载均衡

dns域名解析负载均衡

原理：在DNS服务器上配置多个域名对应IP的记录。例如一个域名www.baidu.com对应一组web服务器IP地址，域名解析时经过DNS服务器的算法将一个域名请求分配到合适的真实服务器上。

如图：



优点：将负载均衡的工作交给了DNS，省却了网站管理维护负载均衡服务器的麻烦，同事许多DNS还支持基于地理位置的域名解析，将域名解析成距离用户地理最近的一个服务器地址，加快访问速度吗，改善性能。

缺点：目前的DNS解析是多级解析，每一级DNS都可能化缓存记录A，当摸一服务器下线后，该服务器对应的DNS记录A可能仍然存在，导致分配到该服务器的用户访问失败。

DNS负载均衡的控制权在域名服务商手里，网站可能无法做出过多的改善和管理。

不能够按服务器的处理能力来分配负载。DNS负载均衡采用的是简单的轮询算法，不能区分服务器之间的差异，不能反映服务器当前运行状态，所以其的负载均衡效果并不是太好。

可能会造成额外的网络问题。为了使本DNS服务器和其他DNS服务器及时交互，保证DNS数据及时更新，使地址能随机分配，一般都要将DNS的刷新时间设置的较小，但太小将会使DNS流量大增造成额外的网络问题。

反向代理负载均衡

原理：反向代理处于web服务器这边，反向代理服务器提供负载均衡的功能，同时管理一组web服务器，它根据负载均衡算法将请求的浏览器访问转发到不同的web服务器处理，处理结果经过反向服务器返回给浏览器。

如图：



例如：浏览器访问请求的地址是反向代理服务器的地址114.100.80.10，反向代理服务器收到请求，经过负载均衡算法后得到一个真实物理地址10.0.03，并将请求结果发给真实无服务，真实服务器处理完后通过反向代理服务器返回给请求用户。

优点：部署简单，处于http协议层面。

缺点：使用了反向代理服务器后，web 服务器地址不能直接暴露在外，因此web服务器不需要使用外部IP地址，而反向代理服务作为沟通桥梁就需要配置双网卡、外部内部两套IP地址。

http重定向协议实现负载均衡

原理：根据用户的http请求计算出一个真实的web服务器地址，并将该web服务器地址写入http重定向响应中返回给浏览器，由浏览器重新进行访问。

如图：



优点：比较简单

缺点：浏览器需要两次次请求服务器才能完成一次访问，性能较差。

http重定向服务器自身的处理能力可能成为瓶颈。

使用http302响应重定向，有可能使搜索引擎判断为SEO作弊，降低搜索排名。

分层的负载均衡算法

十四、一致性Hash算法

一致性哈希算法（Consistent Hashing）最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整
形），整个哈希空间环如下：



整个空间按顺时针方向组织。0和232-1在零点中方向重合。

下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中四台服务器使用ip地址哈希后在环空间的位置如下：



接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：



根据一致性哈希算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。

下面分析一致性哈希算法的容错性和可扩展性。现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

下面考虑另外一种情况，如果在系统中增加一台服务器Node X，如下图所示：



此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X 。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展
性。

另外，一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服
务器，其环分布如下，



此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：



同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node
A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

最新经典文章，欢迎关注公众号