RAID1 Hedged requests 实现

作者：刘长伟

一．现存问题

对于用户请求能够快速响应（在100ms以内）的系统，用户体验会比较流畅和自然。随网速提升以及大型数据仓库的建立使得现在的web服务器能够快速响应成千上万的用户。比如google搜索系统，针对不同用户，能够通过基于已输入内容预测用户可能的查询，在数十个微秒内更新显示用户查询结果。随着系统规模，复杂度的不断增加，服务器缩短响应时间波动是十分必要的。在普通情况下看来一个很短暂的延迟，在大规模系统中也会影响整个系统性能。

为什么存在响应时间的波动:

在一个独立的系统中，响应时间呈现出尾部分布由如下几个原因导致：

1. 资源共享

系统在多个应用中共享资源，比如cpu，cpu cache，内存，网络等。

1. 后台服务

后台服务器一般只占用有限的资源，但当该该服务处理数据时，也会对系统性能产生毫秒级的振动。

1. 全局资源共享

运行于不同服务器上的应用有时也会依赖一些全局的资源，比如网关，共享文件系统等。

1. 后台应用

在后台持续运行的一些应用，比如分布式文件系统中数据恢复，日志压缩等行为，也会导致性能颠簸。

1. 队列

在中间的服务或网络的不同层级中使用的大量的队列，也会放大延迟分布效应。

以上是软件因素，硬件因素也可能会导致这种变化。

组件分层实现导致放大效应

在大型系统中减少延迟的一个常用的做法是并发操作,将一个任务分解为多个子任务,并让子任务在不同服务器上并发执行.并发操作将一个根请求分解为大量的叶子请求,最终将所有请求的结果合并.对于一个及时响应的系统,这样的并发操作要求每个子请求必须在固定时间内完成.

如果1个业务操作需要做100次这样的基础操作，它的平均响应时间是1秒。这看起来似乎可以接受，但如果更仔细地计算一下会发现，实际上高达（算式1）的情况下某些基础操作的响应时间将超过1秒，从而导致业务操作的整体响应时间将超过2秒。

即使一个服务只有10,000分之一的请求响应时间超过1s,一个有用2,000个这样服务的系统将会有1/5的用户请求超过1s.

下表真实记录了google服务器的测量数据,也正好符合上述理论.

	50%ile latency	95%ile latency	99%ile latency
One random leaf finishes	1ms	5ms	10ms
95% of all leaf requests finish	12ms	32ms	70ms
100% of all leaf requests finish	40ms	87ms	140ms

二     国内外现状，水平和发展趋势

       目前解决响应延迟波动的方法主要分两类：

通过软件工程技术来解决组件级响应时间波动的方法包括：设置不同服务级别，使用更高层的排队机制；减少队首阻塞；管理后台活动，同步处理。

使用精心的软件工程方法来构建高效的可交互服务是必要的，但是随着系统规模及复杂度的增加，导致无法最终消除系统延迟的波动。Google因此设计了一些tail-tolerant的方法。这些方法主要分两类：

第一类是几十毫秒级的请求内短期调整，主要适用于大多数操作都针对只读、一致性不强的数据集。手段包括Hedged requests和Tied request。

第二类是几十秒到分钟级的跨请求长期调整，针对更细粒度现象导致的延迟波动。手段包括微分区、选择性复制和延迟引导的察看。

 

三   RAID1 Hedged requests 实现目的和意义

       现在很多的web服务器将相同数据部署到多台服务器，这样不但可以增加吞吐量，还能够实现一定的容错性。这种方法也可以用于减少上层响应时间波动。通过该技术可以有效提高RAID1的读效率。

       在云存储项目中，后台采用RAID1技术提供容错性。在利用这一特点，通过在内核RAID1 read_balance的基础上实现hedged requests,可以有效提高度效率。为上层用户提供更快速的响应。

四 内容及关键技术

Hedged requests：

限制响应时间波动的一个简单方法是向多个服务器同时发送请求，并采用最快返回的结果。客户端先向一台认为最合适的服务器发送请求，当该请求超时时，则向第二台服务器发送请求。当这两个服务器有一个返回后，客户端取消其余请求。虽然这种简单的实现增加了一些额外负载。但通过增加适当的负载而降低响应时间的波动还是很有效的。

使用此方法，当发送第一次请求后等待大于此类请求平均响应延迟的95%响应时间后发送下一次请求，能够在有效抑制尾部延迟的同时，额外负载仅增加大约5%。

Tied requests

Hedged-requests 方法还是存在会在多台服务器上同时处理同一请求的弱点。额外的工作可以通过第一次发出请求后等待95% 响应时间然后再发第二次请求的方法来进行遏制。但这种方法仅对一小部分请求有效。

响应时间的延迟主要原因是服务器在处理该请求之前，都会先将请求放入队列中。当请求真正从开始到处理完成的延迟相对较低。Mitzenmacher说，在一个随机系统中，允许客户端根据两个服务器的请求入队时间长度进行选择能够指数级提升负载均衡效率。我们不鼓励这种方法，而是直接向两个服务器发送请求，并允许服务器之间进行通信，来更新该请求的状态。这种方法称为tied-requests,tied-requests的最简单形式是客户端向两个服务器发送请求，发向不同服务的请求都能够标记同时在处理该请求的其它服务器（tied）。当一个服务器开始处理该请求时，如果该请求还在其它服务器上排队，那先向其它服务器发送一个取消请求。

    这里也可能会有一个情况，就是两个准备处理相同请求的服务器都向对方发送了取消命令，比如当两个服务器的队列都为空时，就很有可能出现这种现象。因此,客户端向第一个服务器发送请求后，在向另一个服务器发送求前，引入一个小的延迟，该延迟两倍于平均的网络延迟（在现代数据中心的网络中为1ms或更小）。

 五 实现

IO engine	IOPS	80%	95%	99%	99.95%	99.99%
sync	103	12	16.4	21.1	34.1	51.2
sync_hedged	104	12	16.3	20.9	33.8	53.6
libaio	114	200	314	462	652	719
libaio_hedged	116	198	305	439	616	665
libaio_w	74	325	649	991	1460	1619
libaio_w_hedged	71	327	634	811	1085	1173
syn:普通read 单线程，bs=4k
libaio:iodepth=16，bs=4k，没有随机压力
libaio_w：iodepth=16，bs=4k，随机压力，10%概率对其中一个盘进行read

网易云大礼包：https://www.163yun.com/gift

本文来自网易实践者社区，经作者刘长伟授权发布