这篇文章是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/