海量存储原理系列用户接口是指结构化查询语言（SQL）。关系代数是数据库关系模型和关系演算的理论基础

文件名称: 海量存储原理系列

所属分类: MySQL

开发工具:

文件大小: 455kb

下载次数: 0

上传时间: 2019-07-02

提供者: aba****

下载 (455kb)

不能下载？报告错误

详细说明：用户接口是指结构化查询语言（SQL）。关系代数是数据库关系模型和关系演算的理论基础。事务引擎是保证事务ACID性质的组件，在很大程度上影响数据库的效率。存和索引是数库本模块，数织和操作方式。一致性和隔离性,可以归结为一个问题,即数据什么时候可被共享,什么时候必须被独占。这些决策,最终决定整个数据库系统的并行度,直接决定多线程并发的性能指标更改数据的同时要保证一致性和隔离性,就要使得针对不同数据的更改,不同人或杋器不发送冲突。如果出现对相同薮据的更改,则要将更新进行排队。一般排队策略有:排他锁;读写锁;写时拷贝;队列;内存事务从性能考虑,排他锁最慢。读写锁的读可以并发,效率稍高,但写和读不能同时进行。写时拷贝的读取和写入之间可以互相不影响,所以效率更高。队列在内存里效果较好,因为可以省去中断上下文切换的时间。内存事务极大提高并行度, 但有原子操作木身功能局限性和组合性不佳的问题。排他锁,队列和内存事务,在目前的数据库中用的相对较少。读写锁,是隔离性中“读已提交,可重复读”两种实现中最重要的底层实现方式,读和写操作都要加锁,相互阻塞,并行度较低写时拷贝是对读写锁的改进,写不阻塞读,读不阻塞写。四、分布式事务随着数据量的不断增长,单机性能遇到瓶颈,所以考虑用多台机器解决问题。分布式场景中,会遇到新的问题: 1)延迟:带来延迟的因素包括:距离、拥塞、內络协议。 2)灾备:冗余和备份策略的选择,影响性能 3)扩展:集群可以通过增加新机器的方式提升整体性能。 4)性能:快速响应、低延迟、高并发, 5)一致:一致性保证。分布式锁的实现‖常复杂而且低效,一致性和高性能有矛盾 CAP埋论: 1)一致性:数据所有备份保持一致。 2)可用性:集群部分节点故障后,所有读和写操作必须要能终止。 3)分区容忍性:集群中消息丢失导致分区是可容忍的。任何分布式系统,不存在一个算法同时满足上述三条性质,最多能同时保证两点同吋做到一致性和可用性的是单机系统。任何分布式系统都必须实现分区容忍性,在一孜性和可用性间权衡五、索引与书籍的目录一样,索引的作用在于加快查找速度,但需要额外的空间你储自只有一些特定的数据结构可以用来做索引,常见的索引如下图所示: 无序集合散列表索引数组有序集合—链表—跳表二叉树 B树系树 LSM树系 COLA树系散列表,即 Hash table,基木原理是用散列码做为索引值,有若干个桶,按桶的数量对索引值取余,进行存储数红就是最基本的数据结构,只能按顺序遍历跳表,是一种轻量级的平衡树的替代结构,通过一种随机化的方法保持树的平衡。跳表形式上由多个链表组成,查询方式与树类似。跳表基本结构如下图所第五层NIL 5 NII 第四层NL 5 ANIL 第三层NIL 4 5 8 NIl 第二层NIL 2 4 5 6 NIL 第一层NIL 3 5 8 NIl 链表头链表尾跳表具有以下性质 1)跳表是按层组织的,每一层都是一个普通的有序链表,最底层的链表存储了跳表中的所有元素 2)如果一个元紊出现在第i+1层,则该元素一定在第i层中;如果一个元素在第i 层中,那么该元素则按某一固定的概率p出现在第i+1层。 3)除最下层元素外,表的每个元素都包含两个指针:一个指向同一层的下一个元素,另一个指向下一层的同一个元素。理论上,跳表可能会有一个很不平衡的结构,但在实际工作中这种概率非常小,其效率与平衡二叉树不相上下二叉树是一种提供二分查找的树形结构 B-Tree是平衡二叉树一种推广,其特点是每个节点保存多份数据,同时有多个孩子;每个节点内的数据保存为数组形式,并按键值排序。这种结构的优点是能够极大地降低树的高度,而且可以利用磁盘读取数据的局部性原理,在很大程度上减少磁盘读写次数,并充分利用磁盘带宽。根节点M OTX IL NP B-Tree的变形包括B+-Tree和B*Tree。B+-Tree主要的特点是所有的键值数据都保存在叶节点中,内部节点只提供指针。B+-Tree把所有叶节点组织成排列链表,提高范围査询的效率。B*-Tree是对B+-Tree的扩展,其特点是在非根节点与非叶节点中增加指向兄弟节点的指针,并让 B+-Tree更丰满,提高空间利用率。当B-Tree运行很久以后,不断地插入和删除操作将使其在磁盘上的存储变得很分散,无法利用磁盘的预读取机制,每次操作都要求磁头在磁片上随机查找扇区,大大降低索引效率。 LSM-Tree是一个经典的索引结构,思想是基于日志文件系统提出的,日志文件系统的优点是通过将大量小文件的读写转化为批量的连续读写, 仗对于文件系统的读写都是顺序的,从而提高效率。 LSM-Tree是一种跨内存和磁盘的多组件算法,该算法将对索引的操作缓存到内存组件中,当内存组件缓存的数据达到阈值后,再批量更新到磁盘组件完成持久化。这种结构,改变了原来直接在磁盘上维护索引的方式,保证对磁盘的写操作都是顺序的,大大提高了索引的插入效率。 C组件 C组件 C.组件 C组什 Merge 内存磁盘上图所示为多组件LSM-Tree的基本结构。C0Tree是驻留在内存中的结构,所有对LSM-Tree的操作都会首先记录到 Co Tree中。因为C0Tree在内存中,所以单独地看每一个操作都不会产生磁盘读写开销。但是内存空问有限,限制了C0Tree 的大小,这就要求能够通过一种高效的方式将C0Tree中的数据迁移到成本较低的磁盘上为此LSM-Tree引入了 Rolling merge过程,用于当内存中的 CO Reel的数据量达到指定的阈值时,将它们归并入外存组件 CI Tree中。 Cl Tree是一个类似B-Tree的结构,所有节点都保证全满以节省磁盘空间,并且节点内部的数据都有序存储, 但节点间的数据没有明显的顺序特征。当数据量不断增加,C1Tree会变得‖常庞大,C0Tree与jC1Tree之间的 Rolling Merge过程开销就会增加。因此可以在 CI Tree之后再增加一些新的磁盘组件 C2…,Ck-1和Ck。这些组件按存储的数据量阈值进行排序,同时在每个相邻组件对(Ci-1,Ci)之间加入异步的Ro1 ling merge过程,该过程负责在较小组件中数据量超过其阈值大小时,将所有数据归并入到较大组件中。随着组件数量的增多, Rolling merge过程的开销逐渐加大,磁盘开销也随之增长,LSM-Trec的插入和査询性能都会下降,因此一般LSM-Tree都选择三组件结构在LSM-Tree中,单独的插入操作不会立即产生开销,所有的开销都来白 Rolling Merg过程,每个插入操作逻辑上的开销是 Rolling merge过程的平摊开销,由于 Rolling merge是顺序写磁盘的,其效率必然要高于所有单独随机写磁盘的效率 COLA是基于缓存无关算法提出的一种结构,其基木思想是对于内存-磁盘这种两级存储结构,有两个参数会影响整体的读写性能:一个是速度快但存储空间较小的一级存储(内存)的大小,另一个是每次在一级存储和二级存储(磁盘)之间传输数据的块大小,块大小对程序员和一般的算法是透明的。如下图所示,一个COLA的结构特点是: 58 17111622273544 1)由多层数组组成,最高层数组大小为1,以后每一层数组大小都是其上一层数组大小的两倍。 2)每一层数组中的元素按照从小到大顺序排列 3)每一层或者全空或者全满,不允许出现只保存一部分数据的数组。因为所有数组的大小都是从1到2n的2的整次幂,所以一个COLA可以存储任意整数多个元素。 COLA的查找过程比较简单,就是逐个地在每一个非空层内进行二分查找 COLA的插入过程相对比较复杂,与LSM-Tre类似,需要进行多次归并操作。当有数据要插入时,首先需要开辟一个临时空间,称为影子数组 ( Shadow Array),影子数组的结构与COA完全一致,但每次插入开始时影子数组是空的。然后,需要检查OOLA的第1层是否为空:如果为空,则直接将该数据插入COLA,插入过程结束;如果非空,则先将该数据插入影子数组的第1层,再将COLA的第1层的数据与影子数组第1层的数据进行归并排序。此时再看COLA的第2层是否为空:如果为空,则归并排序的结果可以直接插入COLA的第2层,插入过程结束;如果非空, 则将归并排序的结果再插入插入影子数组的第2层,再将COLA的第2层的数据与影子数组第2层的数据进行归并排序。如此不断进行下去,直到某次归并排序后的结果已存入COLA,则表明插入过程结束 1|711162227|3544 71116222735 口山7叫|2121x□ 在原始COLA中依次插入12和10 7s2p2x4「口 5|810I 7mt622|273544 当临时空间为空时,归井过程结東 COLA的插入过程看似复杂,但整个过程仝部都不会产生随机读写磁盘的操作,并且无需维护像B-Tree里的复杂指针,因此效率比较高。六、分布式存储规则引擎分布式存储系统的结构图如下所示 DB1 DB2 客户端规则引擎 Dhi= Pkon DBn 抽象的看,分布式和单点的区别在于,客户端的数据如何通过规则引擎划分,而且能保证一致性。规则引擎的作用在于,对有状态的数据,需要一套机制以保证其针对同一个数据的多次请求,应该物理上被发送到同一个逻辑区块内的同一个数据上。其实,规则引擎也是一种索引,但与之前介绍的几种不太一样。规则引擎需要能够査得快,并且尽可能的将数据平均的分配到所有的节点中,同时当新的节点加入,希望只移动那些需要移动的数据,不需要移动的数据则不移动。分布式系统应该有无限的水平扩展能力,这种水平扩展,主要用于解决两类问题,一是磁盘空间不足的问题,二是性能不足的问题。水平扩展就需要数据迁栘,一般来说数据迁移的思路是尽可能地让数据不动,只通过规则变动的方式来完成扩容,如果这种方式无法满足要求,那么再通过移动数据的方式,来满足其他的一些需求。普通的散列可以满足查得快和尽可能平均分配,但新加入一个节点,通常会有非常大比例的数据需要移动,不满足数据迁移友好的原则。为此,引入一致性散列算法致性散列算法的基本原埋如下图所小: Cache A2 hash Key A2 Key C1 Cache c1 3 C2 Key A1 Cache ce Cache Al obiect

(系统自动生成,下载前可以参看下载内容)