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

标签: 技术资料 | 发表时间:2011-05-31 10:00 | 作者:唐福林 {ZuiZui}
出处:http://blog.fulin.org

随机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就可以了,“因为善小而不为”?

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

转自:http://wangyuanzju.blog.163.com/blog/static/13029201132154010987/

用bShare分享或收藏本文

相关 [数据库 随机 io] 推荐:

淘宝海量数据库之六-克服随机IO难题

- William - 阳振坤的博客
与传统磁盘相比,SSD固态盘提供了非常好的随机读性能,单盘可达35000IOPS (4KB)甚至更高,并提供512MB/s或以上的读出带宽. 但通常SSD盘的随机写性能甚至比一般磁盘更差,这是因为,尽管SSD的读和写都以4KB页(page)为单位,但SSD写入前需要先擦除已有内容,而擦除以块(block)为单位,一个块(block)通常是128个连续的页(page),即512KB.

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

- {ZuiZui} - 唐福林-博客雨
随机IO几乎是令所有DBA谈虎色变的一个问题,这个问题,往往在数据量小的时候不出现,在数据量超过内存大小时,才陡然出现,令没有经验的DBA促不及防,也令有经验的DBA寝食难安. 传统的数据库架构对随机IO几乎没有还手之力. 传统数据库的核心通常是页级缓存、B+树、堆或索引组织表,这些机制,对随机IO的抵抗能力,都无一例外的可悲的差.

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

- crystal - 风轻扬
随机IO几乎是令所有DBA谈虎色变的一个问题,这个问题,往往在数据量小的时候不出现,在数据量超过内存大小时,才陡然出现,令没有经验的DBA促不及防,也令有经验的DBA寝食难安. 传统的数据库架构对随机IO几乎没有还手之力. 传统数据库的核心通常是页级缓存、B+树、堆或索引组织表,这些机制,对随机IO的抵抗能力,都无一例外的可悲的差.

MySQL数据库的IO操作

- - haohtml's blog
         淘宝丁奇分享的PPT:MySQL数据库的IO操作,详细分享了四块的内容,并且告诉大家如何调整MySQL数据库IO操作相关的参数,给出了详细的选择策略,现替其整理成文章分享与此. 4.影响io行为的一些参数和选择策略. 一个简单的查询 select * from t where id>=(  select id from t where k1=100 limit 100000,1) limit 2;.

一次IO利用率100%,数据库大量全表扫描问题

- - CSDN博客推荐文章
 1, 具体什么业务受到影响不清楚,但从系统测看,主机IO资源比较紧张(HPUX 11.31 +oracle 9i). glance看IO已接近100%. 2,数据库侧看,大量db file scattered read IO相关等待事件. 3,等待的sql具体如下,主要原因是对ai.RM_A_x全表扫描,该表72GB大小.

当内存512遇上Access数据库600M,IO磁盘受伤了

- - 博客园_首页
服务器内存就512M,Access数据库(文章库)600多M,结果竟然就是IO受伤了. 秋色园技术原理解析 系列,园里不少看过的帅歌,应该有点印象,从开始到现在,还是铁打的Access数据库. 虽然本人目前对Access恨入之骨,皆因囊中羞涩,暂时不得不与之同流合污. 忙碌 微博粉丝精灵几个月来, 秋色园一直运行正常,除了远程界面都变的很卡之外,基本上也没发现什么异常.

可伸缩Web架构的4个问题:瓶颈,CPU,数据库,IO

- - 互联网 - ITeye博客
在这篇文章中我将谈到关于大规模网站架构扩展和性能方面的一些问题. 首先让我们先来了解一些术语. 稍后我将对Web应用扩展过程中所遇到的不同问题进行讲解,例如:. Web系统的性能受多方面因素的影响,但大多数开发人员主要关心的是响应时间和可扩展性这两方面. 响应时间是指Web应用从收到请求到返回响应结果所花费的时间.

物理IO与逻辑IO

- - 操作系统 - ITeye博客
IO性能对于一个系统的影响是至关重要的. 一个系统经过多项优化以后,瓶颈往往落在数据库;而数据库经过多种优化以后,瓶颈最终会落到IO. 而IO性能的发展,明显落后于CPU的发展. Memchached也好,NoSql也好,这些流行技术的背后都在直接或者间接地回避IO瓶颈,从而提高系统性能. 上图层次比较多,但总的就是三部分.

从数据库层面理解:随机 I/O & 顺序 I/O

- - CSDN博客数据库推荐文章
      在谈这俩概念前、先来说说 大I/O vs.      通常、我们把 <=16KB 的I/O认为是小I/O、而 >=32KB 的I/O认为是大I/O.      了解I/O的大小、影响到后期对缓存、RAID类型、LUN的一些属性的调优 .      当前大多数数据库使用的都是传统的机械磁盘.

linux异步IO浅析

- Sepher - kouu&#39;s home
知道异步IO已经很久了,但是直到最近,才真正用它来解决一下实际问题(在一个CPU密集型的应用中,有一些需要处理的数据可能放在磁盘上. 预先知道这些数据的位置,所以预先发起异步IO读请求. 等到真正需要用到这些数据的时候,再等待异步IO完成. 使用了异步IO,在发起IO请求到实际使用数据这段时间内,程序还可以继续做其他事情).