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

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

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

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

▌分布式数据库


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

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

▌概念科普


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

对此,研究人员提出了一种解决方案: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 条评论
登录 后参与评论

相关文章

来自专栏TEG云端专业号的专栏

「TEG+系列」破局者 - 腾讯金融级数据库TDSQL

一 背景 金融行业的数据库市场,尤其是银行的核心交易系统,一直是Oracle、DB2这类传统商业数据库的天下,但是: 2014年,微众银行选用TDSQL作为其核...

4155
来自专栏华章科技

程序员遇到bug时常见的30种反应,你躺枪了么?

开发应用程序是一项压力很大的工作,人无完人,工作中遇到 bug 是很正常的事,有些程序员会生气,沮丧,郁闷,甚至泄气,也有一些程序员则会比较淡定。如何进行修复 ...

951
来自专栏ATYUN订阅号

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

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

812
来自专栏Crossin的编程教室

想用 Python 做数据分析?先玩玩这个再说

数据分析是 Python 的一大应用领域。据我所知,本教室的读者中有不少学习 Python 就是为了在工作中能用它分析数据。这其中,又有相当一部分人是涉及金融相...

4937
来自专栏Crossin的编程教室

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

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

3557
来自专栏工科狗和生物喵

【闲来无事,py写game】Mac-Python3.5安装pygame 1.9.2 小计

正文之前 没错,我就是这么不学无术,C++实在学的鸡儿疼,所以干脆搞点娱乐措施,昨天赶上了京东图书做大活动,所以屯了一批书,好久没碰python了。所以就整本玩...

6126
来自专栏惶心 - 技术博客

用一年的时间,去遇见

白色而透明的屏幕里,像素点时刻变换着颜色。你看不见的黑暗里,只有风扇快速转动,发出微弱的响声。

1709
来自专栏51CTO技术栈的专栏

风靡全国,日活8000万,《王者荣耀》后台技术架构演进!

这个曾经在端游时代主导搭建 RTS 游戏《霸三国》框架的技术团队,在转型做 MOBA 手游《王者荣耀》后为游戏提供了巨大的支持,但这个过程也并非一帆风顺。

1.9K0
来自专栏区块链

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

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

3655
来自专栏FreeBuf

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

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

2059

扫码关注云+社区

领取腾讯云代金券