柳州游戏网站建设,建筑行业平台,特别酷炫网站,宁波网络推广教程欢迎访问 OceanBase 官网获取更多信息#xff1a;https://www.oceanbase.com/
本文来自OceanBase社区分享#xff0c;仅限交流探讨。原作者马伟#xff0c;长期从事互联网广告检索系统的研发#xff0c;对数据库#xff0c;编译器等领域也有浓厚兴趣。 文章目录综述传统单…欢迎访问 OceanBase 官网获取更多信息https://www.oceanbase.com/
本文来自OceanBase社区分享仅限交流探讨。原作者马伟长期从事互联网广告检索系统的研发对数据库编译器等领域也有浓厚兴趣。 文章目录综述传统单机数据库存储与索引技术存储模型介绍数据文件组织方式堆文件索引组织表索引B树基本性质B树基本操作查找插入删除B树并发策略读操作(查找)写操作(插入或删除)数据库扩展技术ShardingShare-StorageShare-Nothing参考文献综述 随着1970年代关系模型被提出数据库进入了一个飞速发展的时期。整个80年代和90年代各类关系数据库层出不穷这些产品到现在依然占据着数据库市场的主流。然而到了2000年以后互联网产业的崛起使得传统的关系数据库在面对海量请求和数据的时候有些力不从心。在这一时期解决可扩展问题的主流方案是拆分数据库(分库分表)诞生了众多的数据库中间层(中间件)同时业界也诞生了众多的K-V数据库如BigTableMongoDBCassandra等解决了半结构化数据的计算和存储的可扩展问题然而业界对于可扩展的关系数据库的诉求一直存在。
2012年Google的论文《Spanner: Google’s Globally-Distributed Database》为业界提供了一个分布式数据库的非常好的参考此后各类参考Spanner架构的分布式数据库系统层出不穷。其中国内厂商在自身用户数以及去IOE动力的驱使下诞生了包括OceanBase和TiDB在内的几款非常优秀的分布式数据库在技术上的差距和国外巨头已经拉平但是市场开拓上还需要继续努力。
同时众多的云计算厂商基于自身的云基础设施为其客户提供的数据库解决方案也为数据库的扩展性提供了新的思路。代表性的产品是亚马逊的Aurora其上层100%兼容开源数据库(MySQL, PostgreSQL)下层依托自身云厂商存储技术设施计算与存储分离的架构成为了众多云厂商参考的对象。
数据库是一个庞大而复杂的系统其各个子系统如SQL事务存储日志等每一个都是既有一定的理论理解门槛又有非常高的实现难度分布式数据库还会涉及更多晦涩的理论如CAP理论2/3阶段提交协议Paxos协议Raft协议等。本系列通过三篇文章尝试从存储和索引的角度和大家共同学习和了解数据库在存储领域的一些技术希望这样浮光掠影的文章能给大家留下些许印象拓宽一些思路在以后的工作中能有所帮助注本系列参考的资料均系本人搜集自互联网公开的论文和博客文章以及开源的代码和文档等并经本人理解和整理。文章中的一些技术观点仅代表个人观点如有描述偏差烦请指正。
传统单机数据库存储与索引技术
存储模型介绍
为了保证在系统发生故障时的数据持久化数据库使用非易失的磁盘作为主存储介质。传统数据库的在磁盘上的数据组织方式为页面行存即数据库将磁盘空间划分为多个页面每个页面的大小一般是4K的整数倍数据在页面内以行为单位存储在一起。数据库读写IO的基本单位都是页面。
由于系统不能直接操作磁盘上的数据因此还需使用内存作为缓存。通常数据库在内存中会维护一个Buffer Pool的数据结构用于缓存从磁盘中读取的页面。数据库上层子系统对于数据的读写都经过Buffer Pool进行。数据库在进行事务操作时先将redo log顺序写入日志文件然后再将修改应用到Buffer Pool中的目标页面。通常这一过程只有一次日志文件的顺序IO操作没有磁盘的随机IO。Buffer Pool会在系统空闲或者内存到达一定阈值的时候异步将某些页面回刷到磁盘并回收内存。Buffer Pool页面回刷会产生随机IO页面的替换策略也会影响系统整体的缓存命中率因此页面回刷策略也是很多研究的热点。
数据库的数据存储在页面上通常以行为单位存储。页面一般会有一个固定大小的页头(Page Header)用于存储页面的一些meta信息如页面类型记录条数同一张表下一个页面的地址等。如果页面存储的行记录是定长的那么从Page Header开始依次存储记录就行了。如果是变长记录即每一行数据的大小都可能不一样一般的做法是从Page Header后开始存储数据再从页面的末尾开始反向分配也目录(Row Offset)空间Row Offset记录行在页面内的偏移。这样可以在不确定一个页面可以存储多少行数据的情况下尽量提高页面空间的利用率。 数据文件组织方式
前面我们讲到数据表的存储方式是以页面为单位进行存储的但是页面与页面之间如何组织也由不同的方式。常见的方式有两种。一种叫做堆文件(Heap File)另外一种叫做索引组织表(IOTIndex Organized Table)。
堆文件
堆文件是数据库中最简单最基本的文件结构新数据插入优先使用文件末尾的空闲页面每行数据都会被分配一个rowid作为行的唯一标识。rowid通常包含其所在的文件ID页面ID以及页面内的行序号ID。
堆文件有以下一些使用场景
数据量很小的表 如数据只有几个页面此时通过索引访问和直接进行全表扫描相比没太大差别。数据表有一次性的大量数据插入的场景 如数据迁移。此时使用对文件进行数据插入效率会比通过索引组织表的方式插入会高非常多。在堆文件上建立索引后也可以用于数据量大的场景。 堆文件的各种操作如下如下。
插入 插入优先使用文件末尾的空闲页面空间只有当空闲空间不足时才考虑复用被删除的记录的空间。删除 删除数据需要将页面上的物理记录标记为删除并删除索引中对rowid的引用。查询 根据索引(BTree)进行点查询或者范围查询查询索引得到rowid之后再通过rowid得到对应的数据。如果没有建立索引的话无论点查询或者范围查询都需要全表扫描。
索引组织表
我们可以看到堆文件的索引只能索引到对应的rowid如果需要获取数据的话还需要一次间接引用(如果页面不在内存中则是一次额外的IO)才能获取到数据。如果一张表主要的查询场景都是通过主键进行查询的话我们可以选择另外一种索引文件的组织方式即索引组织表。 索引组织表最大的特点就是通过在主键上建立索引(BTree)并在索引叶子页面上直接存储数据而非rowid融主键索引和表数据为一体。 索引组织表支持其他二级索引(Secondary Index)只不过与堆文件不同的是二级索引中存储的不是rowid而是行的主键。二级索引通过查询到记录的主键之后再访问主索引获取行记录。
索引组织表的各项操作均通过主索引进行查询或者插入数据均需要从B树的根节点开始一直到叶节点的数据页面上然后再进行对应的操作。 索引
我们常见的内存索引有很多种如HashTable, SkipList, BinaryTree, BTree等但是在传统数据库领域基本上只有B树一种B树可以说是页面为单位组织数据的数据库架构的基石。究其原因主要还是因为B树各项操作的均衡性无论是点查询范围查询还是插入删除等B树均能在可接受的IO代价内完成。
与之相比以HashTable为例HashTable支持很高效的点查询但是对范围查询则只能全表扫描对插入操作来说HashTable最大的问题是Hash桶难以动态扩张。当插入数据量大的时候如果对Hash桶的设置不合适则将导致读取操作IO数急剧增加如果进行rehash则代价巨大难以接受。
B树基本性质
B树由叶结点和非叶节点组成。数据库中使用到的B树叶结点和非叶节点一般都是以一页为单位二者结构类似只不过存放的信息略微有所不同。
对于非叶节点一个页面大小的空间中会存放一些控制信息通常放在Page Header中剩下则是Payload信息。Payload信息中存放着K个KEY和K1个子节点的指针(PID, page_id)。有些实现为了方便会额外增加一个INVALID_KEY这样非叶节点的KEY和指针个数可以一一对应。
对于叶结点其Page Header中除了一些控制信息之外还会存放其左右兄弟的指针这样整个B树的叶结点可以通过左右兄弟指针进行遍历。如果该B树是我们前文讲的索引组织表的话那么叶结点中存放的是真实的行数据。如果是Secondary Index的话存放的是索引的KEY和表的主键值(如果是Heap File的索引的话是rowid)。
B树的KEY可以是一行的某一列也可以是多个列。B树要求所有节点中存放的KEY都必须是有序的。对于非叶节点中的某个其左子树的任一KEY为右子树的任一KEY为那么满足 B树基本操作
查找
B树的查找从根节点开始逐层往下查找直到叶结点。根据每一层的KEY都是有序的特点可以选择进行二分查找(KEY较少的情况下也可以直接遍历)。找到第一个大于查找元素的KEY其左子树即是下一层要搜索的节点。 插入
B树的插入也需要先通过查找找到元素需要被插入的叶结点。如下图我们插入25通过逐层二分查找之后找到31这个值的为位置。如果叶结点有空闲空间可以插入那么只需要把插入元素放进合适插入位置就行了。如果叶节点已经满了的话需要对该节点进行分裂。
分裂方法是将当前已满的叶结点一分为二然后在合适的位置放置待插入的元素。最后像父节点插入新分裂出来的叶结点的第一个KEY。如果父节点也是满的那么需要递归对父节点进行分裂这一过程有可能持续到根节点也被分裂此时B树的高度被升高了一级。 删除
B树的删除操作一样也需要先通过查找找到待删除元素所在的叶结点然后进行删除操作。如果待删除元素不是叶结点中唯一的元素那么直接删除待删除元素即可。
如果待删除元素是该叶结点中的唯一元素则需要将该叶结点也删除掉回收空间用于后续再次利用。此时我们需要将该元素的父节点对应的KEY也删除掉。对父节点的删除也可能引发对父节点的删除操作这一过程可能递归一直到根节点。如果根节点调整后只剩下一个子节点那么我们可以将根节点也摘除掉并将根节点的唯一子节点提升为根节点。此时B树的高度被降低了一级。 B树并发策略
我们前面讲B树的基本操作都是在没有考虑并发的情况下在真实的数据库实现中B树往往是被并发读取的。一张表会被多个请求同时读写对应数据库中多个线程同时在并发读取整棵B树。无论读还是写操作我们都需要适当的加锁(latch)才能保证并发读写的安全。
最直接的想法当然是对整棵树加读写锁读加读锁(RL)写加写锁(WL)。这种做法读写虽然都安全了但是并发都太低性能不好我们需要更细致的枷锁方案以得到更好的并发。
我们来分析B树的写操作(插入和删除)
大多数情况下写操作不引发分裂或者节点摘除的情况下只需要操作目标元素所在的叶结点即可此时我们只需要对该叶结点加写锁就可以了。 随机情况下一个叶结点平均插入或者删除N次才会引发一次分裂或者摘除。此时我们需要对当前叶结点的父节点也进行写操作此时我们需要对父节点也加写锁。即父节点被加写锁的概率是子节点的1/N。
有了上述观察我们来看常用的B树并发策略(Crabbing协议)。
读操作(查找)
读操作从根节点开始逐个节点进行加读锁进行元素查找获取子节点读锁然后释放读锁的过程。如一开始获取根节点读锁查找到KEY出现的子节点然后获取子节点的读锁再释放根节点的读锁。 写操作(插入或删除)
对于写操作也是从根节点开始先获取根节点的写锁进行元素查找找到子节点后获取子节点写锁。获取到子节点写锁之后需要检查父节点是否安全如果安全则可以释放所有父节点的写锁。所谓安全即子节点的操作是否会引起父节点的写入。如某个节点X可以容纳的最大元素(叶结点为KEY个数非叶节点为子节点个数)是N当前元素个数为K 1 K 1 N那么我们知道无论X的子节点如何分裂或者摘除X的父节点都不会受影响因此我们可以安全的释放X的所有父节点的写锁。 数据库扩展技术
随着互联网时代数据量的增大以及对并发读写事务需求量的增加传统的单机数据库已经难以满足互联网时代应用对数据库的需求。底层数据库的瓶颈可能来自存储即单机无法存储下应用所需要的数据量也可能来自计算即大量的读或者写QPS让数据库难以负担。由此产生了各类数据库扩展技术在不同程度上部分解决了以上两个问题。 Sharding
Sharding技术在PC互联网时代使用较多常见的各类数据库中间件如淘宝的TDDL等就采用的这种方案。这种方案本质是由应用层去感知底层数据库的分库分表信息然后在应用层确定查询的路由并合并查询的结果。写入数据时也由应用层自己来保证涉及到多个分库时的事务的成功。Sharding方案一定程度上解决了数据库存储的瓶颈但是对于数据计算的瓶颈仍然未能解决。
Share-Storage
目前这种方案几乎是有自研数据库(微软/Google)的云服务厂商之外的其他厂商的标配典型代表有Amazon Aurora腾讯云TDSQL-C以及阿里云的PolarDB-1.0。这种方案的特点是一写多读多个计算层实例共享底层存储服务且由底层存储服务来解决数据的一致性从而简化计算层的逻辑。以已公开论文的Aurora为例其实现有如下特点 充分利用云服务厂商的基础设施共享存储层几乎都是建立在云服务厂商提供的云存储之上。 充分利用开源代码云服务厂商可以将开源数据库(MySQLPostgreSQL)代码与自己研发的存储层充分结合。在一套存储层基础设施的基础上通过替换MySQL, PostgreSQL的存储层从而可以在一套存储上支持多种数据库且能做到100%兼容。 由于对SQL和事务层代码未做大调整这种方案都只支持单节点写入。通过底层存储服务解决数据存储的可靠性和可扩展的问题通过增加多个只读副本来解决读QPS可扩展的问题。写入节点与只读节点之间写入节点与存储层之间通过事务的原始redo log进行同步效率比MySQL多副本之间通过bin log进行同步高了非常多。 Share Storage的方案解决了存储和读的可扩展但依然存在单点写入瓶颈。云服务厂商采用这种方案有着自己非常现实的考虑 这种方案可以复用开源数据库大部分代码且能做到100%兼容(不仅SQL兼容行为也兼容)充分降低了开发难度属于一个非常合适的折中。 100%兼容多种开源数据库对于以MySQL, PostgreSQL等为主的互联网中小企业而言几乎可以做到无感迁移。 对存储和读请求做了充分的扩展单点写入也是考虑到实现难度兼容性以及客户特性的折中。使用云服务的多数都是互联网中小客户相对写入扩展对读和存储扩展的需求更大一些。
Share-Nothing
目前主流的分布式数据库即所谓NewSQL数据库的实现多采用了Share Nothing的架构。这类架构数据库实例之间不共享存储自己管理自己分区的数据。这是一种完全不同于过去的全新的关系数据库架构需要从SQL事务存储等各个子系统都考虑到扩展性。这类系统的第一个实现是Google的Spanner(Spanner2012)但Spanner支持的存储模型并不是关系模型因此Google F1(F12013)又在Spanner的基础上实现了对SQL的支持成为了一个完整的分布式关系数据库。
受此启发国内互联网企业受制于传统数据库Oracle的限制也纷纷开始了自己的研发计划。目前国内已经商用的分布式数据库主要有三个实现即阿里系蚂蚁集团的OceanBase和阿里云的PloarDB-X(即PolarDB-2.0)以及独立数据库开发商PingCAP的TiDB。
这类分布式数据库都采用了LSM树用于构建底层的存储系统上层通过Paxos或者Raft协议来保证多个副本之间的一致性通过自动的数据分区(可类比MySQL的分表)来解决不同分区数据的并行写入同时通过两阶段提交协议来支持跨分区的多机事务。
这类实现对存储和读写请求的扩展都有了非常好的支持可以说从根本上解决了数据库可扩展的问题。以TPCC Benchmark的结果看排在榜单第一的OceanBase的的事务(写操作)处理能力已经是传统数据库Oracle的20倍。 OceanBase能取的这样的TPCC榜单成绩正是得益于分布式数据库的可扩展能力。整个系统的事务处理能力可以随着部署实例的增加线性扩展而传统的数据库则做不到这一点。
但这类数据库研发门槛高同时LSM树自身的Compaction机制会导致在Compaction时会占用非常大的CPU和IO因此这类数据库需要对Compaction的时机和策略有非常细致的设计否则会显著影响到系统的稳定性。
关于LSM树的原理及各类操作会在本系列的第二篇文章《数据库存储与索引技术二 分布式数据库基石——LSM树》中进行详细介绍。
参考文献
传统数据库
《数据库管理系统实现基础讲义》:https://github.com/oceanbase/oceanbase/blob/master/docs/docs/lectures/index.md PostgreSQL物理存储介绍http://rachbelaid.com/introduction-to-postgres-physical-storage/ 《MySQL技术内幕》https://book.douban.com/subject/24708143/ 《MySQL B树并发控制机制前世今生》http://mysql.taobao.org/monthly/2018/09/01/ 《Coarse-Gr Coarse-Grained, Fine-Gr ained, Fine-Grained, and Lock-F ained, and Lock-Free Concurr ee Concurrency Approaches for Self-Balancing B-Tree》 : https://digitalscholarship.unlv.edu/cgi/viewcontent.cgi?article4733contextthesesdissertations
Share Disk架构
Aurora原始论文:https://www.allthingsdistributed.com/files/p1041-verbitski.pdf Amazon Aurora解读https://dbaplus.cn/news-160-1748-1.html Amazon Aurora解读2: https://blog.acolyer.org/2019/03/25/amazon-aurora-design-considerations-for-high-throughput-cloud-native-relational-databases/ 腾讯云TDSQL-C架构解析:https://www.modb.pro/db/53642 3. OceanBase TPCC测试
OceanBase TPCC结果http://tpc.org/tpcc/results/tpcc_results5.asp?printfalseorderbytpmsortbydesc OceanBase TPCC测试细节https://developer.aliyun.com/article/761887
欢迎访问 OceanBase 官网获取更多信息https://www.oceanbase.com/ 文章转载自： http://www.morning.dwxqf.cn.gov.cn.dwxqf.cn http://www.morning.mfsxd.cn.gov.cn.mfsxd.cn http://www.morning.zknxh.cn.gov.cn.zknxh.cn http://www.morning.ctfwl.cn.gov.cn.ctfwl.cn http://www.morning.jmwrj.cn.gov.cn.jmwrj.cn http://www.morning.rfpb.cn.gov.cn.rfpb.cn http://www.morning.jkzjs.cn.gov.cn.jkzjs.cn http://www.morning.4q9h.cn.gov.cn.4q9h.cn http://www.morning.fxzlg.cn.gov.cn.fxzlg.cn http://www.morning.zrhhb.cn.gov.cn.zrhhb.cn http://www.morning.zpstm.cn.gov.cn.zpstm.cn http://www.morning.qytyt.cn.gov.cn.qytyt.cn http://www.morning.mwrxz.cn.gov.cn.mwrxz.cn http://www.morning.qxjck.cn.gov.cn.qxjck.cn http://www.morning.rjrlx.cn.gov.cn.rjrlx.cn http://www.morning.hmbxd.cn.gov.cn.hmbxd.cn http://www.morning.jwtjf.cn.gov.cn.jwtjf.cn http://www.morning.lztrt.cn.gov.cn.lztrt.cn http://www.morning.kpxnz.cn.gov.cn.kpxnz.cn http://www.morning.jyzqn.cn.gov.cn.jyzqn.cn http://www.morning.mlhfr.cn.gov.cn.mlhfr.cn http://www.morning.fndmk.cn.gov.cn.fndmk.cn http://www.morning.vjwkb.cn.gov.cn.vjwkb.cn http://www.morning.lwdzt.cn.gov.cn.lwdzt.cn http://www.morning.gkdqt.cn.gov.cn.gkdqt.cn http://www.morning.wwthz.cn.gov.cn.wwthz.cn http://www.morning.fbrshjf.com.gov.cn.fbrshjf.com http://www.morning.sbrpz.cn.gov.cn.sbrpz.cn http://www.morning.ymmjx.cn.gov.cn.ymmjx.cn http://www.morning.xpmwt.cn.gov.cn.xpmwt.cn http://www.morning.hphrz.cn.gov.cn.hphrz.cn http://www.morning.qcygd.cn.gov.cn.qcygd.cn http://www.morning.pwxkn.cn.gov.cn.pwxkn.cn http://www.morning.zmzdx.cn.gov.cn.zmzdx.cn http://www.morning.jzmqk.cn.gov.cn.jzmqk.cn http://www.morning.kxymr.cn.gov.cn.kxymr.cn http://www.morning.mlpch.cn.gov.cn.mlpch.cn http://www.morning.rhmpk.cn.gov.cn.rhmpk.cn http://www.morning.gqfbh.cn.gov.cn.gqfbh.cn http://www.morning.fxqjz.cn.gov.cn.fxqjz.cn http://www.morning.xkjrq.cn.gov.cn.xkjrq.cn http://www.morning.fqqcn.cn.gov.cn.fqqcn.cn http://www.morning.nmwgd.cn.gov.cn.nmwgd.cn http://www.morning.bxqpl.cn.gov.cn.bxqpl.cn http://www.morning.rhchr.cn.gov.cn.rhchr.cn http://www.morning.frfpx.cn.gov.cn.frfpx.cn http://www.morning.wzdjl.cn.gov.cn.wzdjl.cn http://www.morning.tkztx.cn.gov.cn.tkztx.cn http://www.morning.btblm.cn.gov.cn.btblm.cn http://www.morning.yrhd.cn.gov.cn.yrhd.cn http://www.morning.rxtxf.cn.gov.cn.rxtxf.cn http://www.morning.pmhln.cn.gov.cn.pmhln.cn http://www.morning.hmsong.com.gov.cn.hmsong.com http://www.morning.nngq.cn.gov.cn.nngq.cn http://www.morning.bqwnp.cn.gov.cn.bqwnp.cn http://www.morning.qgdsd.cn.gov.cn.qgdsd.cn http://www.morning.wtcbl.cn.gov.cn.wtcbl.cn http://www.morning.qdrrh.cn.gov.cn.qdrrh.cn http://www.morning.gtcym.cn.gov.cn.gtcym.cn http://www.morning.wdnkp.cn.gov.cn.wdnkp.cn http://www.morning.tkzrh.cn.gov.cn.tkzrh.cn http://www.morning.dgknl.cn.gov.cn.dgknl.cn http://www.morning.rxhs.cn.gov.cn.rxhs.cn http://www.morning.spdyl.cn.gov.cn.spdyl.cn http://www.morning.hslgq.cn.gov.cn.hslgq.cn http://www.morning.bsjxh.cn.gov.cn.bsjxh.cn http://www.morning.blzrj.cn.gov.cn.blzrj.cn http://www.morning.mjkqj.cn.gov.cn.mjkqj.cn http://www.morning.qfnrx.cn.gov.cn.qfnrx.cn http://www.morning.qdbcd.cn.gov.cn.qdbcd.cn http://www.morning.htsrm.cn.gov.cn.htsrm.cn http://www.morning.qfmns.cn.gov.cn.qfmns.cn http://www.morning.qphcq.cn.gov.cn.qphcq.cn http://www.morning.zhqfn.cn.gov.cn.zhqfn.cn http://www.morning.ghqyr.cn.gov.cn.ghqyr.cn http://www.morning.wqbrg.cn.gov.cn.wqbrg.cn http://www.morning.blbys.cn.gov.cn.blbys.cn http://www.morning.zfkxj.cn.gov.cn.zfkxj.cn http://www.morning.qbtkg.cn.gov.cn.qbtkg.cn http://www.morning.mhsmj.cn.gov.cn.mhsmj.cn
