过去半年里参与了阿里云Redis数据库的开发，随着用户数的逐渐增多，遇到了许许多多的技术上的问题，本篇文章讲系统遇到的连接超时问题，希望日后对他人起到一点借鉴作用。

系统介绍

在说问题之前，首先简单介绍一下我们系统在数据层的架构，它主要包含4个组件，负载均衡服务器SLB，代理服务器Proxy，后端Redis服务器，以及一个探测系统Detector负责诊断数据链路的各个部分的网络联通状态，架构如下图。

每个Redis实例对应一个域名xx.region.kvstore.aliyuncs.com，端口都为6379，用户通过该域名进行访问。每个域名将通过DNS解析成一个唯一的VIP。

每个VIP对应一组后端的Proxy，通过SLB将请求进行转发。分组的原因是为了避免问题的影响范围(我们限制每个组里的Proxy负责的后端的Redis实例数目（200个为一组)，防止因为某个客户触发了Proxy的BUG影响所有客户。

VIP到Proxy的链路由负责均衡服务器SLB控制，它是四层的负载均衡器，采用透传模式，负责用户请求的接入并把用户的VIP放在TCP包的Option字段中，请求的回复直接通过Proxy返回。
Proxy通过TCP包的Option字段，获取用户需要访问的VIP，接着将请求转发到后端Redis实例。由于需要全兼容redis协议，支持事务和Pub/Sub, Proxy采用的是一对一的连接方式，用户建立多少连接，Proxy也随即建立多少连接。
Redis是直接部署在物理机之上，每台物理机平均部署超过200个Redis实例。

Read More

热点Key问题

大促期间的另一个常见问题是Key热点问题。部分Key(可能对应用与某个促销商品)集中于同一机器量，使得所有流量涌向同一机器，成为系统的瓶颈。该问题的挑战在于它无法通过增加机器容量来解决。

解决该问题的办法有很多，最有效果的方式是在业务层对热点数据进行切分。但对于有些情况，如小米双11促销，单台小米机型QPS超过百万，业务无法进行切分。

该问题最常见的解决办法是多写策略。如搭建备用集群，写的时候双写或者异步同步，读的时候就相应的能从多个地方读。但上述方案对于双11这种读、写压力都很大的场景，还是略显不足。

还有就是通过牺牲数据一致性来提升访问效率。一种是针对读的客户端缓存，另一种是针对写的由Facebook Memcached论文中提出Lease租约策略。

客户端缓存的思想是将部分热点内存缓存在客户端，而避免每次访问都去访问服务器。其缺点是本地缓存可能不是最新的。
Lease租约策略则要求每次写key时，都需要事先获得该Key的Token。这能有两个用途，一方面是避免写后读问题，详细可以看这里。另一方面服务器可以通过控制连接在每秒获取Key的频率达到限流的作用，避免写入过多，造成惊群效应。

设计

通过对我们承接的业务进行分析，在促销期间应用对于数据一致性的需求要远低于可用性的需求，他们能容忍数据在短时间内不准确。依据该原则，我们选择客户端缓存办法。
客户端缓存方案包含两个部分，服务端热点统计和客户端本地缓存。
服务端热点统计是用于探测服务当前热点，客户端缓存是将服务端的热点数据存于本地，待下次访问时直接返回。

服务端热点统计

服务端热点Key统计的办法有很多，最常见的办法是直接抽样N次请求取出Topk让客户端进行缓存，但该方法存在一个很大的问题：Topk的准确性，依赖于抽样的次数。较少的抽样次数，可能导致热点key不准确，且频繁发生变化。而较多的抽样，可能提升热点key探测花费的时间、导致热点已过，同时还提高了内存占用。
我们需要一个自适应的抽样办法，能在热点出现时及时发现。这里我们提出了一种双层抽样办法。它分为采样阶段和定位阶段来探测热点key，最后定时反馈热点key给客户端。其具体流程如下。

Read More

每年一度的双11已经过完，相比往年不同今年有幸参加了双11全过程。我所在的缓存团队承担着双11很重要的职责，负责存储商品库存、全站用户Session、购物车等峰值QPS上千万级别的大业务。值得骄傲的是，团队的服务除了在0点时极短时间内对购物车和无线业务实施了限流，整个过程异常稳定。
关于如何架构亿万级别QPS系统或者秒杀系统，之前在网络上已经讨论的很多，主要涉及负载均衡、CDN、缓存、静态化、降级、限流、数据压缩等。但那些讨论往往面太广，趁着现在双11余韵还在，本篇文章将站在我们的键值存储服务Tair系统的角度来阐述，我们是如何应对双11的。

流量突增问题

大促最明显的现象是在短时间内有海量并发，造成服务器过载，资源使用率急剧提升，服务响应变慢，甚至有宕机风险。
解决办法分大致分为两类，提前预防，案发时应急处理。

提前预防是在大促发生之前做的准备工作。它依赖于客户在事先对其使用资源的评估，一次好的预估往往比临时的应急处理方案要更有用的多。通常在大促发生之前，我们通过多次对促销时流量的模拟，反复调整机器的数量，最后设置一个合理的值，这里主要考验的是对系统和用户行为的了解。

但通常我们很难保证业务方对于资源的使用有着准确的预估，当超过预期的流量导入到系统的时候，系统需要应急办法来处理。
对于我们缓存系统，应急办法主要涉及两种：

1. 集群的扩容
   通过增加机器的方式，来均摊负载。该办法思路简单，但在实践过程中，如果直接使用，效果往往很差。因为在机器负载很高的时候，我们执行的扩容操作可能会进一步恶化系统性能。针对我们缓存系统，在大促时命中率往往超过99.99%，贸然的集群扩容，将极有可能击穿后端存储系统。
   为了解决这个问题，我们在扩容之后会事先对集群进行预热，只有当命中率达到预期后才执行扩容。

2. 流量控制系统
   当远超出预期的请求到达服务时我们需要一种机器资源的保护策略：流量控制。在海量并发请求到来时及时返回错误告知客户端减少请求发送数量，让客户端直接收到返回错误，这样的收益来自两个方面：

   • 1.避免服务器过载。如过长请求排队造成的无谓的CPU、内存、网络等性能损失。
   • 2.客户端快速收到错误，使其进入错误处理逻辑。（如直接读本地内存或磁盘）

对于我们的缓存系统，该方法极为关键。系统采用的是做租户模型，承接了公司内部超过500个应用，各个应用公用一个集群。如果因为少数应用的并发流量影响整个系统，将造成极大的灾难。其次不同的应用的关键程度不一，我们需要一个更灵活的资源管理办法来实现服务的等级以及关键时候的降级。

支持服务分级的流量控制系统

我们提出了基于流量控制的有限服务使用承诺。应用在申请接入我们服务之前，将需要提供其预期的资源使用量。这包括两个值：

1. 基本的资源使用量，不管在任何时候，我们的服务都需要提供以上资源(如100w QPS，1w连接，1GB流量)。
2. 最大资源使用量(如150W QPS, 2w连接)，当客户资源使用量超过该值时，我们将限制其资源使用。

在提供上述全局维度的服务承诺同时，还限制了单机维度的资源使用(如单机5w QPS，1000连接)。

对于单机维度的限流，它的实现较简单，统计实例级别实时的资源的访问后，计算出流控状态，定时推送给客户端即可，这里不做过多阐述，主要介绍实例维度的限流。

实例维度的限流，是指在集群层面限制单个应用的整体的资源损耗。由于我们缓存服务采用的是多租户模型，应用的数据分散在集群中多个服务器中，其架构如下图。
。
为了统计应用的全局的资源访问信息，数据服务器将各个应用消耗的资源信息统一汇聚到Collector服务器。

Collector汇总后，推送需要限流的实例给数据服务器，接着数据服务器收到后向客户端发出限流命令。
客户端会根据限流命令来以一定概率直接反馈错误，达到限流的效果。

ConfigServer是元数据节点，负责存储提前协商好的资源使用信息，并定时推送该信息给Collector。当临时需要对服务进行降级时，也是通过向ConfigServer发出请求，实现临时限流。

流量控制系统的具体实现

Collector实现

在收集端Collector负责汇总和计算客户端的流控状态。我们将提前会为每个应用设置事先约定的低水位和高水位阈值在Collector数据库中。Collector通过该阈值来控制实例限流的状态。

每个实例限流有三种状态：Up, Keep, Down。当超过高水位线开始发出限流指令，并设置状态为Up。当处于低水位线和高水位线之间时，将设置为Keep，低于低水位线时为Down。Collector将定时推送实例的流控状态。

• 高可用
  由于Collector在限流系统中处于核心地位，为了保证其高可用，每个集群启用两台彼此不交互的Collector。
  每次实例将访问流量推送给两个Collector，它们都会进行计算，并推送限流结果。数据服务器收到任意一个限流结果，都会进行流控。

客户端实现

在客户端，客户会维护一个限流窗口值Threshold，并根据服务器推送的限流状态，来调整该值。其具体的计算方式如下：
初始时该窗口值为0。当收到服务器Up限流命令时，会提高限流值。Keep时，保持该值。Down则降低限流值。其公式为：

1

Threshold = Threshold + UP_FACTOR*(MAX_THRESHOLD-Threshold)
Threshold = Threshold + DOWN_FACTOR*Threashold

计算出该值后，在每次访问时，都会首先random(0, MAX_THRESHOLD)的值，来与当前Threshold值进行比较，如果低于它则直接返回错误。

线上运行效果

在实际运行中我们设置上下因子为0.25，MAX_THRESHOLD为1000。通过服务端和客户端相结合的方式，我们实例资源使用量处于低水位线到高水位线之间的效果，真实数据如下图：

延伸阅读

1. 淘宝开源Key/Value结构数据存储系统Tair技术剖析
2. 由12306.cn谈谈网站性能技术
3. 移动互联网海量访问系统设计

流控设计背景

阿里云redis服务的一款云产品，它是一个全内存的NoSql数据库，除了内存、CPU资源管理外，流量控制也是保证服务稳定性的重要一环。Redis服务的数据流节点包括proxy节点和存储节点，所有实例的数据访问都要先经过proxy，然后转发到后端对应的redis进程。后端每个存储节点上最多可以部署几百个redis进程，而这些进程一般都属于完全不同用户实例。 我们的服务是以实例为单位来管理用户数据的，内存容量是最核心的资源，实例按存储容量从低到高划分为10种规格，每种存储规格都包括qps、 进/出流量、连接数资源在内的最大使用限制，例如：

流量控制架构

我们知道redis本身是没有流量控制的，为此我们服务专门增加了一个proxy层来对数据流做控制，客户端的所有请求都要先经过proxy鉴权，鉴权通过才转发给后端对应的redis进程，最后再由proxy将结果回复给客户端，如下图。

Read More

这段时间在工作中遇到一起因为客户发送非法协议触发的Proxy解协议的BUG，影响了大多数用户13分钟服务不可用。此类Bug大家在写C++程序时可能也经常会遇到，特别对于云服务场景，客户端种类多样，导致此类BUG很难预防，同时造成的危害巨大。实际上此版本的Proxy已经上线超过两周，此前测试和回归Case也已经跑了1个月。
结合此前3月也出现过一起因为某特殊逻辑引起连接未关闭，导致文件描述符猛涨到20w后，超过操作系统限制，导致Accept死循环的BUG，本文从代码、部署和Bug处理层面探讨如何能最大限度的避免该问题。

1. 代码安全

代码覆盖率

最直观和直接的办法是保证单元测试和功能测试覆盖所有代码。但通常这只是解决该办法的第一步，很多时候我们即便覆盖到了所有代码，仍然存在bug。特别对于没有虚拟机保护的C和C++程序。
这时需要将系统与外界出现交互部分的逻辑梳理出来，大家一起做CodeReview。列举出各个依赖所有可能出现异常，并一一核对代码的处理情况。
特别对于复杂的用户输入，如协议处理，采用从后往前，尽全力构造躲过系统判断的输入。

代码Review负责人

现在各个团队代码开发任务都很大，虽然大家提提Review，但是很多时候，大家只是一扫而过，而并没有仔细为他人去考虑各个可能出问题的逻辑。 为每个项目至少设置一个代码Review负责人，并要求其对代码承担一定责任。

其它

除开常用的内存检查工具valgrind，当前存在很多种代码扫描工具，如Clang，上线前对代码进行一次检查，是很有必要的。很多时候一个灾难性bug可能仅仅源于没有初始化某个变量。

Read More

简介

在分布式系统中，一个经典的问题是如何高效、可靠的保证运行集群中各个节点数据保持一致。Paxos算法是解决该问题中最广为人知的算法，它由Lamport提出，但由于其描述的较为晦涩，同时存在多处省略，在实现过程中往往有很多细节难于处理，在工程中存在许多类似而又不统一的实现。ZooKeeper使用的Zab算法实际上和Paxos存在很多地方的不同。
Raft算法是由Stanford教授提出为了帮助学生理解的同步算法，它和Paxos算法类似，能保证集群数据的强一致性，但它的概念相比Paxos更少，也更便于理解，论文在这里，结合youtube上的教学视频一同观看效果更佳。

现状

当前已经存在许多知名开源系统基于Raft，如Etcd, Consul等。同时还有些系统如SeaWeedFS, InfluxDB采用内嵌的形式实现了Raft协议。
我也简单的基于Goraft，基于leveldb实现了简单示例性质的强一致存储系统。

算法目标

在讲述Raft算法之前，我们首先讨论一致性算法的要求，它包括以下四个方面：

1. 算法需要能够承受各种类型的错误。
2. 一半以上的节点能运行集群能够正常运作
3. 每个操作只要一半以上的节点成功执行就算成功
4. 不能依赖于任何外部时序

实现

Raft协议基于复制状态机（replicated state machine），即一组server从相同的初始状态起，按相同的顺序执行相同的命令，最终会达到一直的状态，如下图所示，一组server记录相同的操作日志，并以相同的顺序应用到状态机。

它将一致性问题进行分解为“集群选举”和“复制日志”两个部分。 集群选举过程是为了从集群中会选出唯一的leader负责服务客户端的请求。而复制日志过程，是为了保证所有server的状态和最终达到跟leader一致。

集群选举

集群节点类型

集群中节点有三种类型，分别为: Leader, Follower, Candidate。 在初始时，大家都为Follower。通过选举产生集群的Leader。

• 在任何时刻，集群只有一个Leader。Leader负责接收所有用户请求，并通过”复制日志”方式同步给Follower。

• Follower以被动的方式运行，只负责响应请求，而不主动发出请求。

• Candidate状态是集群选举开始后，希望变成Leader节点的临时状态。

集群选举过程

Leader定时向Follower发送心跳信息，当某个Follower长期未接受到Leader的心跳信息，Follower将发动新一轮的Leader选举，这时它会做两件事情。

1. Follower变换其状态为Candidate
2. 将当前的Term+1，发起投票请求。

对于每一轮选举(对应一个Term)，每个节点只能投一次票。 节点收到投票请求后，将比较请求中的Term与自身的Term。此时有三种情况：

1. 请求的Term与当前Term相同
   节点此轮还未投过票，此时将返回同意请求。
   节点此轮已经投过票，不做回应
2. 请求的Term大于当前Term
   表明节点已经落后，更新节点的Term，返回voteGranted = True
3. 请求的Term小于当前Term
   不做回应

Candidate对于投票的反馈

1. 当前节点被选为新的Leader
   当节点收到超过一半节点的投票，确定其是新的Leader。此时将状态更新为Leader，发送新一轮心跳请求，告知其他节点Leader已经产生。
2. 收到来自Leader的数据写入请求，且term >= 当前节点的term
   更新Term为请求反馈的Term，变更状态为Follower
3. 投票超时仍没有收到超过一半的确认
   递增Term，等待一段时间，开始新一轮的选举

Read More

   在英旅行期间，偶遇一个在美读研学社会福利(social warefare)的妹子。她的专业要求至少需要1000小时的社会实践，于是她在上课的同时还需辗转于多家社会保障组织，最近就在日内瓦的世界卫生组织实习了三月。不知怎的和她聊到了日后的目标， 她满脸兴奋的说，要是能去非洲一个欠发达地区(比如刚果)工作几年，了解当地的不同文化，感受到世界的五彩缤纷，使人生多一些阅历，多一些思考。接着转过头来问我同样问题， 被她这个充满着浪漫主义色彩的答案震慑住的我，想了想说，想过一个能自给自足并能自得其乐的生活，不用大富大贵，但也不必为生计担忧。她当然对这个答案不满意，觉得生活应该充满更多的色彩和乐趣。但又好像有些犹豫，可能考虑到生计也是必要的。而我也有些不安，觉得目标里确实差了点什么。
   在我看来，人生目标集中反映了双方的人生观和价值观。我从小比较低俗，是较典型功利主义者，谈到生活，首先想到的是如何让自己幸福，而生活得快乐才能让自己幸福。从小在伟大祖国的教育熏陶下，让我一直有一种思想，有趣必须是那些能让我乐呵的，亦或是那些在短期内我能取得一定”成就”的。所以我认为玩电子游戏，和同学一起出去旅游，唱K是有趣的，而除了工科学科其它也是无趣的。做个简易电话，计算机写两个程序，我觉得不错。但人文，特别是地理、历史，政治，是我极为讨厌的学科，因为我觉得不接地气，纯粹是陈述事实，而这些事实又是那么的虚无缥缈。记得高中之前，家里人老说我学习不好，让我好好努力。我总是功利的反问道，学的那些一点用都没有，你说我知道那唐朝什么贞观之治是多少年有什么意义，你说让我证明数学的那些三角形相似，全等什么可以干嘛。我爸总是一句，人生中很多东西都是没有用的，但是却是潜移默化的。我当然不认可这种蹩脚理论，然后不免一场争吵，当然最后都是我胜利告终。

Read More

百度最近在MSST 2015发布的一篇介绍百度云使用的K/V存储系统Atlas的论文，详细介绍了系统的设计理念和思路，内容丰富，干货很多，有兴趣的务必读一下论文。本文简要介绍一下系统的设计，抛砖引玉。

系统的特点

百度云盘为每个用户提供了2T的使用空间，在这些数据的特点有以下

• 百度云94%的文件在[128KB-256KB]之间，所以atlas主要针对小文件存储
• 百度云前面有CDN，到达atlas的请求基本都是随机访问，atlas是随机访问的存储引擎，不支持range操作

架构

对外系统暴露三个简单的接口：

在设计上系统分为两层，上层PIS(Patch and Index)，负责文件到文件块的映射和临时数据的写入。
下层RBS(Raid-like Block System)用来实际存储数据。
用户在使用时，首先访问PIS的元数据服务器，获取PIS的路由表。接着通过文件名进行hash，在路由表中找到对应的PIS服务器，向其发出请求。

PIS系统

PIS是系统的入口，它提供基于文件的三个接口Put, Get, Delete。同时负责存储文件到文件块的索引，和临时数据块。
在设计上，它采用中心化设计，分为Master节点和数据节点。由Master负责管理全局PIS的存活情况和系统路由，数据节点负责存储索引文件。

上图为PIS模块图，为了保证数据的强一致性，用户请求到达PIS时，它将首先生成该文件对应的ID，接着经由复制模块，将此文件复制到两个从节点。
当复制完成后，PIS将数据写入临时的Block中。每个Block最大为64MB。
接着在Index中，记录此文件ID在临时Block的位置的偏移和文件长度
一旦Block超过64MB，将会对该文件进行打包不再修改，并经由RBSClient传给RBS。

Index采用定长形式存储，引擎采用LevelDB。
它的每个Key是128位全局独立ID。Value是由三元组成(BlockId, Offset, Length)。分别对应文件块ID，块上的偏移和文件的大小。
由于每条记录都很小，LevelDB在执行Compaction操作的代价也较小。

RBS系统

RBS负责文件块的存储，它提供文件块的写入，删除和指定文件块偏移和长度的读取。
它同样采用中心化设计，中央节点维护RBS节点存活情况和文件块到RBS的映射，以及数据迁移和灾难恢复。

为了保证系统的高可用性和存储，采用Erasure Code编码，Erasure Code之前广泛使用在RAID系统中，算法要求每次需要提供4个大小相同的块，并为其两个新的块。从而保证对于6个文件块，任意丢失两个及以下的块系统的数据仍然能恢复。
在将64MB文件快写入RBS中时，会事先划分成8个8MB的文件，编码后形成新的4个8MB文件，存在12个RBS数据节点中。
为了方便寻找这12个文件，此前生成的BlockedId最后4位会是0，再此处将分别填上从1-12的ID。
RBS客户端发出写入请求时，会首先通过中心节点，询问可以写入文件块的服务器地址，接着直接对数据节点发出写入请求，写入成功后通知RBS中心服务器。
为了防止部分节点出现故障影响文件块的写入，在写入12个文件之前，RBS客户端会首先向RBS中央节点请求15个IP，当有节点失败时，尝试下一个。

Read More

在海量数据，高并发时代的今天，单机由于其CPU，磁盘IO，网络带宽以及存储空间等原因，已经不再能及时响应用户的所有请求，系统都开始走向分布式，由多台机器组件成一个集群响应用户请求。具体到分布式存储系统，一个很重要的问题就在于数据的同步。本文将简要介绍当前较为流行的数据同步方案，简要分析其原理和利弊，希望能起到一个抛砖引玉的作用。

数据同步初步

数据同步的基本思想很简单，就是将单台机器上的用户数据和请求，通过复制Replicate的方式复制用户的操作命令到多台机器执行。从而应对当某台机器出现故障时，数据仍能存其他机器获取。
一种最朴素的实现方式是采用多台机器构成集群存储数据，机器按照职责分为一个主节点和多个从节点。其中主节点负责接收用户的数据请求，在本地执行用户请求的同时，将数据复制到集群中其他从节点。

上图中描述了同步复制的基本流程。

Read More

fixture

fixture是pytest特有的功能，它用pytest.fixture标识，定义在函数前面。在你编写测试函数的时候，你可以将此函数名称做为传入参数，pytest将会以依赖注入方式，将该函数的返回值作为测试函数的传入参数。
如下面的例子，我们首先定义了hello函数，并将其标记为fixture，在test_string函数中，我们将它作为入参使用。

1
2
3
4
5
6

@pytest.fixture()
def hello():
    return "hello"

def test_string(hello):
    assert hello == "hello", "fixture should return hello"

fixture提供给开发者多种可能性，可以把它当做对象创建者，充当测试开始前的准备函数（类似setup_function)，还能为测试函数提供多种不同参数fixture对象。

Read More