DataStructuresandAlgorithmsforBigDatabases大数据库数据结构与算法

会计学1DataStructuresandAlgorithmsforBigDatabases大数据库数据结构与算法数据收集查询处理过程中有趣的tradeoff一个3亿行的表创建索引花了20分钟去loadthetable但是花了10天在这上面创建索引Bug#9544“SelectquerieswereslowuntilIaddedanindexontothetimestampfield...Addingtheindexreallyhelpedourreporting,BUTnowtheinsertsaretakingforever.”

Commenton“Theyindexedtheirtables,andindexedthemwell,Andlo,didthequeriesrunquick!Butthatwasn’tthelastoftheirtroubles,totell–Theirinsertions,liketreacle,ranthick.”

NotfromAliceinWonderlandbyLewisCarroll第1页/共28页Thistutorial更好的数据结构意味着减少insert/query的开销(tradeoff)这些结构在扩展到更大的尺寸的情况下更加有效、在使用内存分层的结构下LSMTREEB-TREEFractal-tree第2页/共28页我们这里怎么定义bigdata不是说TBPBEB就是bigdata，我们的定义是：数据太大不适合存储在主存中我们需要数据结构化“Index””metadata”就意味着这里有潜在的数据结构这些数据结构也太大了也不适合存在主存中第3页/共28页Inthistutorialwestudytheunderlyingdatastructuresformanagingbigdata第4页/共28页Tokutek公司介绍workingtogetheronI/O-efficientandcache-oblivious(易失)datastructurestokuDB：ACID支持；闭源的MySQL存储引擎这次totorial举的一些例子就是这个第5页/共28页这次tutorial前提selfcontained自给的想去教如果不清楚提问应该有数学基础想要听一下午时间第6页/共28页TopicI/Omodelandcache-obliviousanalysis.IO模型和分层cache分析Write-optimizeddatastructures.数据写优化Howwrite-optimizeddatastructurescanhelpfilesystems.怎样写数据结构优化帮助文件系统Block-replacementalgorithms.Indexingstrategies.

索引策略Log-structuredmergetrees.日志结构的合并树Bloomfilters第7页/共28页Module1:I/OModelandCache-ObliviousAnalysis第8页/共28页Storyformodule如果想理解数据库中数据结构的性能就需要了解现代IO模型这里有一个很长的故事来理解内存分层。Manyarebeautiful.Mosthavenotfoundpracticaluse.Twoapproachesareverypowerful后面的基础第9页/共28页现代磁盘访问的IO模型计算机如何工作数据在磁盘和RAM之间传输Block的传输时间控制着运行时间目标：最小的block传输性能取决于这些参数：blocksizeB,memorysizeM,datasizeN第10页/共28页几个例子：扫描一个队列O(N/B)I/Os搜索一个B-tree:O(logBN)第11页/共28页搜索一个队列:对比搜索array和B-tree第12页/共28页IO影响排序假设下面这几种排序问题：100Mdata10MRAM1MB磁盘块几种排序算法：每次读10M排序，写，然后继续100个10M合并10个10M为100M再跑，重复10次合并10个100M的一起再一次跑1000M排序分析第13页/共28页简化的DMA模型省去CPU开销假设所有块的访问花销相同这是一个好的性能模型么？第14页/共28页2KB或者4KB对于这种模型太小了Innodb的btree有这种尺寸顺序读取比随即读取快十倍，不适合这种模型没有一个最佳的尺寸，因为对不同的操作最佳size不相同(insert/delete)第15页/共28页第16页/共28页第17页/共28页第18页/共28页第19页/共28页Summary内存分层模型的算法模型解释了DB数据结构如何拓展There’salonghistoryofmodelsofthememoryhierarchy.Manyarebeautiful.Mosthaven’tseenpracticaluse.DMA和易失cache作用很大

ParameterizedbyblocksizeBandmemorysizeM.

IntheCOmodel,BandMareunknowntothecoder第20页/共28页Module2:Write-OptimizedDataStructures第21页/共28页写优化的数据结构性能：System:BigTable,Cassandra,Hbase,LevelDB,TokuDB一些写优化的数据结构优化能达到100倍第22页/共28页OptimalSearch-insertTradeoff优化查找插入开销第23页/共28页优化开销例图第24页/共28页一种建立写优化的数据结构的途径

(后面还有其他可能的途径)简单的写优化结构例如一个平衡二叉树删除和插入：发送insert和delete命令从根，然后存储到buffer中，当buffer满了要刷新。第25页/共28页一次insert或者delete每次花费大