Google于2010年4月将一个新的增量索引架构Percolator部署到了websearch index上,并命名为Caffeine(咖啡因)。自己最近发现网上写的日志什么会很快的被Google索引到,而百度则要慢得多,因此特意去找了这篇paper的原文来仔细拜读了下。

Google的Percolator增量索引更新是针对在一个大的数据源中只有少部分被更新需要重新索引而设计的,并没有取代之前的Map/Reduce方式,即原来的索引更新是当增量的数据到达一定规模时,对repository进行MR重新建立索引并加入全局索引。而采用了新的Percolator系统后,每天处理和之前相同规模的文档,平均的生命周期缩短了50%(即从网页被爬取下来到处理,索引完成可以被搜索引擎搜索到的时间间隔)。

Percolator的架构图:

Percolator由Worker, Bigtable, GFS三部分组成,Percolator提供了一系列的observer关联在worker上,这些observer定义需要观察的data table中的columns,当该columns发生变化时,对应的observer会作为一个function call被worker process调用,Percolator的应用程序就是由一系列的observers组成的,每个observer。

阅读全文…

,

扯淡:
百度面试的还在门口等的时候,听见前面面试的铁哥们(俺舍友)貌似就在被问如何对数据进行哈希然后分布到多台机器上,在门外各种焦急,就差短信进去了,但估计发五个字又解释不清。很幸运的,我一进门第一道问题也是这个,面试开了个好头后面就比较容易,都是常规的大数据量处理以及字符串处理的一些算法,然后扯了扯搜索广告系统,很顺利的直接去三面聊天谈offer了,很lucky~

一致性哈希的什么四个要素可以看这里。简单的说就是将缓存的数据和存储数据的机器使用相同的哈希函数映射到同一地址空间上上,每个机器负责整个地址空间中的一定范围内的数据。

阅读全文…

CAP理论中提到一致性(Consistent),可用性(Available),分区容忍性(Partition Tolerance)三者在一个系统中只能同时满足两个,在分布式系统中分区是一定要存在的,系统的设计一般是在一致性和可用性之间做tradeoff。

一致性可以从客户端和服务器端分两种角度来进行描述。从客户端来就是做为观察者如何发现数据的更新,从服务端则是服务器如何来进行整个数据的更新来确保数据一致性。

客户端一致性:

假设系统中有A,B,C三个独立的process/thread做为client,A更新了系统中的某个数据。

  • 强一致性: 在数据更新完成后,任何随后的读都能返回A更新后的数据。
  • 弱一致性: 系统不保证后续的访问会访问到更新后的数据,但如果系统保证在A更新之后再没其他任何对于该数据的更新操作及失败,经过一段时间后,“不一致窗口”,后需的访问都可以访问到A更新后的数据,则是最终一致性,即最终一致性是弱一致性的一种特例。“不一致性窗口”的大小一般依赖于交互延迟、系统负载、复制的replica的个数等因素。

最终一致性又存在如下变体:

因果一致性(Causal consistency): 如果A通知了B它已经更新了数据,那么B的后需操作则读取到A写入的最新值,而与A没有因果关系的C遵守最终一致性语义,并不保证能立即读取到更新。

读自己写一致性(Read-your-writes consistency): 这个名字真难翻译,意思也很好理解,A更新了,A当然总能看到最新的值,这也是因果一致性的特例。

会话一致性(Session consistency): 此是上面那个一致性的实例,访问系统的进程存储在会话中,只要会话存在就能保证read-your-writes一致性,当由于某些失败会话终止后,新建立的会话则不再延续保证。

单调读一致性(Monotonic read consistency): 如果进程已经看到某个数据的值,则后续的读取不会再读到该数据之前的版本。

单调写一致性(Monotonic write consistency): 在此种情况下,系统保证同一个进程的写操作是串行化的。系统如果不保证此一致性就很难编程了。

上述的不同方式在实现中可以进行组合,在最终一致性的实践中,单调读一致性和read-your-write这两种属性经常组合实现。

服务端一致性:

对于服务端而言是如何尽快的将更新分布到系统,以提高用户的体验,有如下三个参数的说明

  • N   数据的备份数
  • W  更新完成时需要确认已经被成功的备份节点个数
  • R   读取数据时需要读取的备份节点个数

当 W + R > N,读和写的备份节点总是有重叠的,可以保证强一致性。当 W + R <= N时数据一致性就无法保证,即弱一致性/最终一致性。

在实际中可根据系统的需要进行W,R,N的配置,R=1,W=N对于读频繁的任务很优化;W=1,R=N对于写操作频繁则比较优化。但当W < (N+1)/2 时,则有可能会导致两个并发的写操作冲突,即他们的写节点不存在重叠。

Amazon Dynamo就设置了R + W > N的quorum-like的备份一致性更新策略,同时也采用了hint handoff的方式实现。即如果一个有N=3个备份的数据分别备份在A,B,C三个节点上,当写到A时,如果A临时的失效,则会把数据写到一个跟此Key无关的节点D上的专用local db,并提示D该数据应该在A上,D会周期的扫描这些数据并试图,当A节点恢复后,D会将该数据发送至A并删除local data.

Hinted Handoff的策略在多个非关系型数据库中都会被采用,包括Cassandra,人人网的Nuclear等。

Cassandra中还提供了多个一致性的Level可供客户端进行选择,包括

  • ZERO: 即一种完全异步的方式实现写,不关心返回
  • ONE:  当有一个节点更新了数据并提交了log,写操作即可返回
  • QUORUM:   N/2 + 1个备份被更新
  • ANY: 在QUORUM上添加了hinted handoff,而其他的一致性模型都要求更新在之前对备份负责的节点上。
  • ALL:  即写操作需要更新成功所有的备份节点。

参考:

Werner Vogels,   Eventually Consistency

Dietrich Featherston,  Cassandra: Principles and Application

    从去年开始接触NoSQL的知识,CAP理论可以说是整个NoSQL运动者的理论指导。

    CAP理论由UC Berkeley的Eric Brewer教授在2000年提出,并于2002年由MIT的Seth Gilbert & Nancy Lynch给出了严谨的证明。

    CAP理论认为以下三者不能同时满足:

    • 一致性(Consistency): 所有的节点在同一时刻看到同样的数据。
    • 可用性(Availability):  节点失效不会影响系统的读写。
    • 分区容忍性(Partition Tolerance): 系统能支持网络分区,即使分区之间的消息丢失系统也正常工作。

    对C、A、P三者的解读很有很多种,具体可以看后面的参考。

    通过上图我们可以看出,根据业务的不同,不同的存储系统会根据自身业务的需求在CAP三者中进行权衡,因此CAP理论的意义应该是一种在分布式数据存储系统设计时tradeoff,而非绝对的认为三者必须舍弃一者,特别是在CAP理论中没有提到系统的响应时间因素,而数据的访问时延是很重要的可用性因素。

    Yale的Daniel Abadi认为CAP理论简单的描述有可能造成错误的解读,重新定义了一个模型PACELC,添加了系统中的Latency描述。

    上图的意思是,如果一个系统需要进行分区,那就必须在可用性(A)或者一致性(C)之间做出一种tradeoff,否则就需要在系统的延迟(L)和一致性(C)之间做出tradeoff,此模型描述了大多数NoSQL数据库中实现CAP理论的方式,也更具备工程中的意义。

    参考:
    Julian Browne, Brewer’s CAP Theory 懒得看英文的可以看译文
    D. Abdi,   Problems with CAP, andYahoo’s little known NoSQL system

    ,

    阅读原文链接地址在这,http://bit.ly/hlFaqL

    Mark一段针对废数据合并的。

    更新和删除操作会产生很多的无用数据,这些垃圾数据的回收是通过定时合并操作实现的,一般可选择每天服务的低峰期,比如凌晨两点启动每日合并任务。

    定时合并(Merge):采用0/1目录的方式,假设当前的服务目录编号为0,合并过程如下:

    1, 关闭目录0的数据文件和索引文件,后续的更新操作(包括合并过程中的更新操作)都写入目录1中新开的文件;

    2, 顺序读取目录0的索引文件,对每一个索引项,对比是否与内存中的内容一致,如果一致,说明是最新的有效索引,将对应的数据追加到目录1中的数据文件,同时生成相应的索引信息追加到目录1的索引文件中并修改内存中的索引项;

    3, 合并过程结束时可以回收目录0中的数据文件和索引文件;

    由于合并过程中可能有更新操作,且都需要追加目录1中的索引文件,因此,需要将索引文件编号分成两段,比如合并过程中写入的索引文件从1开始编号,最大不超过1000;更新操作写入的索引文件从1001开始编号。

    ,