【观点】漫谈推荐系统及数据库技术(二)——分布式数据库技术

【导读】推荐系统和数据库技术,一个是偏机器学习数据挖掘相关的应用,一个是偏系统存储相关的技术,这两者在实际中有很大的应用。上一次专知推出漫谈推荐系统及数据库技术(一),大家反响热烈,特别是很多工业界的人士点赞支持,今天算法工程师宋强继续漫谈自己一些工作的独到见解,欢迎阅读~

漫谈推荐系统及数据库技术(一)

蹉跎岁月,年华易逝。再次闲聊下分布式数据库技术,博各位一阅。

▌分布式数据库


相较于传统的单机数据库,分布式数据库有以下的几个特点:

为了更好支撑分布式事务,分布式数据库的研发人员做了很多的方案寻优。

▌概念科普


类似于单机数据库中遇到的高并发业务场景,分布式数据库同样面临着困惑。在并发读写数据库时,读操作可能会不一致的数据(脏读)。为了避免这种情况,需要实现数据库的并发访问控制,最简单的方式就是加锁访问。通俗来说,加锁会将读写操作串行化,所以不会出现不一致的状态。但是,读操作会被写操作阻塞,大幅降低读性能。

对此,研究人员提出了一种解决方案:MVCC(Multi-Version Concurrent Control),即多版本并发控制。在MVCC协议下,每个读操作会看到一个一致性的snapshot,并且可以实现非阻塞的读。MVCC允许数据具有多个版本,这个版本可以是时间戳或者是全局递增的事务ID,在同一个时间点,不同的事务看到的数据是不同的。当存储的历史版本数据足够多时,可以使用GC(Garbage Collector)对其进行清理。

▌提出问题


在分布式环境中,普遍存在这么一个症结:快慢钟现象。举个例子:张三在武汉时间8:06分给李四汇款,汇款成功后,通知李四去查账。李四在深圳时间8:03分查不到,需要在深圳时间8:07分才查到了帐。这违背了可重复读的原则!(为了方便举例,假设武汉的网络时间比深圳的网络时间快了5s)

▌用?能解决的方案


原子钟这个概念并不新颖,早在很早以前的航天航空领域,它就已经存在了。火箭卫星之所以能够出色的完成入轨和定点目标,一个重要因素就是它们拥有极致精确的时间。那是一种精度可以达到万分之一秒,几万年都不会出差错的可怕存在。

Spanner是Google的全球级的分布式数据库 (Globally-Distributed Database) 。它的扩展性达到了令人咋舌的全球级,可以扩展到数百万的机器,数已百计的数据中心,上万亿的行。除了夸张的扩展性之外,他还能同时通过同步复制和多版本来满足外部一致性,具备HA高可用性。同时冲破CAP的枷锁,在三者之间达到了完美平衡。就在几个月前,Spanner终于release并支持商用了。

互联网精贵(精英+贵族)如Google,在解决该问题上自然底气实足。他们肯花高额的费用在原子钟上,并不是因为不关心算法,而是明白当前算法本身也存在一定的局限性,也许不能完美的解决问题。一如DeepLearning在手机终端的应用。为了解决存储难题,算法尝试对filter参数量化压缩学习。实际上,硬件上的性能提升较之算法上性能提升,效果更加明显。当然,二者本质上是相辅相成的。

但是,即便诚如原子钟,也会有偏差,只不过这个偏差是可预期的(10ms)。那么,我们不禁会发问,“有些短事务,比如只含有一条SQL指令,它需要的执行时间可能小于10ms,即10ms内还是可能造成快慢钟现象发生,那该怎么办?”

别急,Google的研发人员提供了一个非常简单的解决方案。Spanner规定,一个新事务获取的时间点为X,它真正启动的时间为:X + 10ms。通俗的话说,在本地的新事务启动时,它先获取一下当前本地的时间戳X,再等待10ms,确保其他节点的时间不早于X后,才开始执行。因为原子钟保证了任意两个节点间的网络时钟偏差不超过10ms,所以事务的先后顺序得以保证。

▌靠数学推理解决的方案


下面给大家介绍下HLC混合逻辑时钟

  • HLC先验概念

作者认为:数据库的事务的执行标准应该是按照时序进行的,而不是单纯的时间。数据库中存在关联的(因果关系的)事务才需要严格区分先后次序。数据库中不存在关联的事务间的执行顺序可以随意。在HLC的观念里,彻底摒弃了时钟的概念,而是以时序代替。

同样是上述的快慢钟问题,HLC对存在关联的事务进行了时序修正。深圳Read事务发生在武汉Write事务之后。按照HLC的观念,原本的慢钟(深圳)的时序点被修正为关联节点(快钟(武汉))的Write事务时序点+1。所以,当李四收到张三汇款成功的消息后,在本地查账即刻能获得最新结果。

同理,上海与深圳的事务间也存在关联关系,所以上海的时序也需要调整,但是由于上海的时钟本来就快于深圳的时钟,所以调整的结果为E上海=max(E深圳+1,Ep上海+1,T上海)= T上海。(其中,E表示事务发生的时序点,Ep表示该节点此刻记录的最近一次事务发生的时序点(每个节点都会记录最近一次事务发生的时序点),T表示本地的网络时钟)。

除此之外,该方案还存在一个严重的问题,如上图所述,当两个节点间的关联事务频繁发生时,时序变量将可能溢出。具体而言,假定任意一个单位时间内,允许发生的事务最大个数为K。则根据上述理论,在单位时间内首尾两个事务的时序差<= K。当关联事务频繁发生时,不同单元时间内的时序差将会累加,导致时序变量急剧上涨,溢出风险亟待解决。

HLC引入了逻辑时钟的概念,将时序设计成网络时钟.逻辑时钟的组合。前者看成是整数位,后者看成是小数位。即E=En+El,其中,En表示整数部分,El表示小数部分。这种方式能有效地解决时序溢出的问题。具体实现方法是:

If (max(En深圳+1,Epn上海+1,T上海)==T上海)
then E上海=T上海.0 //即此刻逻辑时钟归零
else //取En深圳,Epn上海间的较大者,并启用小数位El。
   then If (max(En深圳,Epn上海)==En深圳) 
      then E上海= En深圳+ (El深圳+1个单位El)
           else then E上海= Epn上海+ (Epl上海+1个单位El)
           end
end

简而言之,就是将单位时间内的关联事务先后次序,通过逻辑时钟来排序;不同单位时间内的关联事务,通过网络时钟约束,避免溢出风险。(具体的数学证明可以详看参考论文~~,笔者从头到尾膜拜地推导了一遍,不过实在懒得敲公式了)

聪明如你,这里也许已经看出点端倪:HLC是基于网络通信质量的算法

  • 应用实践

以CocroachDB为例,在分布式数据库中,结构大致如图所示,Server是服务器、CN和DN都属于解析节点、Storage属于底层存储。其中,CN和DN分别表示协调者节点和数据节点,它们往往分布在不同的地方,拥有各自的本地网络时钟。对于一个事务而言,数据库根据一定规则随机选择一个解析节点为CN。(与该事务实际相关的节点为它的DN节点)CN节点在协调过程中时,当收到DN节点传来的事务执行成功消息后,会通知其他相关的DN节点,调整它们的HLC时序。这样,新事务到来时,获取的时间戳就是最新的时序了。

下次如有机会,跟大家分享下:Oceanbase郁白老师的“两阶段提交的工程实践”。

▌参考文献


1.“LogicalPhysical Clocks and Consistent Snapshots in Globally Distributed Databases”

OPODIS 2014: Principlesof Distributed Systems pp 17-32

2. Google Spanner:

http://research.google.com/archive/spanner.html

作者简介:

宋强,本科毕业于中山大学,硕士毕业于中科院自动化所,曾在华为从事分布式数据库研发工作,现在一家金融机构工作。

特注:

本篇由宋强投稿专知发送,欢迎各位行业技术专家投稿专知,分享您的技术与观点!

Email:zhuanzhi2017@outlook.com;

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-12-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Crossin的编程教室

一名python学习者打开双11的正确姿势

11月11日是个有趣的日子。客观来说,它和一年中其他364(365)天一样没什么特殊,但偏偏又总被人赋予特殊的含义。十年之前,大家谈论的是如何打发“光棍节”(跟...

3417
来自专栏帘卷西风的专栏

从零开始编写网络游戏--卷首语

        自从大四下学期开始,经过短暂的软件开发经历之后,我毅然决定进入我梦寐以求的游戏开发行业,转眼间已经过去5年半了,在这个过程中,有过迷茫,有过放弃...

991
来自专栏Material Design组件

今后设计可注意的点

给用户一份精美小礼品这样的友好举动再好不过了。具体来讲,送出礼品也是之有效的获得客户忠诚度的战术,这是建立在人们互惠准则上的。而这样做所带来的好处也是显而易见的...

954
来自专栏ATYUN订阅号

谷歌重磅推出Android Pie,以AI为驱动

谷歌今天透露,Android P代表Android Pie,接替Android Oreo,并将最新的源代码推送到Android开源项目(AOSP)。谷歌移动操作...

782
来自专栏FreeBuf

安全摘记 | 互联网安全小兵的日常

*本文原创作者:starshine,本文属FreeBuf原创奖励计划,未经许可禁止转载 生活不只有眼前的苟且,还有诗和甲方。于是,我来到了甲方,成为了一个互联网...

1929
来自专栏区块链

每天有数百人搜索App破解,开发者该怎么保护自己的手机应用呢?

百度上搜索“App破解”,会出现1210万条结果。从App破解的入门知识到逆向工具下载,从破解技术视频到全图文教程。 随着黑客技术的普及化平民化,App——智能...

3225
来自专栏ytkah

微信公众平台原创声明功能公测 自媒体原创保护的福音

  昨日晚间微信团队发布微信公众平台面向认证的媒体类型公众号公测原创声明功能的公告,势在维护作者权益,鼓励优质内容产生。心灵鸡汤、养生贴想必你已经厌倦了,甚至都...

3046
来自专栏人人都是极客

嵌入式和单片机的区别在哪?

单片机和嵌入式,其实没有什么标准的定义来区分他们,对于进行过单片机和嵌入式开发的开发者来说,都有他们自己的定义,接下来,就谈谈这两个概念的理解。

1943
来自专栏极乐技术社区

一周小程序【资讯教程Demo】更新

轻松一刻 21天c++自学成材法 ? 资讯与教程 用 RxJS、RxWX 编写更优秀的微信小程序代码 微信小程序播放音频 小程序view中的节点数最多是多大? ...

3077
来自专栏腾讯大讲堂的专栏

17年,中国互联网技术走出国门【腾讯篇】

要说哪些公司代表了中国互联网技术的前沿,估计大多数人都会脱口而出:BAT(百度、阿里、腾讯)。中国互联网发展20多年,经历了QQ、游戏、微信红包、双11等等亿万...

1966

扫码关注云+社区