`
isiqi
  • 浏览: 16493338 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

数据库如何抵抗随机IO:问题、方法与现实

阅读更多

from: http://wangyuanzju.blog.163.com/blog/static/13029201132154010987/

网易NTSE还不错...

随机IO几乎是令所有DBA谈虎色变的一个问题,这个问题,往往在数据量小的时候不出现,在数据量超过内存大小时,才陡然出现,令没有经验的DBA促不及防,也令有经验的DBA寝食难安。

传 统的数据库架构对随机IO几乎没有还手之力。传统数据库的核心通常是页级缓存、B+树、堆或索引组织表,这些机制,对随机IO的抵抗能力,都无一例外的可 悲的差。页级缓存有很强的“连坐”效应,就是为了要缓存一条有价值的记录,顺带可能要同时缓存百条无价值的记录。传统上这一点自豪的称之为 locality,是用来减少IO的,但往往会导致内存缓存的利用率很差。在记录的级别,应用的访问模式通常符合Zipf分布,其中10%的记录所占的访 问概率超过90%。如果我们用记录级的缓存,用相当于数据量10%的内存,就可以消除90%的IO,但用页级缓存,这10%的热点记录,很可能就分布在 70%的页面上,这样同样10%的内存,很可能只能消除可悲的30%的IO。B+树的情况也好不了,如果索引大于内存量,每次随机的索引搜索、插入和删 除,几乎都将带来一次随机IO(假设索引的非叶节点都在内存中)。

新的SSD硬件可以缓解随机读问题,但对随机写依然是无能为力。SSD的技术比较成熟了,期望它哪一天能魔术般的也搞定随机写,是不现实的。但我们可以从数据库架构上来想办法,谢天谢地,其实有很多办法,虽然未必能马上就用上。

先说记录的随机IO。之前已经说过,用记录级的缓存是很好的,我们NTSE的测试 表 明这一招很有效。但似乎不太有公开的数据库支持类似的功能。退而求其次,大家可以用Memcached,但两者有重大区别。用Memcached时,很难 保证Memcached与数据库的一致性,除非用数据库事务来保证,但这样会导致在两个系统之间进行每个事务毫秒级的锁定。虽然数据库内置的记录级缓存也 需要用某种加锁机制来保证一致性,但这个锁定时间是微秒级的,并发度不可同日而语。但最重要的一点是,Memcached通常只能消除随机读IO,对随机 写无能为力。而数据库内置的记录级缓存,则可以很好的解决这个问题。数据库内置记录缓存的设计,常用的有几招:
1、最基本的一招是,如果要访问的 记录在记录缓存中,就不去读底层的堆文件。当然这是废话,如果不这样,那还叫记录级缓存吗?但如果仅仅是这样,记录缓存跟Memcached是一样的,还 不如用Memcached,更灵活。但接下来数据库内置记录级缓存的招数,基本上都是Memcached搞不定的。
2、如果仅仅如果更新命中了记录缓存中的记录,则只更新记录缓存,不更新底层的堆等存储。具体细化下来有UPDATE和DELETE两种,NTSE暂时只能搞定UPDATE;
3、 记录缓存里的东西,总是要有周期的持久化的,否则恢复时间不能保证。这个第三招,就是持久化也就是把记录缓存中的脏记录dump出去的时候,不要去更新对 应的堆中的记录,否则短时间就会爆发大规模的随机读写,做法应该是像内存数据库那样,把脏记录用顺序写IO dump出来。NTSE就是这么做的,刷记录缓存脏记录时,我们先看看对应的页面在页面缓存中在不在,在,则更新堆,否则顺序dump到log中。
4、在更新时,可以只把UPDATE后的后像插入到记录缓存中,根本不去读原来的记录,当然这个要看具体情况,如果后像是依赖于前像的那这招就不灵,但很多时候是可以用的,比如根据主键找到一条记录,不管3721把其中一些属性改掉。NTSE暂时还搞不定这招,有待改进。

记录缓存的这4招,消除数据库中记录操作带来的随机IO是很有效的。遗憾的是这不是必杀技,如果记录的访问确实的纯随机的就会失效,幸运的是这样的情况不常出现。

索 引的随机IO问题要更复杂一点。我们简单点,只说涉及到单个索引项的操作。传统的B+树,无论是搜索、插入还是删除(更新相当于插入+删除,就不额外讨论 了),理论上都是O(log(B)(N))次IO(其中B是页面包含的键值数,N是总键值数),但实际情况下可以假设非叶节点都在内存中,因此是1次 IO。磁盘一般只能有每秒几百次随机IO,因此对大的索引,每秒只能有几百次操作,这个性能真是低的可怜。B+树是70年代的老怪物,但直到今天,大多数 数据库里仍然用得是它,但实际上,有比传统B+树更能对付随机IO的东西。

1996年,P O'Neil等提出的 LSM-Tree 是一个重大 突 破。LSM-Tree主要有两种变形,最简单的LSM-Tree,是一个内存中的小索引加上外存中的大索引,更新先缓存在小索引中,再批量更新到大索引, 这样就有望合并对属性同一页面的多次更新的IO。复杂的LSM-Tree,是划分为多个level的很多的小索引,每个level的大小,近似的是前一个 level大小的r倍,如果一个level有r个小索引,则合并形成一个下一level的较大的索引,这样随机插入或删除的平均IO开销可以降低到 log(N)/B次,是一个很大的提升。但带来的问题是,搜索的时候,就要搜索这么多个小索引,而这样的索引会有O(log(N/B))个,那是可能有几 十个,搜索的性能就可能下降几十倍,这往往也带来问题。LSM-Tree已经有不少的现实应用,BigTable、Cassandra、Lucene等这 些用的是复杂的那种LSM-Tree,InnoDB的change buffer可以说是那种一大一小的简单LSM-Tree。NTSE想在做多版本事务的时候顺便实现change buffer。

2000年,MA Bender等提出的Cache Oblivious B-Tree 是第二个重大突破。这个跟LSM-Tree有些类似,也是索引从小到大分成相邻大小翻倍的多个索引,因此随机插入或删除的平均IO开销也是log(N)/B次,但它用了Fractional Cascading 的技术,使得搜索的性能较传统B+树相关不多。虽然论文发表了10年了,这种索引似乎现在只有TokuDB 一家实现,它是称之为Fractal Tree。我们拿来试了试,效果果然出奇的好。

有没有可能将来搞出一个比Fractal Tree更好的东西呢,遗憾的是如果硬件不发生根本改变,已经证明Fractal Tree已经是最理想的了。

但LSM-Tree或Fractal Tree,其实只是消除索引的随机插入和删除带来的随机IO,对随机搜索没什么帮助。这个剩下的索引的随机搜索问题比较复杂,要分解来看。一种是真正的来自于应用需求的搜索,另一种是检查唯一性带来的搜索。这两种处理方法是不同的。

对 于真正的来自于应用需求的搜索,处理还得借助于记录级缓存类似的技术,但这时变成索引项的缓存了。InnoDB中的Adaptive Hash Index就是这个东西。但对检查唯一性带来的搜索,Bloomfilter是个好方法,经常可以消除98%以上不必要的检查。所以BigTable里就 用。但对传统B+树由于索引是实时更新的,Bloomfilter不好用,对Fractal Tree,索引是在merge的时候再批量更新的,可以用Bloomfilter。我们试了TokuDB,根据性能表明看,它对索引性索引的随机插入,也 能轻松对付,估计也是用了Bloomfilter类似的技术。

因此,我们可以看到,随机IO这个老大难的问题,其实还是有不少的技术可以 解决的。然而,现实是悲摧的,我们经常在用的主流数据库,无论是商业的Oracle、DB2、SQL Server,还是开源的MySQL、PostgreSQL,都基本上还在用最老土的技术,InnoDB里搞了一点change buffer,就能让人津津乐道半天。NoSQL系统走在前面,用上了LSM-Tree,但也并不是最先进的,搜索的性能经常令人担忧。在索引这方 面,TokuDB走在前面,但还没为大众接受。记录方面,不清楚为什么大家不作记录级缓存,这不是很难的事,莫非认为用Memcached就可以了,“因 为善小而不为”?

相信未来,总有改善的一天。

分享到:
评论

相关推荐

    事件减少:一种算法,用于优化可多次运行的数据库查询

    使用Event-Reduce在没有Disc-IO的情况下几乎立即在CPU上计算新结果效率在您可以看到对于随机生成的事件,其中约94%的事件可以通过EventReduce进行优化。 在现实世界中,如果使用非随机事件,则可能会更高。 对于...

    网管教程 从入门到精通软件篇.txt

    、Lipper、FoxPro、Arago、Wordtech、Xbase和类似数据库或与数据库有关产品识别;可用数据文件(能被Excel 97打开);Oracle 8.1.x表格空间文件 DBX:DataBearn图像;Microsoft Visual FoxPro表格文件 DCT:...

    java实验报告、Java课件

    这些题目可能涵盖数据库管理系统的实现、Web服务的开发或是游戏编程等,旨在提升学生的项目经验和实际问题解决能力。在完成课程设计时,学生需要综合运用Java的各个方面,进一步加深对语言的理解。 总的来说,这份...

    自动组卷系统

    类定义了对象的属性(数据成员)和行为(方法),并且可以看作是现实世界中对象的抽象。 标签“java”表明这个话题与Java编程语言相关。Java是一种广泛使用的、跨平台的、面向对象的编程语言,由Sun Microsystems...

    dsfsdgsdgs

    10. **IO流与NIO**:Java的IO流用于读写文件、网络通信等,新的NIO(New IO)提供了一种非阻塞的I/O模型,提高了效率。 11. **多线程**:Java内置对多线程的支持,允许同时执行多个任务,提高程序的并发性能。 12....

    JAVA面试试题

    - `Vector`:与`ArrayList`类似,但线程安全,性能略低。 - `LinkedList`:基于双向链表实现,插入删除效率高,但随机访问效率低。 #### 八、多线程编程示例 示例代码展示了如何通过内部类实现线程,分别对共享...

    java面试题大全带答案.pdf

    - **抽象**:抽象是将复杂的现实问题简化,关注主要特性,忽略不重要的细节。在Java中,抽象通过抽象类(abstract class)和接口(interface)来实现。 - **继承**:继承允许子类继承父类的属性和方法,减少了代码...

    华为java面试题

    4. **抽象**:抽象是对复杂现实世界的简化表示。抽象类不允许实例化,主要用于定义一个类的基础结构,其子类可以进一步扩展具体的功能。 #### 二、String是不是最基本的数据类型? 不是。在Java中,`String`是一个...

    2021-2022计算机二级等级考试试题及答案No.17188.docx

    - **知识点解析**:数据库的概念模型是对现实世界的抽象,它不依赖于具体的数据库管理系统(DBMS)或硬件平台。E-R图是常用的一种概念模型表示方法。 - **独立性**:概念模型独立于具体的机器和DBMS,即不受特定的...

    javam面试题

    - **抽象**:抽象是将复杂的现实问题简化为一系列概念,忽略不重要的细节,关注主要功能。在Java中,抽象通过抽象类和接口实现。 - **继承**:继承允许子类继承父类的属性和方法,减少了代码重复,增强了代码复用...

    超级有影响力霸气的Java面试题大全文档

     Servlet被服务器实例化后,容器运行其init方法,请求到达时运行其service方法,service方法自动派遣运行与请求对应的doXXX方法(doGet,doPost)等,当服务器决定将实例销毁的时候调用其destroy方法。 与cgi的区别...

    java华为面试题

    面向对象编程(Object-Oriented Programming,简称OOP)是一种程序设计思想,它的核心是将现实世界中的事物抽象成对象,通过对象来实现软件设计。面向对象的特征主要包括以下几个方面: 1. **封装**:将对象的状态...

    java swing学生考试系统

    首先,面向对象开发(OOP)是Java编程的核心,它将现实世界中的问题转化为计算机可以理解的模型。在Java Swing学生考试系统中,OOP体现在类的设计和继承关系上。每个功能模块,如试题管理、用户界面、分数计算等,都...

    C#仿抽奖模式

    在IT行业中,编程语言C#被广泛用于开发各种应用程序,包括模拟现实世界活动的软件,如抽奖系统。"C#仿抽奖模式"就是一个基于C#的项目,它旨在创建一个抽奖程序,允许用户输入个人信息,并在点击“开始”按钮后,随机...

    JAVA--pdf3

    13. **Java标准库**:Java的API包含大量预先定义的类和方法,如集合、IO、网络、XML处理等,为开发者提供了便利。 14. **JDBC**:Java Database Connectivity是Java访问数据库的标准接口,允许开发者编写与数据库...

    JAVA上百实例源码以及开源项目源代码

    Java二进制IO类与文件复制操作实例 16个目标文件 内容索引:Java源码,初学实例,二进制,文件复制 Java二进制IO类与文件复制操作实例,好像是一本书的例子,源代码有的是独立运行的,与同目录下的其它代码文件互不联系...

    学习资料整理合集完整版

    通过面向对象编程,我们可以更好地模拟现实世界中的问题,使代码更易于理解和维护。 【异常处理】 在Java中,异常处理是一个重要的概念,用于处理程序运行时可能出现的问题。Java提供了try-catch-finally语句块来...

    Java软件开发实战 Java基础与案例开发详解 14-8 练习题 共6页.pdf

    面向对象分析与设计是一种软件开发方法论,它侧重于识别、设计和实现系统中的对象。 #### 7.2 对象模型建立 对象模型是对系统中的对象及其相互关系的描述,通常通过UML(统一建模语言)类图来表示。 #### 7.3 类...

    SYSC4005:生活是模拟

    2. **数据结构与算法**:学习如何高效地存储和操作数据,如数组、链表、栈、队列、树、图等,以及如何选择合适的算法解决特定问题。 3. **事件驱动编程**:模拟系统通常涉及到事件的处理,如时间推进、用户交互等,...

Global site tag (gtag.js) - Google Analytics