分布式数据库查询算法(分布式数据库查询算法有哪些)

高端定制开发 33
本篇文章给大家谈谈分布式数据库查询算法,以及分布式数据库查询算法有哪些对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。 常见分布式算法有哪些 分布式中有这么一个疑难问题,客户端向一个分布式集群的服务端发出一系列更新数据的消息,由于分布式集群中的各个服务端节点是互为同步数据的,所以运行完客户端这系列消息指令后各服务端节点的数据应该是一致的,但由于网络或其他原因,各个服务端节点接收到消息的序列可能不一致,最后导致各节点的数据不一致。举一个实例来说明这个问题,下面是客户端与服务端的结构图:

本篇文章给大家谈谈分布式数据库查询算法,以及分布式数据库查询算法有哪些对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。

常见分布式算法有哪些

分布式中有这么一个疑难问题,客户端向一个分布式集群的服务端发出一系列更新数据的消息,由于分布式集群中的各个服务端节点是互为同步数据的,所以运行完客户端这系列消息指令后各服务端节点的数据应该是一致的,但由于网络或其他原因,各个服务端节点接收到消息的序列可能不一致,最后导致各节点的数据不一致。举一个实例来说明这个问题,下面是客户端与服务端的结构图:

mysql如何做成分布式?

MySQL做分布式需要通过ndb的Cluster来实现。MySQLCluster是MySQL适合于分布式计算环境的高实用、高冗余版本。 实现的步骤比较复杂,百度云案例:《MySQLCluster(MySQL集群)分布式》 下载地址:

MySQL索引的Index method中btree和hash的区别

Hash 索引的查询效率要远高于 B-Tree 索引。

可 能很多人又有疑问了,既然 Hash 索引的效率要比 B-Tree 高很多,为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢?任何事物都是有两面性的,Hash 索引也一样,虽然 Hash 索引效率高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端,主要有以下这些。

(1)Hash 索引仅仅能满足"=","IN"和"="查询,不能使用范围查询。

由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值,所以它只能用于等值的过滤,不能用于基于范围的过滤,因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系,并不能保证和Hash运算前完全一样。

(2)Hash 索引无法被用来避免数据的排序操作。

由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值,而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样,所以数据库无法利用索引的数据来避免任何排序运算;

(3)Hash 索引不能利用部分索引键查询。

对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。

(4)Hash 索引在任何时候都不能避免表扫描。

前面已经知道,Hash 索引是将索引键通过 Hash 运算之后,将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中,由于不同索引键存在相同 Hash 值,所以即使取满足某个 Hash 键值的数据的记录条数,也无法从 Hash 索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。

(5)Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

对于选择性比较低的索引键,如果创建 Hash 索引,那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下。

分布式存储中,怎样使用paxos算法保证数据的一致性

在分布式系统中,我们经常遇到多数据副本保持一致的问题,在我们所能找到的资料中该问题讲的很笼统,模模糊糊的,把多个问题或分类糅合在一起,难以理解。在思考和翻阅资料后,通俗地把一致性的问题可分解为2个问题:

1、任何一次修改保证数据一致性。

2、多次数据修改的一致性。

在弱一致性的算法,不要求每次修改的内容在修改后多副本的内容是一致的,对问题1的解决比较宽松,更多解决问题2,该类算法追求每次修改的高度并发性,减少多副本之间修改的关联性,以获得更好的并发性能。例如最终一致性,无所谓每次用户修改后的多副本的一致性及格过,只要求在单调的时间方向上,数据最终保持一致,如此获得了修改极大的并发性能。

在强一致性的算法中,强调单次修改后结果的一致,需要保证了对问题1和问题2要求的实现,牺牲了并发性能。本文是讨论对解决问题1实现算法,这些算法往往在强一致性要求的应用中使用。

解决问题1的方法,通常有两阶段提交算法、采用分布式锁服务和采用乐观锁原理实现的同步方式,下面分别介绍这几种算法的实现原理。

两阶段提交算法

在两阶段提交协议中,系统一般包含两类机器(或节点):一类为协调者(coordinator),通常一个系统中只有一个;另一类为事务参与者(participants,cohorts或workers),一般包含多个,在数据存储系统中可以理解为数据副本的个数。两阶段提交协议由两个阶段组成,在正常的执行下,这两个阶段的执行过程如下所述:

阶段1:请求阶段(commit-request phase,或称表决阶段,voting phase)。

在请求阶段,协调者将通知事务参与者准备提交或取消事务,然后进入表决过程。在表决过程中,参与者将告知协调者自己的决策:同意(事务参与者本地作业执行成功)或取消(本地作业执行故障)。

阶段2:提交阶段(commit phase)。

在该阶段,协调者将基于第一个阶段的投票结果进行决策:提交或取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务,否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。

举个例子:A组织B、C和D三个人去爬长城:如果所有人都同意去爬长城,那么活动将举行;如果有一人不同意去爬长城,那么活动将取消。用2PC算法解决该问题的过程如下:

首先A将成为该活动的协调者,B、C和D将成为该活动的参与者。

阶段1:A发邮件给B、C和D,提出下周三去爬山,问是否同意。那么此时A需要等待B、C和D的邮件。B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排,则发邮件告诉A它们同意下周三去爬长城。由于某种原因,D白天没有查看邮件。那么此时A、B和C均需要等待。到晚上的时候,D发现了A的邮件,然后查看日程安排,发现周三当天已经有别的安排,那么D回复A说活动取消吧。

阶段2:此时A收到了所有活动参与者的邮件,并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D,下周三爬长城活动取消。此时B、C回复A“太可惜了”,D回复A“不好意思”。至此该事务终止。

两阶段提交算法在分布式系统结合,可实现单用户对文件(对象)多个副本的修改,多副本数据的同步。其结合的原理如下:

1、客户端(协调者)向所有的数据副本的存储主机(参与者)发送:修改具体的文件名、偏移量、数据和长度信息,请求修改数据,该消息是1阶段的请求消息。

2、存储主机接收到请求后,备份修改前的数据以备回滚,修改文件数据后,向客户端回应修改成功的消息。 如果存储主机由于某些原因(磁盘损坏、空间不足等)不能修改数据,回应修改失败的消息。

3、客户端接收发送出去的每一个消息回应,如果存储主机全部回应都修改成功,向每存储主机发送确认修改的提交消息;如果存在存储主机回应修改失败,或者超时未回应,客户端向所有存储主机发送取消修改的提交消息。该消息是2阶段的提交消息。

4、存储主机接收到客户端的提交消息,如果是确认修改,则直接回应该提交OK消息;如果是取消修改,则将修改数据还原为修改前,然后回应取消修改OK的消息。

5、 客户端接收全部存储主机的回应,整个操作成功。

在该过程中可能存在通信失败,例如网络中断、主机宕机等诸多的原因,对于未在算法中定义的其它异常,都认为是提交失败,都需要回滚,这是该算法基于确定的通信回复实现的,在参与者的确定回复(无论是回复失败还是回复成功)之上执行逻辑处理,符合确定性的条件当然能够获得确定性的结果哲学原理。

分布式锁服务

分布式锁是对数据被外界修改持保守态度,在整个数据处理过程中将数据处于锁定状态,在用户修改数据的同时,其它用户不允许修改。

采用分布式锁服务实现数据一致性,是在操作目标之前先获取操作许可,然后再执行操作,如果其他用户同时尝试操作该目标将被阻止,直到前一个用户释放许可后,其他用户才能够操作目标。分析这个过程,如果只有一个用户操作目标,没有多个用户并发冲突,也申请了操作许可,造成了由于申请操作许可所带来的资源使用消耗,浪费网络通信和增加了延时。

采用分布式锁实现多副本内容修改的一致性问题, 选择控制内容颗粒度实现申请锁服务。例如我们要保证一个文件的多个副本修改一致, 可以对整个文件修改设置一把锁,修改时申请锁,修改这个文件的多个副本,确保多个副本修改的一致,修改完成后释放锁;也可以对文件分段,或者是文件中的单个字节设置锁, 实现更细颗粒度的锁操作,减少冲突。

常用的锁实现算法有Lamport bakery algorithm (俗称面包店算法), 还有Paxos算法。下面对其原理做简单概述。

Lamport面包店算法

是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport(英语:Leslie Lamport)发明。

Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购,安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买,就必须重新排队。

这个类比中的顾客就相当于线程,而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点,存在两个线程获得相同的签到号码的情况,这是因为两个线程几乎同时申请排队的签到号码,读取已经发出去的签到号码情况,这两个线程读到的数据是完全一样的,然后各自在读到的数据上找到最大值,再加1作为自己的排队签到号码。为此,该算法规定如果两个线程的排队签到号码相等,则线程id号较小的具有优先权。

把该算法原理与分布式系统相结合,即可实现分步锁。

Paxos算法

该算法比较热门,参见WIKI,

Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中,是分布式计算中的重要问题。节点通信存在两种模型:共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby,而Chubby使用Paxos算法来保证备份的一致性。

采用乐观锁原理实现的同步

我们举个例子说明该算法的实现原理。如一个金融系统,当某个操作员读取用户的数据,并在读出的用户数据的基础上进行修改时(如更改用户帐户余额),如果采用前面的分布式锁服务机制,也就意味着整个操作过程中(从操作员读出数据、开始修改直至提交修改结果的全过程,甚至还包括操作员中途去煮咖啡的时间),数据库记录始终处于加锁状态,可以想见,如果面对几百上千个并发,这样的情况将导致怎样的后果。

乐观锁机制在一定程度上解决了这个问题。乐观锁,大多是基于数据版本( Version)记录机制实现。何谓数据版本?即为数据增加一个版本标识,在基于数据库表的版本解决方案中,一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时,将此版本号一同读出,之后更新时,对此版本号加一。此时,将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对,如果提交的数据版本号大于数据库表当前版本号,则予以更新,否则认为是过期数据。

对于上面修改用户帐户信息的例子而言,假设数据库中帐户信息表中有一个 version 字段,当前值为 1 ;而当前帐户余额字段( balance )为 $100 。

操作员 A 此时将其读出(version=1 ),并从其帐户余额中扣除 $50($100-$50 )。

在操作员 A 操作的过程中,操作员B也读入此用户信息( version=1 ),并从其帐户余额中扣除 $20 ( $100-$20 )。

操作员 A 完成了修改工作,将数据版本号加一( version=2 ),连同帐户扣除后余额( balance=$50 ),提交至数据库更新,此时由于提交数据版本大于数据库记录当前版本,数据被更新,数据库记录 version 更新为 2 。

操作员 B 完成了操作,也将版本号加一( version=2 )试图向数据库提交数据( balance=$80 ),但此时比对数据库记录版本时发现,操作员 B 提交的数据版本号为 2 ,数据库记录当前版本也为 2 ,不满足 “ 提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略,因此,操作员 B 的提交被驳回。这样,就避免了操作员 B 用基于 version=1 的旧数据修改的结果覆盖操作员A 的操作结果的可能。

乐观锁机制与分布式系统相结合上, 我整理了伪代码如下:

obj 操作的目标

vlaue 修改的值

atom_update_ver 每个目标上的版本,每次修改该值递增

set( obj, value)

{

//从每个节点上取出修改前的对象版本

get original_ver = obj.atom_update_ver from each node;

//将值赋到每个节点的obj目标

set obj = value from each node;

//条件修改每个节点的obj版本,目标版本加一

//比较和修改操作是原子操作

result = (set obj.atom_update_ver = original_ver + 1

where original_ver + 1 obj.atom_update_ver

for each node);

if(result == ok)

return set_ok;

else

return set(obj, value);//不成功递归修改

该算法未考虑节点下线、失效等问题,在后续我将分析采用乐观锁原理实现一致性算法,解决问题2、节点失效、通信失败等问题。

分布式数据库查询算法的介绍就聊到这里吧,感谢你花时间阅读本站内容,更多关于分布式数据库查询算法有哪些、分布式数据库查询算法的信息别忘了在本站进行查找喔。

分布式数据库查询算法 分布式数据库查询处理和优化算法分布式数据库分页查询分布式数据库查询优化分布式数据库连表查询分布式数据库联表查询在分布式数据库系统中以每个查询的在分布式数据库系统中逻辑数据库用户不必关心数据分布的细节
扫码二维码