1. Overview
实际情况：读比写多，数据源多样。因此需要灵活且通用的缓存系统。
Memcached提供简单的缓存操作（set,get,delete）并可作为分布式系统的组件。初始下，提供的是单点的内存散列表（Memcached），然后将其构建成一个分布式键值存储（Memcache）。
整体架构如下图：
2. 集群中：延迟和负载
主要关注/降低：获取数据的延迟，缓存未命中时的负载
2.1. 降低延迟
原有的架构下，一个外部请求落入Web服务节点，会产生多个memcache请求，落到各个memecache节点上，会造成incast congestion（某个网络组件同时大量发出，接收方来不及处理），导致单点瓶颈。
因此优化在于memcache客户端：
客户端包含序列化、压缩、路由、错误处理、批量请求等功能，而路由表由辅助系统提供更新。
2.1.1. 并行请求和批量处理
根据请求，构建DAG以表示数据依赖，Web服务节点使用它最大化请求的并发度（通常一批有24个键）。
2.1.2. 客户端-服务端通信
memcache服务节点不会直接通信，且可嵌入到进程中。memcache客户端包含2个模块：可嵌入进程的库和单独的代理mcrouter（提供接口代理并路由）。
客户端可通过UDP或TCP和memcache服务节点通信：
- 前者可直连
memcache（不需经过mcrouter和建立连接），并可检测丢包和乱序（不恢复，返回错误，状态为“缓存未命中”，但客户端不会插入从数据库中获取的数据） - 后者需要经过
mcrouter提供更好的可靠性
通常UDP用于
get操作，TCP用于set,delete操作以提高可靠性
2.1.3. Incast Congestion
Memcache客户端实现流量控制以限制incast congestion。
客户端使用滑动窗口以实现流量控制：
- 窗口中代表未收到响应的请求，若收到响应，则移动窗口，下一个请求就可以发送了
- 窗口大小可随成功的请求缓慢增长，若响应失败就缩小窗口（和TCP拥塞控制类似）
- 窗口应用于所有
memcache请求，而TCP只应用于单独的连接/数据流
2.2. 降低负载
2.2.1. 租约
引入租约以解决：过期设置（设置过期的值到缓存）和惊群效应（对某个键大量频繁读写，频繁写导致缓存频繁失效，频繁并发读会造成大量未命中，请求落入DB）。
租约的做法如下：
-
缓存未命中后，
Memcache给客户端一个租约（64位令牌，与键绑定），每当客户端设置缓存值时捎带这个令牌 -
Memcache收到租约后，验证并仲裁数据是否应该被写入仲裁方式类似于load-link/store-conditional：
- load-link：返回内存位置的当前值到寄存器（这里指上层应用）
- store-conditional：在当前位置保存新值（若load-link后内存上的值没被修改，否则返回错误）
-
若是对应键的
delete，让令牌失效
略微改动租约，可缓解惊群问题：
- 可配置
Memcache节点每个主键每10s返回一个令牌 - 在10s内中的请求，若无租约捎带，则告知客户端稍等重试
- 通常拥有租约的客户端会成功设置数据，重试时，数据已经在缓存中
过期值：
在过期数据可接受的场景下，当某个项删除时，Memcache会保存一个标记过期的最近过期值，并存活很短的时间，这样当读请求过来时不需落入DB。
2.2.2. Memcache池
Memcache将整个缓存分割成多个独立的池，默认池为wildcard，不合适放入默认池的项放入其它池中，如：
- 为经常访问，但未命中时开销小的项分配一个小池
- 为不经常访问，但未命中时开销大的项分配一个大池
如A服务的键基本不变，B服务的键经常变动，若不把池加以区分，则A的缓存会被频繁替换，造成性能浪费
2.2.3. 池中复制
在以下场景，可以复制池中的项改善延迟：
- 应用周期性同时读取很多主键
- 整个数据集可放入1~2个
Memcache节点 - 请求速率高，单节点难以承受
即通过复制（多副本）均摊负载，提高性能，不过在修改的时候需要向所有副本分发消息以维护一致性。
2.3. 故障处理
对于小范围故障，则依赖一个自动化修复系统，并引入Gutter接管故障的节点（Gutter数量往往为集群数量的1%）。
当客户端没收到节点回应，则认为节点故障，尝试往Gutter发送请求，并在未命中下插入对应数据。而Gutter的数据会很快过期，以避免Gutter失效。
Gutter的设计避免的故障后的rehash，避免了连锁故障，并将负载转移到Gutter上，降低了失败下DB的负载。
3. Region中：复制
Region：
- 多个front-end clusters，它包含：
- 多个web server
- 多个
Memcache节点
- 数据存储集群
Region架构考虑到更小的故障与和更易控制的网络配置，并使用复制获取更独立的故障域、更易控制的网络配置和更少的incast congestion。
可将Region视为一个数据中心
3.1. Region内缓存无效化
通常而言，数据存储层的修改需要同步到Memcache集群。当web server修改数据后，它也会向Memcache集群发送缓存项失效的命令。
而当数据存储层的事务提交后，会有一个守护进程mcsqueal（每个数据库节点一个）会从日志中抽取相关信息，并广播到Memcache让缓存无效化。
3.1.1. 减少发包频率
mcsqueal会批量处理操作，使用很少的包发送给mcrouter服务节点，然后mcrouter从批量包中分解单独的操作，路由到正确的Memcache节点。
3.1.2. 由web server发送失效命令
存在2个问题：
- 批处理时，没
mcsqueal有效率 - 系统性的无效问题，难以解决（如配置错误导致错误路由），而
mcsqueal可以简单的重新执行，因为数据库有可靠的日志
3.2. Region池
由于用户请求会被随机路由到某个front-end cluster，因此缓存数据会被复制多份。过度复制会造成内存浪费，因此引入region池，即：在一个Region中，被所有front-end cluster共用的Memcache节点集合
它的思想就是增加延迟（因为可能跨cluster访问）以减少内存占用，对访问频率不高的缓存有用。
3.3. 预热冷集群
预热一个新的front-end cluster，可以不从数据库预热，而是从其它的front-end cluster预热，以降低预热时间。
一致性问题：更新请求落入冷集群，造成缓存失效，之后读请求落入冷集群，未命中，然后从热集群拉数据，但失效通知没收到，拉到过期数据，并插入到冷集群中，造成不一致。
解决方法：设置拖延时间（默认2秒），当执行删除操作后，在这段时间内，拒绝插入，表明有更新的数据，这样客户端收到拒绝时就从数据库读取最新的数据。（理论上无法避免一致性问题，但能显著降低不一致的概率）
4. 跨Region：一致性
为保证高可用，多Region往往为主从架构，即：
- 主Region：持有主DB
- 从Region：持有从DB只读副本
对于DB层的写：主DB接收写并复制日志到从DB
对于Memcache的写，可能会落入主和从的Region上：
-
主Region：
-
web server往DB更新，并让同一个front-end cluster的缓存无效化
-
其它Region的失效通过DB层的
mcsqueal守护进程处理失效主DB的
mcsqueal使本Region的所有front-end cluster失效，从DB会收到主DB的日志，并通过自己的mcsqueal使自己的所有front-end cluster失效。
-
-
从Region：使用remote marker机制降低读到过期数据的几率，当web server准备更新键$k$
- 设置该Region的remote marker 为$r_k$
- 往主DB写入，并在SQL中嵌入失效的$k$和$r_k$
- 在本front-end cluster删除缓存的$k$，后续的读会检查$r_k$：
- 若存在，则请求重定向到主Region
- 否则定向到自己的Region
- 主DB收到更新后会将更新广播到从（当前）Region
- 从（本地）Region收到更新后，守护进程负责把所有front-end cluster的$k$和标识$r_k$清除
实现而言，使用Region池实现，$r_k$被整一个Region共享。
当同一个键并发修改，另一个操作删除remote marker时，可能返回过时数据，但是几率很小。
Revision：
Memcache池被一个front-end cluster共享；Region池被一个Region（所有front-end cluster）共享。
运行上的考虑：将缓存同步流（实际上是缓存delete stream）与DB复制的信道共用，可提高网络运行效率、降低带宽。
5. 单点提升
5.1. 性能调优
基本优化：
- 允许散列表自动扩张（否则查询时间区域线性）
- 使服务器多线程运行，并使用全局锁保护多个数据结构
- 每个线程有自己的UDP端口，减少竞争
前2个已经贡献到开源代码中
在此基础上，还有：
- 降低锁粒度（全局锁粒度太大）
- 使用UDP通信
5.2. 适应性的slab分配器
Memcached使用slab分配器管理内存，算法大概是：
- 定义不同的内存块（slab class）大小，从64字节到1MB，等比1.07
- 每个slab class预先分配对应的内存块
- 申请内存时，找到对应的slab class，通过free list找到空闲块，若找不到，则使用LRU替换得到空闲块
而在此之上，实现了一个适应性分配器，周期性平衡slab分配以适应当前负载，给不同的slab class动态分配不同的大小。
5.3. 临时项的缓存
Memcached支持过期时间，过期项可以留在内存中，只有它再次被请求或者被LRU替换时，才会被检查清除。即原有的只支持懒惰/延时删除，这种方式对偶尔活跃的项不适合。
在此基础上，增加周期/立即删除的功能，适用于短期过期项：
- 将这些项放入临时项缓冲区（一个环形链表）
- 每隔1秒，遍历链表，过期项则被删除
5.4. 软件升级
软件升级时，往往需要重启并预热。
因此这里修改了Memcached，使用System V共享内存（即使用进程间通信/IPC，具体见此），将缓存项放入共享内存，升级的进程可从共享内存读取。这样升级过程中，数据依旧可用。
