这篇文章是percona的在xldb2012的分享,是一篇教程,介绍了一些基本概念,比较旧了,了解概念

官方总结 ppt链接

  • 如何选取数据结构能显著减轻(signaficantly mitigate)插入/查询/更新 的开销
  • 这些数据结构数据量大了,怎样更高效的利用内存

大数据,也就是放不下内存,靠数据结构来管理,教程也是针对大数据场景下数据结构的管理来展开的

Module 1: I/O model and cache-oblivious analysis.

IO带宽,三个参数, 数据大小N,内存大小M,传块大小B

  • 如果有1000M数据,10M内存,数据块1M,怎么排序呢
    • 首先读10M 排一次,一共排100次
    • 然后10个10M合并,一共10次
    • 然后10个100M合并
  • 浪费的IO
    • 首先是N/B次 传输,然后是合并logM/B(N/B)

上面这个也叫做DAM(Disk-Access-Model)分析,因为这种场景下,内存不是瓶颈,IO是瓶颈

问题在于,对于cache-oblivious的场景,你是不知道M(可用内存) B(传输块大小)的,作者做了一版穷举B的测试,数据表示没有最佳的B

感觉作者没说完啊,对于CO怎么优化也没说

Module 2: Write-optimized data structures. We give the optimal trade-off between inserts and point queries. We show how to build data structures that lie on this tradeoff curve.

这里列的是tokudb,用的lsm tree,没啥说的

Module 2 continued: Write-optimized data structures perform writes much faster than point queries; this asymmetry affects the design of an ACID compliant database.

这里提到了mongo用的Fractal-Tree Index 没听说过这数据结构

Module 3: Case study – TokuFS. How to design and build a write-optimized file systems.

介绍tokufs,读写指标吊锤ext4

论文在这里

实现细节

  • metadata index data block index 加速
  • metadata index key记录文件名,data block index记录文件名和blocknum 连续读
  • blocksize固定512
  • 压缩索引
    • 路径名字前缀非常多余,可以优化移除
    • zero-padding,很多块占用用了padding,可以移除(?有没有安全风险?)
  • 原型阶段,不知道谁用了

Module 4: Page-replacement algorithms. We give relevant theorems on the performance of page-replacement strategies such as LRU.

讨论缓存有效性问题,引入各种cache组件,比如LRU

讨论最佳替换算法,以及竞争性分析,在线算法竞争性分析可以看这篇文章 也放在参考链接里了

具体的概念就不展开了,直接说结论

LRU LFU FIFO k-competitive

基本上LRU和内存(OPT)表现一致,多了一些内存浪费

大段时间都在证明上

还有一些需要考证的问题

  • 如果block大小不一,性能表现如何?
  • 写回(write-back)的代价
  • LRU实现起来 代价稍高(调用系统时间,其实这不算什么问题)

Module 5: Index design, including covering indexes.

b树索引加速查询但是影响插入,维护索引代价不大,所以如何索引需要考虑清楚

  • 索引缩小数据规模
  • 提高局部性
  • 排序

Module 6: Log-structured merge trees and fractional cascading.

介绍LSM tree以及LSM tree在DAM模型上的表现

如何提高点查效率

  • 缓存
  • 不聋过滤器 Bloom filter
  • fractional cascading.(?啥意思)

以及LSM加优化之后和COLA差不多

LSM tree + forward + ghost = COLA

没看懂细节 总之tokudb论文里有

还有buffer tree之类的都是对btree的优化。这里不展开了

Module 7: Bloom filters.

读完感觉没有参考资料有可读性。毕竟比较旧了,2012年的,还是挺有前瞻性的

参考资料

  • 需要了解cache-bolivious 概念 https://users-cs.au.dk/gerth/emF03/slides/cacheoblivious.pdf
  • 一个CO的简单优化,就是分治 https://blog.csdn.net/toughbro/article/details/5931029

考量cache oblivious最好是对比完全不考虑memory hierarchy结构的算法复杂度测量机制,O(nlogn)这样的,只是计数计算的复杂度。或者在console上常常做的cache aware的优化,就是针对cache line size来组织数据结构大小,一次prefetch一个cache line的数据做操作。这个cache oblivious比理想算法更接近于电脑硬件(考虑到memory hierarchiy)但也没有变态到完全根据cache line size来设计数据结构和算法。简单说来,就是假设一个cache line size,对问题进行分而治之,分的粒度到virtual cache line size,就停止分解

  • 和我第一小节差不多 https://www.jianshu.com/p/8bfb47c01a7e
  • 随便搜co搜到一篇论文 https://www.cse.ust.hk/catalac/papers/coqp_tods08.pdf
  • 算法介绍 https://blog.csdn.net/dc_726/article/details/51724097
    • 第五小结,介绍了具体的优化算法,以及列出了很多论文,不错
    • 第四小结,写优化数据结构,除了LSM tree还有很多,提供思路
  • 竞争性分析,建议看这篇文章 https://blog.csdn.net/anshuai_aw1/article/details/108467900 写的不错
  • tokudb有很多点子,催生了很多想法
    • 写优化数据库 https://github.com/weicao/cascadb
    • fractal-tree数据库 https://github.com/BohuTANG/nessDB
      • 另外,这个兄弟的博客不错,对于了解CK来说。值得看一看 https://bohutang.me/2020/06/05/clickhouse-and-friends-development/