记录学习过程中的点点滴滴
信息检索
Jeff Dean谈如何在大型在线服务中做到快速响应
七 19th
之前在公司内网看到fanli分享过该类的内容,里面提到了backup requests和canary requests,印象比较深刻,也是深有体会,
所以这里就转载下这篇文章,以便后续加深理解。
原文:
Jeff首先以Google的搜索服务为例,说明了何为大扇出服务(Large Fanout Service),即一个搜索请求需要有大量子系统(Web、新闻、图像、视频、博客等等)参与其中,以便提供更丰富的搜索结果。在Google,基本不 会为特定的服务提供特定的机器,而是将服务都部署在一个机器池中,这被称为共享环境(Shared Environment),Google的共享环境大致会包含以下几个部分——Linux、调度系统、文件系统ChunkServer、多种其他系统服 务、Bigtable Tablet Server、随机MapReduce任务、CPU密集型任务以及随机应用。它的好处是可以极大地提升利用率,但同时也会带来诸多无法预测的问题,比如网 络拥塞等等。尤其是响应时间的长尾现象比较明显,一次请求的平均响应时间是10毫秒,但是却有99%ile的响应时间大于1秒,在大扇出服务中,如果需要 调用100台服务器获得最终结果,那有63%的请求耗时会大于1秒。
(备注:99%ile的含义:%ile means the percentage of people ranked below you)
针对延时问题,有些基本的降低延时的技术:
- 定义不同的服务级别,针对服务器上的请求队列和网络流量设定优先级。
- 减 少线头阻塞(head-of-line blocking),将大的请求打散成一系列小请求;比如,一个读请求需要读取64MB数据,而另有一个100KB的读请求必须等前者完成了才能得到处 理,此时可以将大请求分为多个小请求,以便100KB的那个请求能及时得到处理。
- 管理好昂贵的后台活动,比如分布式存储系统中的日志压缩就算昂贵的后台活动,此类活动可以考虑在负载低峰期去执行。
Jeff指出,我们要做的事就是基于一堆不可靠的资源打造一个可靠的整体,基于一堆无法预估的资源打造可以预测的整体。在延时处理方面,Jeff将对应的技术分为两大块:
- 跨请求适应(cross request adaptation),通过检测最近的行为,采取一些措施来优化后续的请求处理,通常会和负载均衡有关,生效时间大约是十几秒到几分钟。
- 同请求适应(within request adaptation),在当次请求中,对响应较慢的子系统采取一些措施,以改善本次请求的整体响应时间,通常是立刻生效的。
随后,他分别就两类技术进行具体展开说明。
google早期的索引结构介绍
三 1st
最近一直在做索引压缩方面的事情,无意中看到了Jeff Dean大牛分享的google早期的索引结构,对于我们这种刚刚起步的搜索公司,还是很有启发意义的,收获还是比较大,所以就简单记录下。
1. 索引压缩常用的压缩算法
淘宝的一篇技术blog分享了一些比较常用的压缩算法:
- varint (变长压缩): 字节对齐,压缩比不高
- group varint: 变长压缩的变形,比varint的解压速率高很多,这里有它的实现
- Gamma: 对比较小的数字压缩比会比较高,将数值分为两个部分: 一元编码(num_bits)+二进制编码
- Simple9 + simple16: 对于32bit的空间进行组织,可存储多个数值
- PForDelta + NewPForDelta: 比较新的压缩算法,压缩比和解压缩比都比较高效,适合于docid_delta的压缩
关于这些算法的相关介绍可以看下www.wikipedia.org,或者搜下对应的paper.
2. Google的索引结构
可以看到,对于token的doclist是以Block的方式进行组织的,如果doclist比较长,还会使用skip table来快速查找;
Block的组织方式:
a. block header: 使用变长存储与上一个block的delta, 并存储block 实际的存储长度(可能是作为验证)
b. 第二行使用Gamma来压缩编码类型及在block中出现的docs的数目(因为这些数值都比较小)
c. 使用Rice压缩对应docld delta, 其实这里可以使用比较新的压缩算法PFDelta,更高效一些
d. 使用Gamma来压缩对应token在doc中出现的frequence, 即hit的数目
e. 使用length-limit Huffman 来存储Hit Attribute信息,这里主要是利用Attribute的重复的比例会很高,也就是说大部分hit attribute
都会是相同的,所以用到了Huffman压缩,然后对length进行了限制
f: positions用Huffman-Int 来压缩位置信息,由于position分布不确定性很多,对position的压缩一直是业界的难题,压缩比不会很高。
Huffman-Int : 类似于Gamma压缩,但是对于一元编码部分,使用了Huffman code.
优化
这里其实可以将doclist和hit 信息进行分离存储,因为只有在打分的时候才会用到hit的相关信息,访问次数会比较少,而doclist就会访问比较频繁
可以对其进行Cache,这样Cache命中率会更高一些
近期评论