解读Google分布式锁服务

阳光穿透心脏的1/2处 2022-04-12 11:07 177阅读 0赞

## 背景介绍 ##

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

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

# 架构Overview #

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

![1357476691_2000.png][]

事务（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(初始状态)

<table style="padding:0px; margin:10px; font-family:'Helvetica Neue',Helvetica,Arial,sans-serif; text-align:center; color:rgb(56,56,56); font-size:15px"> 
 <tbody style="padding:0px; margin:0px"> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">Key</td> 
   <td style="padding:0px; margin:0px">Data</td> 
   <td style="padding:0px; margin:0px">Lock</td> 
   <td style="padding:0px; margin:0px">Write</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserA</td> 
   <td style="padding:0px; margin:0px">100:t1</td> 
   <td style="padding:0px; margin:0px">&nbsp;</td> 
   <td style="padding:0px; margin:0px">&nbsp;</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserB</td> 
   <td style="padding:0px; margin:0px">50:t2</td> 
   <td style="padding:0px; margin:0px">&nbsp;</td> 
   <td style="padding:0px; margin:0px">&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

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

<table style="padding:0px; margin:10px; font-family:'Helvetica Neue',Helvetica,Arial,sans-serif; text-align:center; color:rgb(56,56,56); font-size:15px"> 
 <tbody style="padding:0px; margin:0px"> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">Key</td> 
   <td style="padding:0px; margin:0px">Data</td> 
   <td style="padding:0px; margin:0px">Lock</td> 
   <td style="padding:0px; margin:0px">Write</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserA</td> 
   <td style="padding:0px; margin:0px">90:t2100:t1</td> 
   <td style="padding:0px; margin:0px">Primary Lock:t2</td> 
   <td style="padding:0px; margin:0px">t2</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserB</td> 
   <td style="padding:0px; margin:0px">50:t2</td> 
   <td style="padding:0px; margin:0px">&nbsp;</td> 
   <td style="padding:0px; margin:0px">&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

Step2(把UserB的人气分加10)

<table style="padding:0px; margin:10px; font-family:'Helvetica Neue',Helvetica,Arial,sans-serif; text-align:center; color:rgb(56,56,56); font-size:15px"> 
 <tbody style="padding:0px; margin:0px"> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">Key</td> 
   <td style="padding:0px; margin:0px">Data</td> 
   <td style="padding:0px; margin:0px">Lock</td> 
   <td style="padding:0px; margin:0px">Write</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserA</td> 
   <td style="padding:0px; margin:0px">90:t2100:t1</td> 
   <td style="padding:0px; margin:0px">primary_lock:t2</td> 
   <td style="padding:0px; margin:0px">t2</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserB</td> 
   <td style="padding:0px; margin:0px">60:t350:t2</td> 
   <td style="padding:0px; margin:0px">Primary_lock:UserA<a href="http://my.oschina.net/difrik" style="padding:0px; margin:0px; color:rgb(68,102,187); outline:0px" rel="nofollow">@data</a></td> 
   <td style="padding:0px; margin:0px">t3</td> 
  </tr> 
 </tbody> 
</table>

Step3(事务提交)

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

<table style="padding:0px; margin:10px; font-family:'Helvetica Neue',Helvetica,Arial,sans-serif; text-align:center; color:rgb(56,56,56); font-size:15px"> 
 <tbody style="padding:0px; margin:0px"> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">Key</td> 
   <td style="padding:0px; margin:0px">Data</td> 
   <td style="padding:0px; margin:0px">Lock</td> 
   <td style="padding:0px; margin:0px">Write</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserA</td> 
   <td style="padding:0px; margin:0px">t390:t2 <p style="padding-top:0px; padding-bottom:0px; margin-top:0px; margin-bottom:15pt; line-height:1.5; letter-spacing:1px"> 100:t1</p> </td> 
   <td style="padding:0px; margin:0px">&nbsp;</td> 
   <td style="padding:0px; margin:0px">t3:data:t2t2</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserB</td> 
   <td style="padding:0px; margin:0px">60:t350:t2</td> 
   <td style="padding:0px; margin:0px">Primary_lock@UserA.data</td> 
   <td style="padding:0px; margin:0px">t3</td> 
  </tr> 
 </tbody> 
</table>

B：再提交非primary（步骤同上）

<table style="padding:0px; margin:10px; font-family:'Helvetica Neue',Helvetica,Arial,sans-serif; text-align:center; color:rgb(56,56,56); font-size:15px"> 
 <tbody style="padding:0px; margin:0px"> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">Key</td> 
   <td style="padding:0px; margin:0px">Data</td> 
   <td style="padding:0px; margin:0px">Lock</td> 
   <td style="padding:0px; margin:0px">Write</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserA</td> 
   <td style="padding:0px; margin:0px">t390:t2 <p style="padding-top:0px; padding-bottom:0px; margin-top:0px; margin-bottom:15pt; line-height:1.5; letter-spacing:1px"> 100:t1</p> </td> 
   <td style="padding:0px; margin:0px">&nbsp;</td> 
   <td style="padding:0px; margin:0px">t3:data:t2t2</td> 
  </tr> 
  <tr style="padding:0px; margin:0px"> 
   <td style="padding:0px; margin:0px">UserB</td> 
   <td style="padding:0px; margin:0px">t460:t3 <p style="padding-top:0px; padding-bottom:0px; margin-top:0px; margin-bottom:15pt; line-height:1.5; letter-spacing:1px"> 50:t2</p> </td> 
   <td style="padding:0px; margin:0px">&nbsp;</td> 
   <td style="padding:0px; margin:0px">t4:data:t3t3</td> 
  </tr> 
 </tbody> 
</table>

事务结束了，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机制介绍的比较简单，感兴趣的请参考论文[原文][Link 1]。

摘自：http://my.oschina.net/u/593721/blog/100389

[Google]: http://blog.nosqlfan.com/tags/google
[1357476691_2000.png]: https://img-my.csdn.net/uploads/201301/06/1357476691_2000.png
[Link 1]: http://www.google.com/research/pubs/pub36726.html