解读Google分布式锁服务

标签: BigTable Google percolator 未分类 | 发表时间:2011-01-04 15:31 | 作者:nosqlfan XiaoHui
出处:http://blog.nosqlfan.com

背景介绍

在2010年4月,Google的网页索引更新实现了实时更新,在今年的OSDI大会上,Google首次公布了有关这一技术的论文。

在此之前,Google的索引更新,采用的的批处理的方式(map/reduce),也就是当增量数据达到一定规模之后,把增量数据和全量索引库Join,得到最新的索引数据。采用新的索引更新系统之后,数据的生命周期缩短了50%,所谓的数据生命周期是指,数据从网页上爬下来,到展现在搜索结果中这段时间间隔,但是正如Google所强调的,这一系统仅仅是为增量更新所建立的,并没有取代map/reduce的批量作业处理模式。

架构Overview

Google的新一代增量索引更新 – Percolator,是建立在Bigtable之上,提供的API也尽量接近Bigtable的方式,所以整个架构大致是如下的样子:

事务(Transaction)和锁(Lock)有区别吗?

在关系数据库领域,二者还是有很大区别的,但是对Percolator而言,Transaction = Lock,所以我们这里讨论的分布式锁,也可以说是分布式事务,所以下面提到的锁或者事务,指的都是同一件事。

Percolator利用Bigtable原有的行锁,再加上自己的一些巧妙的做法,实现了分布式锁服务,这就意味着,Google可以实时的更新PB级别的索引库。最近我们发现Google的搜索结果时效性很好,刚写好的文章,几分钟之后,Google就可以检索到,原因就在Google的Crawler在抓到新的网页之后,不用再等待一定的时间批量更新索引,而是实时的更新,数据生命周期大大缩短。

Percolator支持跨行,跨表的事务,充分利用了Bigtable本身已经有的行事务、备份机制。

简单的示例

在分析Percolator的细节之前,先看一个简单的例子,对Percolator有一个大概的认识,有利于后面的理解。

下面的这个例子是把UserA的人气分减掉10,加到UserB的人气分上,key表示每一行的key,data,lock,write是列名字,data存储数据,lock存储锁状态,write表示事务提交后的数据位置引用.

初始状态:UserA有100个人气分,UserB有50个人气分

最终状态:UserA有90个人气分,UserB有60个人气分

Step0(初始状态)

Key Data Lock Write
UserA 100:t1
UserB 50:t2

Step1(从UserA中拿出10个人气分)

Key Data Lock Write
UserA 90:t2100:t1 Primary Lock:t2 t2
UserB 50:t2

Step2(把UserB的人气分加10)

Key Data Lock Write
UserA 90:t2100:t1 primary_lock:t2 t2
UserB 60:t350:t2 Primary_lock:UserA@data t3

Step3(事务提交)

A:先提交primary(移除锁,写入新的timestamp,在write列写入新数据的位置引用)

Key Data Lock Write
UserA t390:t2

100:t1

t3:data:t2t2
UserB 60:t350:t2 Primary_lock@UserA.data t3

B:再提交非primary(步骤同上)

Key Data Lock Write
UserA t390:t2

100:t1

t3:data:t2t2
UserB t460:t3

50:t2

t4:data:t3t3

事务结束了,UserA有90个人气分,timestamp是t3,Userb有60个人气分,timestamp是t4。(至于锁的写法和write列为什么那样写,后面再详细解释)

事务的执行过程

Percolator锁分为两种,primary和non-primary,在事务提交的过程中,先提交primary锁,无论是跨行还是跨表,primary锁都是没有区别的。

事务的提交

事务的提交的过程分两步,以UserA为例:

首先,在write列写入新数据的位置引用,注意不是数据,是引用(理解成指针会更形象),上面step3A 中t3:data:t2表示在t3时刻提交的数据,最新的数据在data列的t2 timestamp

然后,移除lock列的内容。

因为Bigtable支持行锁定,所以上述两步都是在一个Bigtable事务内完成的。

读操作

当一个client在发起读操作之后,首先会向oracle server申请time stamp,接下来Percolator会检查lock列,如果lock列不空,那么读操作试图移除(修复)这个lock或者等待,在后续锁冲突处理详细介绍如何修复。

补充:oracle发放time stamp是严格递增的,而且不是一次发放一个,而是采取批量的方式。

写操作

当一个client发起写操作之后,首先会向oracle server申请time stamp,Percolator会检查write列,如果write列的timestamp大于当前client的timestamp,那么写失败(不能覆盖新的数据 write-write conflict);如果lock列有锁存在,说明当前行正在被另外的client锁定,client要么写失败,要么试图修复(lock conflict)!

Notify机制

Percolator定义了一系列的Observer(类似于数据库的trigger),位于Bigtable的tablet server上,Observer会监视某一列或者某几列,当数据发生变化就会触发Observer,Observer执行完之后,又会创建或者通知后续的Observer,从而形成一个通知的传递。

锁冲突的处理

当一个client在事务提交阶段,crash掉了,那么锁还保留,这样后续的client访问就会被阻止,这种情况叫做锁冲突,Percolator提供了一种简单的机制来解决这个问题。

每个client定期向Chubby Server写入token,表明自己还活着,当某个client发现锁冲突,那么会检查持有锁的client是否还活着,如果client是working状态,那么client等待锁释放。否则client要清除掉当前锁。

Roll  forward & roll  back

Client先检查primary lock是否存在,因为事务提交先从primary开始,如果primary不存在,那么说明前面的client已经提交了数据,所以client执行roll forward操作:把non-primary对应的数据提交,并且清除non-primary lock;如果primary存在,说明前面的client还没有提交数据就crash了,此时client执行roll back操作:把primary和non-primary的数据清除掉,并且清除lock。

小结

Google的分布式锁服务很好了支持了增量索引的实时更新,缩短了数据的生命周期。本文对notify机制介绍的比较简单,感兴趣的请参考论文原文

来源链接:http://www.searchtb.com/2010/12/distributed-lock-service-in-google.html

分享家:Addthis中国

相关 [google 分布式锁 服务] 推荐:

解读Google分布式锁服务

- XiaoHui - NoSQLfan
在2010年4月,Google的网页索引更新实现了实时更新,在今年的OSDI大会上,Google首次公布了有关这一技术的论文. 在此之前,Google的索引更新,采用的的批处理的方式(map/reduce),也就是当增量数据达到一定规模之后,把增量数据和全量索引库Join,得到最新的索引数据. 采用新的索引更新系统之后,数据的生命周期缩短了50%,所谓的数据生命周期是指,数据从网页上爬下来,到展现在搜索结果中这段时间间隔,但是正如Google所强调的,这一系统仅仅是为增量更新所建立的,并没有取代map/reduce的批量作业处理模式.

Google  的 favicon 缓存服务

- 小猫 - 我爱水煮鱼
在添加友情链接或者其他操作的时后需要应用其它网站的图标(favicon),如 iPad 网址导航,如果一个一个去找会非常麻烦,Google 提供了一个比较快速得到相应网站 favicon 的服务,使用下面的 URL 调用 GOOGLE 的 favicon 缓存,将后面的域名改成相应网址即可,没有favicon的网站会显示一个小地球.

Google关闭字典服务

- Johnson - Solidot
Google在没有给出任何预警的情况下突然关闭了字典服务. Google建议用户“通过 Google 网页搜索查找相关定义,或通过 Google 翻译来翻译相关内容”. Google字典最初Google 翻译的一部分,后成为一项独立服务. 与Google 翻译相比,Google字典提供了更丰富的语义解释、示例,并提供了来自外部来源如维基百科的链接.

如何用redis实现分布式锁

- - CSDN博客数据库推荐文章
redis作为一个强大的key/value数据库,其实还可以用来实现轻量级的分布式锁. 最早官方在 SETNX命令页给了一个实现:. 不过这个方案有漏洞,就是release lock用的DEL命令不支持cas删除(delete if current value equals old value),这样忽略race condition将会出现问题:.

分布式锁看这篇就够了

- - zhisheng的博客
转载请务必注明原创地址为: http://www.54tianzhisheng.cn/2018/04/24/Distributed_lock/. 在单进程的系统中,当存在多个线程可以同时改变某个变量(可变共享变量)时,就需要对变量或代码块做同步,使其在修改这种变量时能够线性执行消除并发修改变量. 而同步的本质是通过锁来实现的.

Google的HTTPS服务不稳定测试

- Freeman - 月光博客
  从2011年3月2日开始,人们发现从国内访问很多Google的HTTPS服务(以下简称服务)开始出现不稳定现象,很多人怀疑是Google的服务或网络不稳定所致. 本文通过技术测试的方法发现服务不稳定的根本原因.   为了测试服务不稳定的原因,我们使用了2台VPS服务器,一台在上海,一台在香港. 这2台VPS服务器上分别运行测试程序,对Google的HTTP服务和Google的HTTPS服务同时进行测试.

Google服务器架构图解简析

- Version - 服务器运维与网站架构|Linux运维|互联网研究
Google,无疑是互联网时代最闪亮的明星. 截止到今天为止,Google美国主站在Alexa排名已经连续3年第一,Alexa Top100中,各国的Google分站竟然霸占了超过20多个名额,不得不令人感叹Google的强大. 不论何时,不论何地,也不论你搜索多么冷门的词汇,只要你的电脑连接互联网,只要你轻轻点击“google搜索”,那么这一切相关内容google都会在1秒钟之内全部搞定,这甚至比你查询“我的文档”都要快捷.

Google运行90万台服务器

- Niclau - Solidot
但根据一份新报告,数字是90万. Google绿色能源团队项目经理David Jacobowitz告诉斯坦福教授Jonathan Koomey,2010年Google数据中心耗电量不到全球数据中心总耗电量的1%. 全球数据中心总耗电量大约1988亿kWh,Google的耗电大约为220MW. Koomey的报告是2007年数据中心能耗报告的最新版.

Google Docs遭遇服务中断故障

- 建军 - cnBeta.COM
北京时间9月8日早间消息,谷歌文档(Google Docs)生产力套装今天遭遇服务中断故障,截至太平洋时间14:35(北京时间9月8日5:35)为止尚未恢复,免费个人用户和企业用户均受到此次故障的影响.

Google服务HOSTS失效解决办法

- - 牛B博客 niub.us
嗯,全国人民喜迎斯巴达,一片和谐之声. google 服务这两天又不稳定了,明显的表现就是 google+ 无法访问,google.com搜索直接被重置. 身在这片儿神奇的土地上,上个网真是不容易呀. 想必很多基友都是使用通过修改hosts访问google网站. 但是, google服务 北京IP 常常被河蟹,于是要寻找可用的IP.