Neo's Blog

Reactor 模式首先是事件驱动的，有一个或多个并发输入源，有一个Service Handler，有多个Request Handlers；这个Service Handler会同步的将输入的请求（Event）多路复用的分发给相应的Request Handler。如果用图表示的如下：

其实在设计模式层面，IO多路复用也是采用 Reactor 模式的。

IO 多路复用模型可以看成是 Reactor 模式在 IO 模型上的应用。

总体思路

底层原理

算的越少，算得越快

局部性原理

空间换时间

并行

在我看来，高性能指的是，我们的系统能够在尽可能短的时间内完成用户的请求，也就是说latency尽可能的低。

如果说系统能够支撑更大的吞吐量，能够承载更多的同时在线。我们除了降低latency，还可以考虑加机器（如果还没有reach到某个系统平瓶颈的前提下）

提高吞吐量

增加并发进程数

注意：无限增加，不会无限提升性能(对系统的扩展性有要求)

减少响应时间

IO密集型：优化数据库索引、加缓存

CPU密集型：优化算法时间复杂度、减少不必要运算等

并发读的核心优化理念是尽量减少用户到服务端来“读”数据，或者让他们读更少的数据；

并发写的处理原则也一样，它要求我们在数据库层面独立出来一个库，做特殊的处理。

从一个架构师的角度来看，要想打造并维护一个超大流量并发读写、高性能、高可用的系统，在整个用户请求路径上从浏览器到服务端我们要遵循几个原则，就是要保证

1. 用户请求的数据尽量少
2. 完成这个请求的路径尽量短、依赖尽量少 =》 上游到下游的请求数尽量少

也就两个大的方向：提升单次效率、减少不必要的请求

1. 动静分离方案（移除无关依赖、减少请求）
2. 热点的发现与隔离（缩短热点的服务路径）
3. 请求的削峰与分层过滤（异步化，减少无必要的依赖）
4. 服务端的极致优化（缩短热点的服务路径）

参考：

https://zhuanlan.zhihu.com/p/721305456

一些概念

有合理的办法应对系统的增长（数据量、流量、复杂性）

一个良好适配应用的可扩展架构，是围绕着假设（assumption）建立的：哪些操作是常见的？哪些操作是罕见的？这就是所谓负载参数。如果假设最终是错误的，那么为扩展所做的工程投入就白费了，最糟糕的是适得其反。

数据库、缓存、依赖的第三方、复杂均衡、交换机带宽都是系统扩展时需要考虑的点

阻碍可扩展性可能的因素：

1. 某个中间件（更有可能是）的连接数—-因为常规的app机器说是足够多的，而中间件（例如Mysql）大多数实例数量并不多
2. 服务注册与发现中心出现性能问题（某一个namespace下的instance过多，而其内部算法性能有问题）
3. 负载均衡算法出现性能问题（考虑你的负载均衡算法是$O(N^2)$，如果机器数量到达1w台，做一次负载均衡的计算量将不可忽视）
4. 应用层访问存储的算法有问题（如果存储扩容了，上层应用更改的成本很大很大）
5. 存储本身的问题，单库单表的设计，缺乏扩展性；正确的设计应该是：索引与数据尽早分离。例如用ES做索引，而DB仅作某主要维度的关系查询。

分层

首先要分层，分层是实现扩展的必要条件；分了层才能让系统有更好的可扩展能力；

我们将系统分为如下几层：

接入层

主要负责负载均衡，要求负载均衡策略的时间复杂度要尽量简单，追求$O(lgn)$的时间复杂度，最坏不能超过$O(n)$。对于更坏时间复杂度的均衡策略，性能上会扛不住。

应用层

业务层：按照业务拆分、按照重要性拆分（轻重分离，核心、非核心）、按照请求来源（客户端、web、内网等）—这个跑偏了，这些点主要服务于可用性。

这里侧重点在于无状态，我们一定要确保我们的服务无状态。

存储层

存储层做扩展会更麻烦一些。

实施分片策略时，要考虑的最重要的问题是选择什么分片键(ShardingKey)。分片键（也叫作分区键，Partition Key）由一个或者多个数据列组成，用来决定将数据分到哪个Shard。在图1-22所示的例子中，user_id被用作分片键。分片键可以把数据库查询路由到正确的数据库，使你高效地检索和修改数据。在选择分片键时，最重要的标准之一是选择一个可以让数据均匀分布的键。

一些挑战：
重分片数据：出现如下情况时，需要对数据重新分片。第一种是因为数据快速增长，单个Shard无法存储更多的数据。第二种是因为数据的分布不均匀，有些Shard的空间可能比其他的更快耗尽。当Shard被耗尽时，就需要更新用于分片的哈希函数，然后把数据移到别的地方去。我们会在第5章介绍一致性哈希算法，它是解决这个问题的常用技术。

名人问题：也叫作热点键问题。过多访问一个特定的Shard可能造成服务器过载。想象一下，把Katy Perry、Justin Bieber和Lady Gaga的数据都放在同一个Shard里，对于社交应用而言，这个Shard会因读操作太多而不堪重负。为了解决这个问题，我们可能需要为每个名人都分配一个Shard，而且每个Shard可能还需要进一步分区。

连接和去规范化(de-normalization)：一旦数据库通过分片被划分到多个服务器上，就很难跨数据库分片执行连接(join)操作了。解决这个问题的常用方法就是对数据库去规范化，把数据冗余存储到多张表中，以便查询可以在一张表中执行。

一般情况下，要求我们根据业务量提前估计好存储容量。根据计算出来的总的存储量，提前做足够的数据分片。

换言之，对于存储层，我们的一种思路是：早做扩展，以确保将来不做扩展；

另外一种思路是，添加必要的路由层（数据访问路由层）或者路由算法（数据表倍增法），来确保将来的扩展对上层不可见。

manager层

1. 抽象service层可能提供的一些原子能力
2. 封装对第三方接口的调用

池化技术
核心思想：用空间换时间，期望使用预先创建好的对象来减少频繁创建对象的性能开销，同时还统一管理了对象，降低了对象的使用成本。
例子：
（1）数据库连接池-最小数量、最大数量、如果超过最大则等待
（2）线程池-最小数量、最大数量、有界队列（监控队列中元素的个数）
线程池大小：区分IO密集、CPU密集
（3）内存池

超时事件管理

IO模型

线程模型，一般会综合考虑IO模型、超时事件如何管理、线程池、消息队列等

topic 高性能服务设计

设计思想

内存池

资源管理

对于服务器框架而言，有哪些需要管理的资源？

1. 内存
   1. 内存池的设计关键
2. 客户端连接
   1.
3. Request & Response
4. 线程

同步 OR 异步

阻塞 OR 非阻塞

线程 OR 进程

谁来接收client连接

某一个固定的线程（进程） 还是 几个线程（进程）轮着来？

接收到连接之后，如何处理？

自己处理 还是 交给其他人处理？

accept —> recv ——> send —->

存储模型有哪些？

关系模型

文档模型：数据通常是自我包含的，而且文档之间的关系非常稀少

图数据模型：任意事物都可能与任何事物相关联

底层方法论

海量存储系列参考：
https://blog.51cto.com/aliapp/1327613

是什么

也就是用于处理数据的一类方法的抽象，最主要的作用是，按照某个条件选出一批数据，然后再进行一些简单的统计计算的功能。如是而已:)

事务

事务，本质来说就是一组由一个人（或机器）发起的连续的逻辑操作，共同的完成一件事情，在完成整个事情之前，其所有的改动，都不应该对其他人可见和影响。而在事务结束之后，其一切的改动，都必须“全部”“立刻”对其他的人（或机器）可见。

单机事务

这个排队可供选择的方法，就我知道的有：1，排他锁。2. 读写锁。3. Copy on write（MVCC） .4. 队列。5. 内存事务。这些方式。

从性能来说，排他锁最慢，而读写锁因为读可以并发，所以效率稍高，但写和读不能同时进行。
Copy on write(MVCC) 则读取和写入之间可以互相不影响，所以效率更高。
队列这种方式，内存时效果很好，省去中断上下文切换的时间。内存事务，目前还在研究阶段，具备很大潜力的东西。

分布式事务

背景：异地延迟、scale out、冗余带来的一致性

索引

加速找到想要的数据：索引

成本：你付出了空间成本，本质来说就是空间换时间的过程。同时，也会降低写入的效率。

B树

如果是一个运行时间很长的b树，那么几乎所有的请求，都是随机io。因为磁盘块本身已经不再连续，很难保证可以顺序读取。

两种思路：

1. 使用ssd，让寻道成为往事，提升硬件，让随机读写没有那么慢。

2. 放弃部分读性能，使用更加面向顺序写的树的结构来提升写性能。

这个类别里面，从数据结构来说，就我所知并比较流行的是两类，

一类是COLA（Cache-Oblivious Look ahead Array）（代表应用自然是tokuDB）。

一类是LSM tree(Log-structured merge Tree)或SSTABLE

(代表的数据集是cassandra,hbase,bdb java editon,levelDB etc.).

那么，b树的写太烂了，我需要提升写，可以放弃部分磁盘读性能，怎么办呢？

简单，那就弄很多个小的有序结构，比如每m个数据，在内存里排序一次，下面100个数据，再排序一次……这样依次做下去，我就可以获得N/m个有序的小的有序结构。

在查询的时候，因为不知道这个数据到底是在哪里，所以就从最新的一个小的有序结构里做二分查找，找得到就返回，找不到就继续找下一个小有序结构，一直到找到为止。

很容易可以看出，这样的模式，读取的时间复杂度是(N/m)*log2N 。读取效率是会下降的。

这就是最本来意义上的LSM tree的思路。

那么这样做，性能还是比较慢的，于是需要再做些事情来提升，怎么做才好呢？

于是引入了以下的几个东西来改进它

1. Bloom filter : 就是个带随即概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是我就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。

2. 小树合并为大树： 也就是大家经常看到的compact的过程，因为小树他性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了。

这就是LSMTree的核心思路和优化方式。

不过，LSMTree也有个隐含的条件，就是他实现数据库的insert语义时性能不会很高，原因是，insert的含义是： 事务中，先查找该插入的数据，如果存在，则抛出异常，如果不存在则写入。这个“查找”的过程，会拖慢整个写入。

====

W+R>N

相信这个大家都耳熟能详了吧？呵呵，我从其他角度来说明这件事吧。

N表示这个复制集群的总数【很多地方解释的不是很准确造成了不少误解】。

W表示写入份数

R表示一次一致性读所需要的份数（这里要注意，是随机从N中选择的机器数量哦）

===

gossip协议

gossip协议是这两套存储的基础之一，说复杂也复杂，说不复杂也不复杂。。其实gossip就是p2p协议。他主要要做的事情是，去中心化。

怎么做到的呢？我只希望在这篇文章里给大家留下几个印象：gossip是干什么的？怎么做到的？优势劣势是什么？即可。对协议的细节感兴趣的，可以自己去深入研究。

gossip的核心目标就是去中心。

做到的方式：

根据种子文件，按照某种规则连接到一些机器，与他们建立联系，不追求全局一致性，只是将对方机器中自己没有的数据同步过来。这里就设计到如何能够快速的知道自己的数据和其他人的数据在哪些部分不一致呢？这时候就要用到Merkle tree了，它能够快速感知自己所持有的数据中哪里发生了变更。

优势：

去中心化，看看伟大的tor，只要能连到一个seed，有一个口子能出长城，那么你最终就能跳出长城。。

劣势：

一致性比较难以维持

5种IO模型

当应用程序需要通过操作系统进行IO通信时，一共有下面5种IO模型供选择。

（同步）阻塞IO

（同步）非阻塞IO

（同步）IO多路复用

复用IO的基本思路就是通过slect或poll、epoll 来监控多fd ，来达到不必为每个fd创建一个对应的监控线程，从而减少线程资源创建的目的。

（异步）信号驱动IO

FATAL缺点：信号I/O在大量IO操作时可能会因为信号队列溢出导致没法通知。

异步（非阻塞）IO

缺点：技术比较新，可能还有些坑没有填完；另外就是异步IO会让应用比较复杂，代码变得难以理解（异步不符合人的思考习惯）

端口复用，通过互斥锁来避免惊群效应

为什么不采用多线程模型管理连接

1. 无状态服务，无需共享进程内存
2. 采用独立的进程，可以让互相之间不会影响。一个进程异常崩溃，其他进程的服务不会中断，提升了架构的可靠性。
3. 进程之间不共享资源，不需要加锁，所以省掉了锁带来的开销。

为什么不采用多线程处理逻辑业务？

1. 进程数已经等于核心数，再新建线程处理任务，只会抢占现有进程，增加切换代价。
2. 作为接入层，基本上都是数据转发业务，网络 IO 任务的等待耗时部分，已经被处理为非阻塞/全异步/事件驱动模式，在没有更多 CPU 的情况下，再利用多线程处理，意义不大。
3. 并且如果进程中有阻塞的处理逻辑，应该由各个业务进行解决，比如 openResty 中利用了 Lua 协程，对阻塞业务进行了优化。

采用了什么：

多进程模型

每一个进程，维护一个epoll对象，来管理所有连接上来的client，并设置为非阻塞。

select

不足：

1. 通过数组来管理fd，数量限制
2. 触发方式单一，仅支持水平触发（LT)

poll

优点：通过链条来管理fd，突破数量限制

不足：

1. 当你拥有一个很大的socket集合，不过由于网络延时，任一时间只有部分socket是“活跃”的，但是select/poll每次调用都会线性扫描全部的集合（时间复杂度是$O(n)$，导致效率呈线性下降。
2. 内核与用户态的数据拷贝

epoll

特点：

1. 没有最大并发连接的限制
2. 通过红黑树管理所有的fd，时间复杂度为$O(lgn)$
3. 更丰富的触发方式，同时支持水平触发（LT)与边缘触发（ET)

Reactor模型

单线程Reactor模型
优点：单 Reactor 单进程的方案因为全部工作都在同一个进程内完成，所以实现起来比较简单，不需要考虑进程间通信，也不用担心多进程竞争。
不足：
（1）第一个缺点，因为只有一个进程，无法充分利用 多核 CPU 的性能；【该缺点可以部署多个进程来解决】
（2）第二个缺点，Handler 对象在业务处理时，整个进程是无法处理其他连接的事件的，如果业务处理耗时比较长，那么就造成响应的延迟；
使用场景：CPU密集型
例子：Redis

单 Reactor 多线程 / 多进程
优点：能够充分利用多核CPU
不足：
（1）子线程完成业务处理后，要把结果传递给主线程的 Reactor 进行发送，这里涉及共享数据的竞争。
（2）因为一个 Reactor 对象承担所有事件的监听和响应，而且只在主线程中运行，在面对瞬间高并发的场景时，容易成为性能的瓶颈的地方。
使用场景：
例子：?

多 Reactor 多线程 / 多进程
优点：克服单 Reactor 多线程 / 多进程的缺点2，主线程不会成为瓶颈；【相对上面的方案，实现更加简单一些】主线程和子线程分工明确，主线程只负责接收新连接，子线程负责完成后续的业务处理；主线程和子线程的交互很简单，主线程只需要把新连接传给子线程，子线程无须返回数据，直接就可以在子线程将处理结果发送给客户端。
不足：
使用场景：
例子：memcache、Netty

多 Reactor 多线程 / 多进程（变种）
思路：进一步的放大子线程/子进程的工作，把accept的工作也交给了子进程。
使用场景：
例子：Nginx

判断使用同步或异步

计算qps * latency(in seconds)【最大并发】，如果和cpu核数是同一数量级，就用同步，否则用异步。

eg. qps = 2000，latency = 10ms，计算结果 = 2000 * 0.01s = 20
和常见的32核在同一个数量级，用同步。

eg. qps = 100, latency = 5s, 计算结果 = 100 * 5s = 500。和核数不在同一个数量级，用异步。

eg. qps = 500, latency = 100ms，计算结果 = 500 * 0.1s = 50。基本在同一个数量级，可用同步。如果未来延时继续增长，考虑异步。

这个公式计算的是同时进行的平均请求数（你可以尝试证明一下），和线程数，cpu核数是可比的。当这个值远大于cpu核数时，说明大部分操作并不耗费cpu，而是让大量线程阻塞着，使用异步可以明显节省线程资源（栈占用的内存）。当这个值小于或和cpu核数差不多时，异步能节省的线程资源就很有限了，这时候简单易懂的同步代码更重要。

异步或bthread

有了bthread这个工具，用户甚至可以自己实现异步。以“半同步”为例，在brpc中用户有多种选择：

发起多个异步RPC后挨个Join，这个函数会阻塞直到RPC结束。（这儿是为了和bthread对比，实现中我们建议你使用ParallelChannel，而不是自己Join）
启动多个bthread各自执行同步RPC后挨个join bthreads。
哪种效率更高呢？显然是前者。后者不仅要付出创建bthread的代价，在RPC过程中bthread还被阻塞着，不能用于其他用途。

如果仅仅是为了并发RPC，别用bthread。

不过当你需要并行计算时，问题就不同了。使用bthread可以简单地构建树形的并行计算，充分利用多核资源。比如检索过程中有三个环节可以并行处理，你可以建立两个bthread运行两个环节，在原地运行剩下的环节，最后join那两个bthread。过程大致如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

bool search() {
  ...
  bthread th1, th2;
  if (bthread_start_background(&th1, NULL, part1, part1_args) != 0) {
    LOG(ERROR) << "Fail to create bthread for part1";
    return false;
  }
  if (bthread_start_background(&th2, NULL, part2, part2_args) != 0) {
    LOG(ERROR) << "Fail to create bthread for part2";
    return false;
  }
  part3(part3_args);
  bthread_join(th1);
  bthread_join(th2);
  return true;
}

这么实现的point：

• 你当然可以建立三个bthread分别执行三个部分，最后join它们，但相比这个方法要多耗费一个线程资源。
• bthread从建立到执行是有延时的（调度延时），在不是很忙的机器上，这个延时的中位数在3微秒左右，90%在10微秒内，99.99%在30微秒内。这说明两点：计算时间超过1ms时收益比较明显。如果计算非常简单，几微秒就结束了，用bthread是没有意义的。尽量让原地运行的部分最慢，那样bthread中的部分即使被延迟了几微秒，最后可能还是会先结束，而消除掉延迟的影响。并且join一个已结束的bthread时会立刻返回，不会有上下文切换开销。

round-robin

总是选择列表中的下一台服务器，结尾的下一台是开头，无需其他设置。比如有3台机器a,b,c，那么brpc会依次向a, b, c, a, b, c, …发送请求。注意这个算法的前提是服务器的配置，网络条件，负载都是类似的

Weighted Round Robin

根据服务器列表配置的权重值来选择服务器。服务器被选到的机会正比于其权重值，并且该算法能保证同一服务器被选到的结果较均衡的散开

不足：

1. 无法快速摘除有问题的节点
2. 无法均衡后端负载
3. 无法降低总体延迟

nginx的WRR算法原理如下：

每个服务器都有两个权重变量：

a：weight，配置文件中指定的该服务器的权重，这个值是固定不变的；

b：current_weight，服务器目前的权重。一开始为0，之后会动态调整。

每次当请求到来，选取服务器时，会遍历数组中所有服务器。对于每个服务器，让它的current_weight增加它的weight；同时累加所有服务器的weight，并保存为total。

遍历完所有服务器之后，如果该服务器的current_weight是最大的，就选择这个服务器处理本次请求。最后把该服务器的current_weight减去total。

动态感知版的Weighted Round Robin

动态感知的WRR
peer.score = success_rate /(lantency * cpuUsage)

具体做法：

1. 利用每次RPC请求返回的Response夹带CPU使用率
2. 每隔一段时间整体调整一次节点的权重分数

不足：

自动刷新权重值，但是在刷新时无法做到完全的实时，再快也不可能超过一个 RTT，都会存在一些信息延迟差。当后台资源比较稀缺时，遇到网络抖动时，就可能会把该节点炸掉，但是在监控上面是感觉不到的，因为 CPU 已经被平均掉了。

best of two random choice

repsonse中附带cpu使用率，信息滞后造成了严重的羊群效应

计算权重分数，每次请求来时我们都会更新延迟，并且把之前获得的时间延迟进行权重的衰减，新获得的时间提高权重，这样就实现了滚动更新

时间衰减系数的滑动平均值：伴随时间，老的均值，权重越来越小，新的response time，越来越高

randomized

随机法，是随机选择一台服务器来分配任务。它保证了请求的分散性达到了均衡的目的。同时它是没有状态的不需要维持上次的选择状态和均衡因子。但是随着任务量的增大，它的效果趋向轮询后也会具有轮询算法的部分缺点。

根据随机算法，将请求随机分配到后端服务器中，请求的均匀请求依赖于随机算法，该实现方式较为简单，常常可以配合处理一些极端的请求，例如热点请求情况。不适合对命中率有要求的场景。

consistent-hashing

Hash哈希是根据Source IP、 Destination IP、URL、或者其它，算hash值或者md5，再采用取模，相同的请求会请求到同一个后端服务器中。该算法无法解决热点请求，会把某个时间段的热点请求路由到某个单机上，造成雪崩效应，同时在扩充和节点宕机时发生命中率急剧降低的问题（hash算法导致），该策略适合维护长连接和提高命中率。Consistanct Hash是对Hash 算法的优化，可以有效的解决宕机和扩充造成的命中率急剧降低的问题。

一致性Hash算法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而一致性Hash算法是对2^32取模，什么意思呢？简单来说，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0~2^32-1（即哈希值是一个32位无符号整形）。

整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1，也就是说0点左侧的第一个点代表2^32-1， 0和2^32-1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环。

下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置。

brpc locality-aware

优先选择延时低的下游，直到其延时高于其他机器，无需其他设置

在DP 2.0中我们使用了一种新的算法: Locality-aware load balancing，能根据下游节点的负载分配流量，还能快速规避失效的节点，在很大程度上，这种算法的延时也是全局最优的。基本原理非常简单：

以下游节点的吞吐除以延时作为分流权值。

比如只有两台下游节点，W代表权值，QPS代表吞吐，L代表延时，那么W1 = QPS1 / L1和W2 = QPS2 / L2分别是这两个节点的分流权值，分流时随机数落入的权值区间就是流量的目的地了。

一种分析方法如下：

稳定状态时的QPS显然和其分流权值W成正比，即W1 / W2 ≈ QPS1 / QPS2。
根据分流公式又有：W1 / W2 = QPS1 / QPS2 * (L2 / L1)。
故稳定状态时L1和L2应当是趋同的。当L1小于L2时，节点1会更获得相比其QPS1更大的W1，从而在未来获得更多的流量，直到其延时高于平均值或没有更多的流量。

具体见：

Locality-aware