LSM树凭顺序写击败传统B树 后台压缩争抢资源引爆长尾延迟

LSM树凭顺序写击败传统B树 后台压缩争抢资源引爆长尾延迟 LSM树利用追加写将写入吞吐提升近十倍，但后台合并文件时与实时读写争夺磁盘I/O，导致其响应延迟的可预测性显著逊于传统B树。 内容从极简的四行 Bash 脚本玩具数据库切入，层层递进地阐述了从 Bitcask 追加日志与内存哈希索引，演进至现代工业级 LSM-Tree（涵盖 MemTable、SSTable、Compaction、布隆过滤器与 WAL 容灾）的完整技术脉络。随后，讲座对比了 LSM-Tree 的高吞吐顺序写与 B-Tree 矮胖平衡树就地随机写的架构权衡与延迟可预测性，并剖析了分布式环境下的本地二级索引（LSI）与全局二级索引（GSI）。最后，内容转向面向海量扫描的 OLAP 分析型系统，详细讲解了数据仓库星型模型、列式存储（如 Parquet/ORC）以及利用 Bitmap 索引与游程编码（RLE）实现硬件级高速位运算的底层逻辑。 B-Tree 架构统治数据库三十余年，适合复杂事务和低延迟点查，但其原地随机写和页分裂导致写入吞吐受限；而基于顺序追加写的 LSM-Tree 在写入吞吐上可比 B-Tree 快近一个数量级。 (40:00) LSM-Tree 虽具备极高写吞吐，但其后台 Compaction 进程容易与线上实时读写争抢磁盘 I/O 和 CPU，导致其长尾延迟的稳定性与可预测性弱于 B-Tree。 (45:00) OLTP 核心瓶颈在于磁盘寻道时间，重度依赖 B-Tree 等索引；而 OLAP 瓶颈在于磁盘带宽，当扫描量超过全表 50% 时索引失效，转而依赖列式存储与高压缩比算法提升吞吐。 (72:45) 列式存储（如 Parquet、ORC）通过独立存储各列配合 Bitmap 索引与游程编码（RLE），可将多条件过滤转化为硬件级位运算，但代价是插入新数据会导致全部列文件平移，因此仅适合低频批处理写入。 (70:00)

讲师 Scott Shi 在剖析 Martin Kleppmann 的《DDIA》数据检索机制时指出，数据库底层架构由访问模式驱动，分化为依赖行式随机寻道的事务型（OLTP）引擎与追求带宽吞吐的分析型（OLAP）列式引擎两大流派。 访问模式驱动 OLTP 与 OLAP 的架构分流 (2:30) OLTP 系统面向高并发的轻量级读写，单次仅操作极少量记录，核心瓶颈在于磁盘寻道延迟，因此高度依赖索引机制进行单行快速定位。相较之下，OLAP 系统服务于企业决策分析，典型查询需要扫描全表 50% 甚至全部数据，此时传统索引失去意义，系统瓶颈转移至磁盘带宽与吞吐量，促使架构转向只读批量导入、宽表不可变事件流与激进的数据压缩。 OLTP 存储内核：B-Tree 的稳定性与局限 (35:00) B-Tree 架构通过构建 3 到 4 层的矮胖平衡树结构，仅需跳转约 3 次指针即可定位数据，单扇出为 100 时 4 层即可索引 250 TB 数据，读写延迟平稳可预测且善于处理复杂事务。但其弱点在于采用就地修改（In-place Update）与随机写入，页分裂（Page Split）和物理碎片化导致范围扫描成本高昂，且高并发写场景下吞吐受限，需通过 WAL 或写时复制（Copy-on-Write）避免断电产生半写损坏。 LSM-Tree 的高吞吐写入与后台资源竞争 (20:00) LSM-Tree 通过纯顺序追加写规避就地修改，写入先落入 WAL 与内存中的 MemTable（通常为跳表或平衡树），写满后冻结为不可变的 SSTable 文件，写吞吐理论上比 B-Tree 快 6 到 10 倍。为了控制空间膨胀并处理删除标记（Tombstone），系统必须在后台执行文件合并压缩（Compaction）；若参数未精心调优，激进的压缩任务会与实时请求争抢 CPU 和磁盘 I/O，导致长尾延迟相比 B-Tree 更难预测。在读取方面，LSM-Tree 依赖稀疏索引与布隆过滤器（Bloom Filter）来避免遍历所有 SSTable 寻找不存在的键。 分布式二级索引与关系型索引形态 (47:30) 在分布式 NoSQL（如 DynamoDB）中，本地二级索引（LSI）将索引与数据限制在同分区内，单分区写入快，但跨分区全量读取需高成本广播扇出（fan-out）；全局二级索引（GSI）提供集中视图保证高速读，但写入面临跨网络和跨分区写放大，配置 5 个 GSI 最坏需并发写入 6 个分区。在单机关系型引擎中，InnoDB 聚簇索引将行数据与主键绑定，二级索引需回表查询，而覆盖索引（Covering Index）通过将目标字段附加在索引中以消除回表磁盘 I/O；多维空间数据则需借助 R-Tree 或 GeoHash，全文模糊检索则需依赖 Trie 树回溯。 列式存储的位图索引与写入倾斜成本 (64:30) 面对宽表上百个字段而分析仅需少数列的场景，Apache Parquet 等列式存储将每列独立落盘，使有效数据利用率从传统行式的 4%–5% 提升至 100%。列式存储结合位图索引（Bitmap Index）与游程编码（RLE），能够将多维度复合筛选转换为硬件底层的按位与（Bitwise AND）指令操作。然而，为了保持列内严格有序以实现极高压缩率，插入任意新行需要修改所有列文件并平移数据（复杂度达 O(N)），因此列式数据库排斥实时随机写，只适合按小时或天为周期的批量批处理导入。 数据检索引擎不存在全能解法：B-Tree 胜在事务一致性与可预测的低延迟点查，LSM-Tree 以后台合并波动为代价换取极致写吞吐，而列式存储则彻底放弃随机写以实现十亿级数据的大规模分析扫描。

[0:00] Scott Shi: 前两章其实我觉得比较 boring [6:55] Scott Shi: 当你觉得业务使用模式不是很熟悉的时候，一定要主动追问面试官：你的 Access Pattern 是什么？ [14:48] Scott Shi: 数据库的值永远只有两种结果——要么返回正确的数据（Correct Result），要么抛出异常（Throw Exception），绝对不能返回错误的脏数据（Wrong Answer）！ [45:00] Scott Shi: less predictable than B-Tree [56:15] Scott Shi: 我的 stakeholder，我的甲方爸爸 [56:15] Scott Shi: Immutable（不可变数据）是一个非常好的设计理念 [60:30] Scott Shi: 很容易就 100 多个 column [71:45] Scott Shi: 读的 call 非常 heavy [72:45] Scott Shi: 要不要 index 已经无所谓了

[0:00] 这个的话是Martin的第三章Chapter 3这张非常有趣前两张其实我觉得比较 boring他有讲了很多history这张就相对比较有趣一点就是touch到一些比较有趣的内容了然后这张呢首先画一张图就是把这个database呢按type分成了几种下面这个是Btree的东西就是Btree,BplusTreeFamily这里面有MySQL,MongoDB,Postgres就是典型的Btree然后上面是比较新的叫LockStructuredStorage或者LockStructuredMergeTree这种有Cassandra,有HBase,有Reag,有Lucing这个是RockDB,LevelDBDenimal也属于这方面的虽然Denimal没有列吧但是Cassandra你可以以为这是OpenSource的Denimal然后在这个右面的是这个Analytic DatabaseAnalytic Database的话它有一些比如说这个HDFSHadoop File System然后在Hadoop File System有Hive, Impala, Impala和PrestoImpala我记得是哪一个公司的一个也是一个Apache顶级的一个project,我忘了是哪一个公司了,然后还有这个encoding,这个有个parkread是吧,就是它这个一个最近非常流行的一个encoding,column based的encoding,其实我忘了parkread是什么,最近非常流行,也是这个analytic database的一方面,然后这个analytic database data model的话是star schema就是我们稍后也会简单cover一下然后redshift像那个redshift的话就是景象大神工作的那个公司他也是做analytic database但是他们是用了自己的东西他们毕竟是从98年99年开始所以他们都是自己的customize code然后还有一些scientific database比如说array databaseGenome data,这都是一些Centific database,不会cover一般来说,除非你在学校或者做research,一般也不会cover这些好,我们回顾一下如果database分成两个大的module的话左边是transactional databasetransactional database,就是所有的request它讲究的是一个小的request然后它每次fetch比较少量的data然后clude就是create,read,update,delete少量的data然后再返回所以它这个bottleneck是能很快的index很快的locate那个data所以你需要indexing来去improve这个bottleneck右面是analytic它这个work pattern是早见比如说你说的那个你说开的store里面哪一个store最profitable那你实际上是要读大量的整个table都要scan一遍很多时候大部分lookup pattern是整个table需要scan一遍那你整个table需要scan一遍的话它这个focus是什么呢focus上怎么样能把这个data增加这个data的throughput是吧怎么样能处理更快一点增加这个dataprocessing的throughput所以你可能要做compress并且需要做不同于transactional的compress它的index有没有那么必要了因为你要fetch50%以上的data的时候你index不index没有区别所以这个index可能就不是那么重要了所以这是相当于是两种完全不同的use case就是transactional data和analytic data在transactional data里面这也是传统database里面里面,非常老的就是Btree,Btree是从1970年就是Stonebreaker这些非常老的researchers写的东西,Stonebreaker还在做database相关东西,Stonebreaker还放到了很多startup然后这个logstructure merge trade呢就是这个是比较新的了也是你看它这个应用的不管是Cassandra还是还是这个RockDB,LevelDB,还是Lucine是非常新的了它有它自己的优点这是2000年以来就是一次突破这是对B trade的一次突破,之前都是B trade dominant好,如果我们从high level来讲什么是database呢?database呢从most fundamental level的话,database就出了两件事一个是stored data,然后一个是read data,一个write,一个read,一个write,一个read,非常简单。然后如果你想实践database的话,你可以用非常简单的四行code,就可以实践一个database。然后这个database就是非常简单,就是你把这个database变成一个file了。你setdatabase的时候,就是write database的时候,你就是key value,$1,第一个parameter是key,第二个parameter是value,你就把它写到这个file里面,append到这个database file里面当你read这个value的时候 [5:00] 把它另一行首先用这个Grip,这个Linux command grip找建的那一号,然后把那个Key和这个豆号给取掉,然后你找建最新的一个value,那就是这个read了,就是比如说你同一个值写了多遍,比如说我们进化下面的例子,你开始的时候set是123456,然后是set到那个London的big bang是吧,然后你又SET的42,SET是SAN FRANCISCO,你再SET一次的时候,再SET42,SET的层,比如说,New York City,是吧?当你get 42的时候,你是get latest,因为是Tale,Tale是latest,所以这就是一个database了,这就是一个,一个非常弱智版的database就一个read一个write那你这个database有很多地方需要优化的地方是吧?比如说我们在这个需要加我们之前说过这个database是transactional,看起来更像一个transactional database是吧?你需要set和get非常响亮的record那你这个database需要一个非常快的identify你的record 是吧?假设你这个database一秒钟靠一个million time那你一秒钟就要append一个million row在上面那你怎么样能从一个million row里面飞快的找进一个key呢是吧,如果你是用这个Database的话,你就是Linear去scan了,然后这个效率非常低。其次的话是,如果这个Key不存在这个Database里面,这个KeyValue不存在这个Database里面,你要把整个File全部search一遍。这个就是直接就ON了是吧,并且这个K不存在的概率是极高的,你直接search一遍就ON上去了。所以这个tradeoff首先我们需要一个index是吧,这个k在哪儿,然后它在什么地方,那我们需要一个index,那这样index的话就可以把这个sickTime呢,从on变成oe,technically其实是olog,但这个log其实非常小了,所以就可以认为是on到oe的这个样子。然后但是我们加index的时候,其实你就写了两遍,一遍是你data实际在的地方,另一遍是你index在的地方,就是我们叫rate amplification你看看,amplification就从一中到二然后就是一点,然后index呢,其次呢你需要这个database administration和developer非常carefully 出上这个 index根据你这个访问的模式,Access Pattern, System Design里面,Access Pattern是非常非常重要的一件事。就是特别在Mock Interview的时候,你一定要问,就是当你觉得他那个Use Pattern不是很熟悉的时候,你就一定要问一下你的面试官就是你的access pattern是什么然后当你设计的时候,你要想一下这个Access Pattern是什么,这个Access Pattern无非就是几项嘛,就是你的read是多少,你的read-read ratio是多少,然后你这个RAID的话是以什么方式来RAID?你比如说你是通过人名来RAID呢?你是通过ID来RAID呢?还是通过什么来RAID?然后你write的时候是怎么样write 是吧你在 write 里面哪一些 case uniques 的需要考虑一下所以这个access pattern是非常非常重要的一件事,因为你的access pattern不同的话导致你的设计会完全不同。比如说我们前两天在群里面讨论的这个100个file,100个gb的file,如果你这个read pattern是append的话,那你有多种方式优化,是吧?你这个file只会递增,是吧?你之前的file可能都不需要改。都不需要去来回反复的copy但你每次如果100个JFiles重新generate的话重新generate的话,那就看怎么样重新generate它,如果每次generate只改其中一小部分的话,那你还是可以把它break down,已有的不变的部分可以重复利用是吧,然后但是变的部分你可能需要把它version一下,然后point到不同的新的这个file block上是吧,但是不变的部分可以重复利用,所以你这个access pendant是非常会决定你的design的这个模式的,然后这个它不仅是影响就是你这个作为一个high level 就是这个architecture 的design模式,它也非常影响这个非常影响作为Application Developer的时候,你要怎么设计这个index也很重要。设计这个Access Python非常重要。然后这块的话,index有一个叫Multi-Field Index,Multifield index是什么呢?比如说我举一个例子,比如说你是做一个不好的例子,不好的第三个例子是什么呢?比如说你现在是YAP,然后你index的时候,index latitude和longitude然后 latitude 和 longitude分别作为field存起来,然后当你search的时候,当你search说我要search这个在latitude和lentitude的多少之间,多少一个rectongle之间的时候,你就search latitude要大于多少小于多少,lentitude大于多少小于多少。这个其实是比较不好的例子为什么呢 [10:00] 所以当你search的时候我举个例子 你这个当你look up 这个 restaurant 的时候你比如说它Leditle的是125度和126度之间,你其实在Database里面选出了所有125到126之间所有的restaurant,在restaurant可能有上半家,你比如说这个,就说纬度吧,你比如说这个,呃,San Francisco纬度可能和东北差不多是吧,就是说你当你选San Francisco restaurant的时候,你说它这个纬度在125,36到37之间,你可能就选到了北京的 restaurant也选上了,然后这个东北那块比如说长春啊那个restaurant也显上了是吧,然后这样的话这个performance很糟糕应该是index是精确到一个或几个record你这样的performance很糟糕所以当你做MultiField Index的时候,你需要去额外的优化。像这种情况下,Latitude,Lentitude,你可以有两种方法,一种是GeoHash。最后开始就把这个LightedG和Longer编在一起,就变成一个Single Dimension的东西,然后你可以做近似search。还有一个的话,就是它有专门的一个algorithm叫RTree,这个是PostQuest的支持,PostQuest的支持一个叫RTree的东西它这个效率也很高它是search一个Rectangle的trade,它是根据Rectangle 3来search,效率也很高然后对是这样子的,然后另一个MultiField的index是什么呢?就是当你有两个field子,然后你这个field子,这index lookup的时候是第一个index,它比较那个cardinality,就是它那个值比较多比如说是City你City的话美国可能600-700个state是吧,如果是按content的话,可能有几千个content是吧,然后另一个是state那你首先index应该是那个Cardinality 比较高的那个,就是现在Counted来Index,因为这样的话你的那个Performance会比较好。如果你按State来Index的话,你只有50,所以你这个B-TRAID会变得很高,你B-TRAID,Multifield的index会变得很高,那它的performance也是不太好。所以这个index,这块讲了一些小的知识,index是比较要非常注重细节的,就是这个index非常注重细节,它会很大的影响在performance。所以你这个需要index的时候需要反复琢磨一下甚至是要做一些实验但总体来说你要multifield index的时候你先index in your cardinality 比较高的那个field好,我们这块呢,就是刚才那个DB,就是这个两行的database,我们稍微更改一下。让它performance更高一点是吧我们把这个database变成什么呢?变成一个in-memory的hashmap在一个log structure file 在 disk上的log structure file也就是说当你有一个新的record的时候,你在memory里面先把那个file写到disk上,比如说你先来一个,比如说举个例子就是62指向了Vancouver是吧,你62指向了Vancouver,那你就是先把Vancouver record 写到disk上写到disk上以后就直接append到disk上,当你append成功的时候,然后再把62在指向这个byte offset 写到这个in-memory hashmap上然后你这个record就写成了然后比如说你这块有个其他example,比如说你这个42San Francisco update 了,42%不只像San Francisco,42%只像New York City 是吧?同样的把New York City append到Vancouver之后是吧,然后这个Cisha就指向了新的offset就是到200,就到200多的offset,就不是64了,那你64这个就就没有人指向它了,就可以被回收了。这个PyT是什么呢?所有的Write是sequential的,你sequentialWrite的performance会好很多。然后这个的话,还有几项注意的是,它这个FileFormat是csv-like format。然后他说白了就是两部分,一个是in-memory,hash-map,一个是file-format,是对刚才的那个四行的database的一个优化然后这种情况下当你对一个值进行update的时候,当你比如说42从San Francisco直向New York City的时候,你这个San Francisco这个record是完全没有用的。是完全没有用的,然后这个database,其实这个database还是非常有好处的,database好处是什么呢?就是我们讲YouTube的时候有个YouTube Viewer,是吧?就是你这个YouTube有多少个访问量?这个里面K就可以变成YouTube的resourceresource地址,比如说你这个resource是我上传了一个YouTube视频,那这个key就是我的YouTube ID,YouTube video ID,然后这个value呢可以是看了多少数量所以这个看综合树像它一旦被更新了以后像这种情况下,一旦被更新了以后,比如说这个PER被看了一次从2103变成2104,那2103这个值就没有意义了就没有意义了,但是它一旦被更新以后 [15:00] 比如说后面的话最后更新到2214,那所有之前这个PURS的这个值都没有意义了。所以你可以做这个,在你这个Data File就可以做这个Merge,当你Merge的时候可以把所有的旧值E-RASE掉,然后只留下最新的值。那你这两个file merge了以后就变成了一个非常小的只有四个record的一个file这是它一个merge的过程并且你可以多个files in merge,因为它这个,你比如说你可以思考一下一个video,YouTube video,它有上百万的访问量,也就说明什么呢?这个假设我上传一个video,假设有一个million的访问量,有一个million的duplicate record,之前99999个都是从佛罗上流最后一个就可以了,所以它这个compaction的时候,compaction的时候它这个回收率是很高的,可以接受很多空间那我们就是说我们把这个六行的database,刚才的四行的database转化成了这个相对比较复杂的一个in-memory的hashmap和一个on disk了 on disk了 fell fell一个巨大的file 其实是一种优化了有什么问题呢 我们还可以怎么优化呢首先这个fileformat CSV不是一个很好的format如果你用 Binary Format 的话,可能会更快一点,你可能做一些 Compress然后可能更快一点其次的话就是你delete record的时候会比较复杂你delete的时候,你比如说当你delete一个k的时候,你不管这个k加什么,比如说你这个看的YouTube数量,你不管加个什么数值,它都不是valid的,你应该说这个YouTube就不是零个访问量,它是NOW的访问量是吧,这个NOW就是一个非常special的一个corrector,它不是任何一个数字,那你可能需要一个tombstone,就是你有个special character,你可以定一个special character叫tombstone然后这个 Tombstone就表示这个 record 是被deleted然后如果真的想把它做成一个database的话这个其实就是Lock Structure Database,Lock Structure Merge Tree Database,如果想把它做成Lock Structure Merge Base的话,你还需要Recover是吧?当你比如说这个Database restart的时候,那你的In-Memory的HashMap就全部丢失了,你需要有一个Recovery Mechanism,这样的话你的Database没有Data Loss。然后其次的话,另一种情况下就是当你写入这个Database的时候,当你写入这个BSS的时候,你可能写了一半的时候,像我们刚才的例子,如果我们处理不小心的话,你可能是先写上去说83指向New York City,是吧?但是你这个83,in memory那块写完了,在那个disk上的New York City没写完,那你就cropped data,是吧?就是partial written records,那你这种情况下的话,你需要处理它,是吧?所以这个有一些成熟的这个系统,比如说你可以用bit cask,BitCast的File,你可以有checksum,然后这样的话,你就是当你有一部分logcropped的时候,你的system可以detected,然后ignose一部分,就是你就return这个database internal error,是吧,你就这个,你这个data确实loss了,你没办法recover了,你就可以用这个checksum说这个data已经loss了,没办法recover了,你这样的话,你return一个exception,而不是说return一个wrown records,所以database的值,你永远只有两种结果,一种是return correct result,一种就是return correct result,一种就是说,就是 throw exception 对吧 你不能 return 一个 wrong answer最后一点就是Concurrency Control, database 最重要的一点就是我们之后大概一个月后吧,会讲到 concurrency control,这 concurrency control也是database相对比较最难的一点,有很多种algorithm。比如说你这种情况下,你有多个request同时进来的时候,你有多个request同事进来的时候,你最后写的结果不能有两个request冲突了,两个write冲突了,这个写了一半,那个写了一半,两个request,比如说你不管是42还是83,两个k指向的都是同一个地址,然后这个地址一半是San Francisco,一半是New York City,那肯定就出现conflict了是吧?就出现crafted result,不应该出现这种结果。Database的最强的,strongest concurrency control,是所有的rights在写进Database的时候,它写的时候,ICF是sequential写的。就是说白了,其实多个人同时想进入这个Database这个门。多个人同时想在这个 database 里面写东西然后你因为这个门一次就是你通过这个设计是吧一个店一个咖啡店里面多个人同时想进入咖啡店你通过这个设计然后导致同时想进的人排成一个队一个一个进去,那就是database concurrency control 里面最强的一种 concurrency control 了。就是concurrent write as if executed sequentially然后这个Database如果想把它变成一个Commercial database,真的能使用的Database的话,你还要加这些东西。然后这个里面其实concurrency control,就刚才我们上面讲的concurrency control,其实相对比较好处理的。为什么呢?因为它所有的血都是就是他这个写的都是immutable的,就是你可以把它设计变成appended only的,这样的话其实 [20:00] Concurrency Control 比较简单,Btrade Concurrency Control 会复杂很多,你想一下,你其实这个写的时候,你是对production record进行了修改,所以你不能直接在里面写,你直接在这个DTrain里面写的话,你直接在Btrain里面写的话,你如果写了一半突然停电了,那你就有 corrupted,就是 partial written records 是吧这个就在Btray里面就crafted了然后其次的话两个人同时写的时候你有可能就是一部分是A写的一部分是B写的也会有麻烦所以这个Btray concurrency control和这个rate right呢其实是有额外处理的,但是这个问题不在这个我们看到这个Lock Structure Merge Trades中存现,因为它这个就是append,就是一个简单的append好我们这个Database其实分三步,这个LockStructure Merge Tray其实已经快结束了,快设计完了,非常简单一个东西开始的时候是四行DataBase,然后变成了一个in-memory的HashMap,加一个on-disk的Filesystem然后再加上一些Compression,然后再加一些Delete record,然后加一些Quest Recovery加一些partial written record detection,加一些 concurrency control,然后它就可以变成一个log structure merge tree了。这个就是用在Cassandra,LevelDB,RockDB和HBase的,它是有很多额外的用处,比如说这个和这个Time Series Database是很像的,Time Series Database它不是用Kit,它是用Time Series to merge的也是类似的结构,是Time Series已经merge,Time Seriesmerge trade最近有国内有个database叫TaoDB,也是做这个Time Seriesmerge trade,就是Time Series database的然后Lucine就是我们之前谈论的这个Elasticsearch底下那个database engine,它也是TaxSearch的Engine,它也是用这个LockStretcherModernetray的相似的解法,但是它中间相比更复杂一点,它是用try来做这个index的,它不是用hashmap做index,相对比较复杂这个Design也是跟B-Tray相比呢也是非常简单的,比B-Tray要简单很多,然后它也更快一些,它其实比B-Tray写起来,因为它是sequential写的,B-Tray的话你还需要去lookup record,然后再写,你写的时候其实非常fragmented,这块写下那块写下,但是这个lock structure,merge trade都是sequential写的,所以它效率会快很多。这个lockstructuremerge trade刚才那个还是不够的,我们还是要做一些额外的优化。什么额外的优化呢?我们注意到刚才那个说其实所有的record呢所有的Record呢是必须能在in memory放下的如果你这个K数量比较少的时候还是亏但你K数量很多的时候怎么办?比如说你所有的YouTube URL这个数量已经相对来说比某些UseCase的K数量少很多但你YouTube的数量还是很多的我们之前记得比如说每秒钟250个上传吗?这个数量还是挺多的你的K数量还是很大当你这个K数量超过你memory能放下的数量的时候这个database不能用了是吧你就不停的可能有page swap是吧这个效率就很低了你现在得不停的把memory data换到disk的配置上,然后不停的换几个,这效率就很低了,是吧?你如果disable page swap,可能就直接crush掉了,是吧?所以我们必须做一些什么优化呢?一个优化就是说你不需要把所有的K放上去像这种情况下的时候,你只要间接性的放K就可以了。你比如说,你要找一个hand puffs,那你肯定是在hand bag之后,在handsome之前,这个是那个lex order,你肯定是在handbag之后,在这个handsome之前,你只要选一些select一部分k作为index就可以了那这样的话当你找的时候你这个效率就很多你不需要把所有k放到inmemory里面你就很快的找见他最近的一个最近的之前的那个就可以了然后这个lookup也是可以很高效的,因为反正它是tree lookup,就是logn也是可以很高效的。然后这是一点,然后其次的话,比如说你另一点可以优化是什么呢?就是你这个record 你有handbag, handcuff, handful,整个record是很多个KValue的一个小的section这个小个section叫block的话你可以compress它是吧你可以把这个data再compress一下你在把data传到disk的时候,complex一下的时候,你的效率也很高,因为你complex了以后,首先你in memory能放更多data,你disk上同等的空间也能放更多的data其次的话对 你就可以放更多 data 毕竟database只要不是in-memory database,它大部分时间都是在那个,它那个时间都是在那个disk上,就是写到这个filesystem,写到disk上这个时间是远远藏于远远藏于任何其他时间,decompress,compress这个时间 [25:00] compress decompress有一个那个我花10秒钟时间给大家普及一下一个知识,您可以不知道,就是CPUCash,然后 memory然后有一个图,还有一个disk,然后timecomparationCompare ratio,本来想加的,忘了我看一下有没有想法。就这个图就这个图这个图是一个非常直观的图,就是在不同的地方,时间差多少。比如说你在CPU register 里面进行计算的时候,你可以认为就是类比的话就是在你大脑进行计算,或者是你要取东西的话就是在大脑中取,就很快。当你在这个chip cache上,它有L1,L2,各种cache是吧,就L1,L2,L3 cache好像还有。你在这个L1的cache的时候,就跟CPU绑定的这个cache的时候,你就是将来在这个room里面取。如果你在这个比较这个L2和L3开始,就在这个BOD上就开始的时候,有点像在这个Hotel去,这个都很快,就是当你取个Record。但是如果你在Memory去的话,这个就相当于是你从这到,从这到那个Sacramento了,就是到Sacramento了,因为你这1.5个小时嘛,最比的话1.5个小时,就相当于是你就不在这个Hotel去了,不在你住的Hotel,你要去Sacramento去了。你跑到这个这个两年时间,两年时间到disk取就两年时间,现在没有人用这个tip了是吧,但是你去disk取现在两年时间,我也不知道两年能跑到什么地方呢,他这块写了一个Pluto,是吧,冥王星。Pluto迷惘星,跑到迷惘星起来,这个时间就很长了。所以可以看到这里面,其实到memory这块,如果用register作为一分钟来取这个data的话,到memory这块就相当于到Sepremental一个小时半还是可以接受的,但到Disk的话就两年,所以可以看到大部分Database,如果你是Durable Database的话,Durable, Guaranteed Durability的话,你肯定要把Data写到这个Disk上,所以你这个Disk永远是Database Performance的这个Portal Lake。好好,就是普及一个简单的概念谢谢大家好我们接着看那个LogStrux Merge Tree 啊当你看到LogStrux Merge Tree的时候有一个Write进来的时候实际上你就是把它加到InMemory Balance Treein memory balance tree你可以用 red black tree也可以用那个一位要去这个tree,就是它是一个balance tree,然后这个时候,这个tree有时候被靠着mem table,它的存储是guarantee worst case,是ologn的,所以它这个performance还是很快的当你这个 mem table 比这个 certain threshold 的大的时候它一般设置几个MB,这个可能还是要unpractically看怎么样结果最好,你就把它写到disk上,然后变成一个ss table file。我看到有人说话有问题问吗好,那我们就接着说,就变成一个ss table file,这个效率还是很高的,因为你在这个ss table里面,就是 sorted,SortedStringTable 在这个SSTable里面,你所有的这个KValue还是SortbackK的,然后你的这个新的SortedString Table是连续的,比如说你开始写,假设我们举一个极端的情况,你可以是从1到1万的。那你开始写的时候1到100可能是第一个block然后100到200是第二个block然后你最新写的9000到10000可能是最后一个block所以你最新写的是在memory上的是在memory上的,所以你最新写的most recently write,同时也是最有可能被lookup的,所以这个lookup pattern如果是你刚写了以后就要读,read after you write的话,那你其实大部分读都是从这个memory里面读的,然后你读比如说你是一到一半的,然后你开始读5000,那5000的话你可能得回去找几个block才能读到,你要读一,你可能得回去找到最新最旧的block才能读到,那你如果读0,这个0从来没有写过的话,你要把所有的block全部lookup一遍才能找见,那你这个performance就很糟糕了,我们提后面有一个优化,来怎么优化它,其次的话就是就是读的时候就是从最新到最旧读,一般来说这个写的时候都是就是写和读,拍本的时候刚写了以后读嘛,这个就是比如说常见的几个,你可以想一下常见的几个YouTube啊这种Use Case是吧,或者是Twitter啊这种,一般最新的Data也是最hot的Data,然后最旧Data一般也没人看。好,然后在background的时候就是你需要有个compaction process,不停的摆一下 [30:00] 这非常旧的这个这个file不停的把非常旧的file就是sustream tablefile come back起来因为比如说你如果是video的那个lookup的话,你其实这个compression rate可以很高是吧,你要有一个非常popular video,你compression rate可以就是一个million直接到1是吧这样的话就是你这个data就是可以compress一下然后它这个compassion有多种compassion方法它有一种是size tiersize tier还有一个level compaction这个不讲太多因为其实这个size tier我理解这个level compaction我也没看它的细节size tier比较简单就是什么呢比如说举个例子在SDR 比较简单就是你比如说你超过一年以上的data就举个例子,超过一年以上的data全部compact成一个大的file然后一年到六个月的data,一年到六个月就有datacompact成一个file,然后六个月之内的data,六个月到什么上一周datacompact成一个file,然后上一周的datacompact成一个file,然后最后是in-memorydata,这样的话你其实就是四层。四层是吧,当你要找一年旧以上的data的话,你就去最下面这个file,一年以上旧的data,你要去找最新的data就在inmemory,就是几层。这个Tier也是可以configure的,然后这个compaction更多可能是根据这个这个大小是吧,你可以根据这个大小Dynamically Comprise 几个Tier然后这个话最后还有一个问题是,如果你这个Kit不在这个Data里面怎么办,那你就要做Bloom Filter了。继续时间关系我就不讲bloom filter了你可以认为是Bloom filter 就是有一个 non-bunny就是能帮你排除一定不在里面的,比如说你要找这个1到1万有一个KV的一个stop,你要找0,0一定不在里面,当它返回一定不在的时候,就是bloom filter很快的返回,它可能在不在,他说一定不在的时候你就可以说这个可以不存在让他返回可能在的时候你还要去去查一下它站不站这个其实其实道理非常简单大家search一下这个bloom filter就行了这样的话可以就是Reduce Lookup Non-Existed Kit的 performance因为如果这个Kid不存在然后这个Bloom Filter又是个False Positive的话,你需要Look up所有的Tears,这个Performance是最糟糕的。这个LogStructureMerge也讲完了 然后大家有什么问题吗谢谢大家有什么问题吗? sorry好谢谢大家请不吝点赞 订阅 转发 打赏支持明镜与点点栏目我想问一个问题怎么保证那个MAM table不丢失 crash withdrawal哦这个有一些细节东西啊这MemTable怎么不丢失呢你就是在写memotable的时候,你也写到一个writeahatlog里面,这是一种方式。也就是说当你一个request进来的时候,你不仅在log里面写好,在log里面已经committed了,就是flash掉了,然后mem table再写好,然后你再返回。谢谢大家这样的话是不丢失的,因为你这个MEM table其实也在disk上有一个,就是说白了在MEM table在disk上有一个duplication,如果你crush掉,你可以从disk上读去最新的MEM table。谢谢大家然后重建这个MEM table解决回答你问题吗,它这个设计和这个Btrade的Radiahide log是一样的,就是Btrade有个Radiahide log也是同样的问题。谢谢大家谢谢大家谢谢大家谢谢大家我看到有些chatTraditional database都用这个log structure mergership,Traditional database用btree,这个log structure mergership是非常新的一个东西啊它实际上可能就十几年的历史我也忘了最早的paper什么时候写的,可能是十几年历史,大规模使用就十几年历史,是从2010年以后才使用的。这个是非常新的一个东西这个它有好多自己的好处了,我们稍后会compare它的advantage和disadvantage,但是这个是非常新的一个东西。好,我们看Btrade。B-Trait,B-Trait的话就是我觉得大部分上个Database还是有点这个概念的是吧?B-Trait就是说白了就是你把所有的Key说把所有的key然后那个按大小抬下去,比如这种情况下你的Key在100到200之间,你可能要去这个这个block里面找 是吧然后你如果是在200到300之间你可能要这个之间找如果你在什么250到250到270之间你要去这个区域里面找B-Trait是说白了就是一个非常非常flat的Trait嗯一般来说 [35:00] 接着我给了一个数据,我们可以看一眼,我给了一个数据。一般来说,假设你一个page 是hundred reference 的话,你四个level 的 b-tray 是给支持250t 的 data 的所以一般来说的B-Tree其实就是三个level到四个level之间,很少到四个level基本上不可以支持4个level以上的,所以当你lookup key的时候,你可能就是走三次就可以早见了比如说你从这到这到这就早见了最多再下面再加一层,再加一层就250个T了,所以当你想到Btray的时候可以认为是非常flattened的Tray,然后B+Tray还有一些额外的优化,比如说这个里面你这个100到130之间,比如说我们举个例子,举个例子这个里面,你就不需要列出所有的这个值全部了,比如说就是,250几到226你只要列出它那个不一样的地方就可以了是吧你比如说你在250的时候你就去这儿你要是255的时候就去255你只要列出不一样的地方就可以了你还是可以额外的接上一些空间但是总体来说B-Tree就是一个非常非常flat的Tree然后这时候呢就是你如果你只lookup的话这个B-Tree还是挺好用的是吧您只是Lookup只是read这个B3很好用就是最多lookup三层这个非常快就早见了但是你写的时候就比较复杂了你Btrade写的时候比较复杂了比如说这种情况下你这个block里面这个page里面你实际上它只能支持这块为了demonstration它只能支持5个record当你再写一个record的时候它就写不下了是吧那你就必须对这个page进行split了这种情况下的话你就把这个page分成两个balance分成两个,因为它是五个,加一的话六个,所以每个page有三个是吧?然后前面的话是从333到335,后面的话是从337到342分成两个以后你要把它的parent也更改把 parent 也要把新的这个,就是这个 key 加上去,就是你这个 B-Trait 的这个,这个第一个可以加上去这样的话就是parent也更改过了这样改完了以后呢你才能算写进去注意到这个更改呢, again,你是不能直接在里面更改的是吧,直接在里面更改,万一写了一半的时候,突然断电了怎么办,就half written record有多种写的方式啊,一种方式就是有多种保证你这个Half Written Record不会出现问题的方式,一种写的方式就是你写一个Write Ahead Log就是rata highlog就说白了是一个log就比如说你这种情况下就说我把333我这几个337我在这个337加了一个334是吧然后做这个operation然后在上面改当你出现croption的时候当你出现corruption的时候你再去就是说这个 data 我进行这个操作的时候 这个transaction的时候出现问题了我把这个cracket data再修复 这是可以用redheadlog进行修复 另一种写呢就是叫Copy on write,什么意思呢?就是说,当你在这个进行操作的时候,这个Btree这两个配置进行操作的时候,你不在这个上面进行操作。你把它copy一下就是上面这个copy一下然后写上这个新的k下面这个copy一下也写上新的k所以你其实是Copy and Write 其实是什么呢?就Copy了三个Pagecopy了三个page然后把它modify好然后就modify好了,然后把上面之前指向这个旧的这个配置的 pointer 指向新的 pointer那就可以了就是量重方式,Copy on write更好,其实思考一下Copy on write更好实现一下,为什么呢?你把这个Copy完是吧?把这个parent和child的copy完,然后把child的分拆开,然后把它modify好,把parent的分拆开,modify好。然后你把新的partner指向他,那这样的话你是seamless的进行这个 write,就是中间没有一个crafted state。如果你用 write ahead log 的话,你可能需要一些修复嘛,就比如说你只要 partial,partial write的话你还得看,我这个write ahead log,log1写完了吗?写进去的话,log2写完了吗?log3写完了吗?如果log3那儿crafted的话,你可能还得再recover,所以相对可能辅来一点,countercase比较多一点,copy on write相对比较新一点。好好好好所以这话呢,第一点就是你要加个WriteHeadLog,就是为了保证你这个Data是Durable,没有CraftedData然后这个Return High Log也是在那个Log Structure Merge 里面也有作为一个优化,就是也是Garantee Durability 一部分其次的话 Btrade 只辞到 Partial key就到那个partial key,然后找不一样的地方去下一个 key这个是给你其中另一个用好再其次的话这个Btree还有个什么问题呢?Btree有一个问题是什么呢?就是你这个Pay [40:00] 可能是可以在disk上任何一部分的,如果我看之后有没有时间能讲一下整个这个database这个,整个这个sql database这个,就是从最上面一层到最下面一层,它中间是很复杂的。它这个file management也是很复杂的一部分,是吧,这个file和page management也是很复杂的一部分,所以这个tick可能是连续的。就是你的从那个logical角度,那个cache联系的,比如说是从从Hansom到Hankoff是吧你Cache联系的但是你Page可能是一个天南一个海北才能非常分散一点当你要scan through logic partial,就是当你scan through 汉的开头的时候,你可能就一个天南一个海北的早,效率就很低了,但在lock structure merge tree 里面,就相对比较密集一点,就比较早的时候,你lookup的时候就这个 data不需要去太多地方,scan的时候就比较好早见好,然后最后一点的话是有些额外的优化,比如说你这个里面你可以把所有的chow的page连起来比如说 Shell Page 连接就是一个比如说两-way link, please.2-way linked list,那种情况下你比如说你要就是scan through 的时候,比如333,334,335,336,336找的时候,你就直接从这个配置到下一个配置找就可以了。你这样的话就不需要再lookup一遍了,就是变成一个2-way linked list 的优化,额外的小的优化。然后请问为什么337出现了两次在哪里出现两次呢上面这个是告诉你去哪儿lookup的就是上面这个是它是一个reference到一个file的就是说你到了337你就知道这个337到345去这个file找下面这个是它是一个带value的你可以这么想,它所有的KValue全部在Leaf上它所有的key value全部在leaf上,然后它不是leaf的node,其实是全部是作为index来存在的。就比如说你lookup的时候你要找337,它不是leaf,它就是一个指引,指引到你的那个利服上对 B+Tray 和 B-Tray 还有一点不一样是 我忘了哪一个是哪一个了 就是有一个Tray 是可以把Value存在这个呃存在这个就是这个free leaf 的这个node上的我记得可能是Btree可以存在非leaf的node上的B+tree应该是所有的value要存在这个leaf上的有一点不同,如果你不找Grabbase,没必要好然后我们接着看,对比一下LockStrucureMergeTray和BTray不同的话,LockStrucureMergeTray是SequentialWrite,所以它会更快一点。然后它那个throughput更高一点,因为是sequential write,你sequential write,一般来说sequential write是你random write的加倍6到10倍,快一个数量级,所以你肯定log structure 更快一点好其次的话它是个Tiered Storage,你最新写的词,你读起来更快一点但是Btrade就不是了,Btrade的话谢谢大家B-Trade虽然也有一些优化,但是它不完全满足最新鞋的值。lookup更快一点,因为Btray也是相当于是在inMemory里面也是一种开始的存在,所以它可能最新写的也很快,但是当你读不是在Memory能handle以外的话,这个Btray效果是比logstructure,meritray要稍微差一点的。其次的话这个Lockstrash Merge Tray Compress 更好一点你所有的data log 当你做 compression 的时候你基本上是没有fragmentation的你基本上把所有的record compress好,基本上很少有fragmentation的但我们看这个B+Tree,你很多时候可能有超过就是小于一半,但是你可能刚好一半的,worst case,你可能有一半左右的fragmentation,就是说什么呢,就是一半的storage,是spare space,从来没有用到过。然后最后的话这个lockstructure merchant的write amplification是比较小的当你进行B trade的时候当你写了B-TRAID的时候你的Rate amplification会比较多,因为你还要写额外的一些index啊什么的。但是它这个LockStruxMertraID呢,它会把那个SoughtStringFile呢,不停的compress它。不停的去compact它,所以比较小,并且我们思考一下这个这个这个Btray 当你写Btray的时候,如果你是copy on write的话,你实际上整个这部分全部要copy一遍整个这部分全部要copy 上就是pages split 整个这部分全部 [45:00] 我把我拍一下所以这个Armortize 的时候是OE 的,但是你如果只是看这块的话,你其实这个是你只写这个operation的话,其实是三个配置数量三个配置数量,一个配置上可以写很多record,一个配置很大的嗯配置几十k,几十k,一百k,就可能,我忘了具体最大段,非常早的时候教科创可能写的是8k,但是那是非常老的概念,可能现在是一百来k,好然后但是这个 Log Structure Merge Trainer有一个问题,它downside是什么呢?包括这块杨阳也提出来,就是当你要找一个tubular的record会非常慢,所以你需要去找最底下那层。但是这个也是一个optimize,就是比如说你optimize的它就三个tier,其实你最多找三层,那和这个Btrade是一样的,Btrade就是找三四层,你optimize的三个tier。其实也没有说明显要慢很多,但是Lock Structure Merge Tray里面明显的一个当下的是,你有一个Background Compact Process,如果这个Background Compact Process你没有Configure好的话,它可能会run的非常aggressive那你这样的话你就会和 ongoing 的这个 real-time 的 read 和 write 增强资源那你会影响 real-time 的 ongoing 的 read 和 write也就相当于是跟那个就是正常的request 就是增强资源,那你这样的话,因为Btray不需要做Compression,它不需要有这个background process,所以Btray的performance是比较predictable,但是你这个lockstructure merge trade呢,当你background process你configure没configure好的时候,你没有优化好的时候,你就比较less predictable than Btray,你可能就是有些时候写的时候,非常非常快,有些时候写的时候,你要跟compact process的强资源就很慢,好还有最后一点的话就是这个log structure merge train 呢其实你一个case可以存在多个地方特别是你update很多次的话你要存在多个地方你其实会增加很多complexity你会增加很多complexity,特别是当你做transaction的时候,你的complexity会比较高一点。因为做transaction的时候,你需要很多key一起update,所以这个logstruction merge trade总体来说transaction cost会高一点复杂度会高一点好好,这块就讲完了,有什么就是,就是一方面是lockstress,trimer,trade,一方面是btrade,这两个简单的comparation,看什么额外的想法或者是question吗?谢谢大家谢谢大家感谢观看那我们就接着看index好,index的话,我之前讲那个就是之前讨论这个system design的时候,在Mock-Infuel的时候讲了很多次,就是global secondary index和local secondary index,这个主要是针对,很多时候是针对Denimal讲的。这个index的话,secondary index的话也是非常常见的用一个概念,就是什么叫local secondary index?local secondary index就是您可以认为想像一个single node,是吧?single node,然后你把这个index写到一个地方。5,9,是来个DFA就是 local 的一个 secondary index但是如果你比如说在 Dynamo 里面,你所有的 data 实际上是写了上千个 node 里面,就是 data 是partition 上千个node里面当你去lookup这个index的时候比如说这个index 我举个例子是city好了你这个这个整个record是按user id 进行partition的所以你每个partition里面是有这个City是非常diverse的是吧,你比如说在San Francisco这个City里面,你这个partition,12345678可能都有这个San Francisco这个这个这个这个records,这个City是San Francisco是吧,如果你是local的话,你就只在那个partition里面进行deck,如果你是global的话,就是说所有的San Francisco的这个records,你在一个地方,在一个consolidated的地方,在同一个地方,你都有这个同一个地方你都有一个这个就是index 比如说你当你lookup San Francisco的时候你就知道它在partition1的第15个record有 是吧 在partition2的第16个record有 在partition3,partition1000都有这个地方 是吧就是你把它consolid在一起,放到一起,但是这个Global Secondary Index本身也可能会被partition是吧,因为你用Global Secondary Index本身太大的话也需要被partition,这就是另一种就是需要把它scale出去的一个实践了,你比如说你要是举个极端例子,比如说你有10万个node存一个非常大的一个database的话,你Global Secondary Index可能需要有3-4个node去存是吧,但这样的话San Francisco,你才知道San Francisco在哪些地方全部出现过,然后这样子所以这个就是DynamoDB里面选Global secondary index local [50:00] 是有非常大的Performance difference的我们到时候会我们到时候会讲一下就是会讲一下这个performance有什么不同现在粗略讲一下的话就是如果你用Local secondary index的话,你write会很快。write很快,比如说你新加的一个record是指向San Francisco的你到partition50了你只要更新partition50的index就可以了你write it就是你的 record 和这个 index 只要 write 一个 partition 就可以了但你 look up 你需要 found lookup 比如说你要找所有的在 San Francisco 的 record你需要把所有的 partition全部search一遍,然后在所有的partition里面去猜的local secondary index全部search一遍,然后它能找回所有的record去在San Francisco的Record所以你用 local secondary index 的话你用local secondary index的话,你write很快,在你read的时候,你要翻到所有的partition上这个ray的performance会比较糟糕然后如果你用 global secondary index 的话你比如说你还是在partition50上加了一个San Francisco的record在Parisition 50加上San Francisco record你San Francisco要去个global的地方去把它index一下所以说你这会儿update的时候,你其实update不是一个partition,你不讲update partition 物试,你可能还要update一个index partition把它update进去,这样你要update多个地方。因为你这个只是一个index,你可能有多个index,比如像denomodb是,我记得是最多limited的5个secondary index,所以当你写一个partition的时候,如果DynamoDB有5个index的话,你可能需要最多写6个partition,是吧?每个index在不同的partition上,你可能得写6个partition的record然后写进去 但是这个Global Secondary Index lookup很快比如说你要找San Francisco 你去那个Global Secondary Index partition一找然后就找见所有的San Francisco在哪一个partition 第几个record就是Look up很快所以这是一个tradeoff,这是一个很明显的tradeoff。你如果用DenemoDB或者这种Cassandra的话,你需要去思考一下,就是你希望更快一点呢?写的时候更快一点呢?还是希望读的时候更快一点?是吧?也盼着你的这个access pattern。谢谢大家 谢谢大家然后这是 Global Secondary Index和 Local Secondary Index, 还有其次的话是Clustering Index, Covered Index和 Only Reference Index这个也是比较复杂的一部分这个的话一般更多指的是B-Trait这种Btrade这块的话,我们可以我们往回看一下,BCE往回看一眼。你看这种情况下你就是这块比较简单就是一个k一个value,这个value可能是一个非常小的value能直接写到这个配置上的,比如说是个integer12345这种可以直接写到这个配置上的也可能是什么呢,也可能是一个pointer,pointer到一个file的就是pointer到一个file system上,比如说你这个record比较大一点是吧,并且这个record长短不一的时候,你可能就pointer到这个Pyter的一个Page 就是DiskPage上然后这个Pyter也非常简单就是你给一个Page的这个index你给一个第几个page 然后给一个offset然后就能找见这个record了 到时候它上面会写长度是多少所以这种就叫 Only Reference IndexOnly reference index, only reference index就是你这个index直接是他那个pager的,pager和offset的,就only reference,然后这个是我记得有人说是在用在 Postgres 上的,我不是很确定啊,可能是用在 Postgres 上的,但我知道 Cluster Index 是用在 MySQL 上的,依然是在依然的就是说在Memory里面,这个Index是直接和Record在一起的,绑定在一起的。是什么意思呢?比如说当你look up 一个 record 的时候,person record 的时候,它的 primary key 和它所有的 field 绑定在一起,然后放到 memory 里面。它的 primary key 和所有的 field 绑定在一起,放到 memory 里面。如果你是从另一个index找见它的话,从另一个index找见它,它的index会指向它的primaryKit的这个地方所以你所有的 modification 其实全部在 InMemory 里面做的你不管是从PrimaryKit进行Modify,还是从其他的IndexModify,你实际上全部在Member里面做的用memory做完,然后它可能要flush到 disk上,然后guaranteed durability,但是你全部放在一起的,就是它的index和它的row是整个打包放在一起的,叫cluster的index。所以在这种情况下,MySQL的ClusterIndex的SecondaryIndex是只向cluster的index的,然后他们中间有一种叫covered index,这是一种折中化的优化了,covered index是什么呢?就是你需要configure,但你只对其中的一部分field放到 in-memory [55:00] 就是对你经常update的这个field放在inMemory里面经常读去update的read和update的field放到index里面然后其他的field是放到这个disk上的你需要reference到disk上然后这是一个折衷的方法就是一种是全部放在disk上only reference index就是全部放到disk上就是你这个index只向的是disk上的一个page一种是全部放在memory上就是index和这个fieldbundle在一起还有一种是折衷的这个也是比较复杂的也是一种优化,它也是为了optimize read 和 write 的 performance,还有 index 的 lookup performance。然后还有一种就是 multi-column index,我们之前讲过了,就是当你比如说按 latitude 的 search 的时候,你可以用 geohatch 或者 kd 或 r 或 rectangle 的 tree 进行 lookup,这个就比较偏了,感兴趣的话可以 lookup 一下,特别这个 post-west 的 r 还是比较有趣的。然后最后一点是 fuzzy search,在lucin里面 fuzzy search,因为lucin是个try,所以当你比如说我们可以举个简单例子,比如说你要找foo的时候,就是fooo,找fooo的时候,然后你中间那个corrector不知道是什么就是F star O就是所有满足FOO或FIO或FUO都可以那你这种情况下怎么找呢因为它是个try嘛所以你先找件F这个corrector然后对F的所有child全部search然后它这个child下面再有O的话那就是满足你这个fuzzysearch的record如果你这个child里面下面没有O那就不属于了,就是backtracing,就这样它不属于你就可以支持fuzzy search,在losing里面支持fuzzy search但是如果你是只是这种,我们想一下如果只是这种lock structure trade的话或者是这种exactly match,index match的话你是不支持这种f什么star o这种search是不支持的好,就是index了,index也是相对比较复杂就是可能需要一些延展阅读就是如果对这个比如说这个SecondaryIndex不是很熟的或者是对ClusterIndex不是很熟的或者MulticolumnIndex不是很熟的可能还需要额外读一下就是简单给大家一个概念这个还是有很多细节的有什么问题吗大家那我们看接下来我们之前看的都是transactional database然后除了transactional database 还有analytic database这两个access pattern是完全不一样的像我其实大部分职业时间都是work on analytic database要么是做了一个analytic database就是我的customer就是unounted database的user举个例子吧transactional database我举个简单例子用我这个customer举个简单例子比如说我们在这个trip上Uber上有人request一个trip 是吧那它就是属于叫transactional database它是发生了一个transaction就是有人request一个trip然后这个trip完成了有个payment就是transaction但是呢我的customer不care多少个transaction我的那个stakeholder就是我的那个甲方我甲方爸爸不care有多少个sansaction他care什么呢就是Uber上面有多少个incidencesafety incidence那我实际上search的是一个analytic database就是我需要一个analytic database所以我是要去找见所有的什么San Francisco的trip然后对所有的San Francisco triprip,哪些有incidence,我要进行分析,然后就成一个table,然后它可以search这个table,是吧?所以这两个lookup pattern是完全不一样的。如果是比如说你是order trip的话,你其实每次你只能order一个trip,所以这个是small record fetchback key,但是如果我是找所有San Francisco的incidence的话,我是要把所有的trip在San Francisco的trip全部拿出来,然后把它aggregate 起来,然后分析有多少个incidence所以如果是transaction,就是只order一个trip的话,它实际上是random access那么多trip record,是random access你需要非常lowlandancy的一个rights但是对我们这种courley来说,对我server的那个stakeholder的courley来说,甲方爸爸的courley来说的话我需要注重的什么呢,是注重的ETL,就是这个data的bulk import还有这个event stream,就是它这个access pattern是非常大量的数据Dudge record, 然后如果我是order一个chip的话,就是普通的user,但对我来说的话,对于这个analytic database的话,就是比如说我们就是Head of Safety Data,或者是那个Bot Member,Uber的Bot Member,就是Dara这种CEO这种就是我的间接customer, [60:00] 然后其次的话最后的话就是这个data代表什么这个Data的话,如果是这个Transaction的话,这个Data表示这个Data的最新的状态,这个Trip是不是完成了?这个Trip是不是Complete了?如果是Analytic的话,这个Trip所有的状态放在一起,所以我非常喜欢Immutable,没事都一直说Immutable,Immutable也是非常好的一个设计理念,就是你所有的Event不覆盖,你就是写一个新的,然后你到时候把所有的Event列出来,12345发生了什么都列出来,ImmutableRecord,所以你这个Event的所有的History的状态全部有。好然后最后的话,DataSize的话,其实一个request可能就是几K,到几个M之间嘛,然后你整个DataSize,就是你一个Request是1k到1m之间,你整个DataSize可能是Gigabyte,Terabyte,但是对于Analytics,因为你所有的Record都有,甚至TBs和Petabytes之间,所以这个DataSize也是不一样大的好,这块的话也给了一个analytic 例子,实际上的话这个analytic database 因为它的access pattern 完全不一样,所以它有一个special 的叫data warehouse 和data lake 的概念Data Warehouse和Data Lake区分也非常简单,Data Warehouse你想就是Amazon的仓库,你实际上已经全部索引好了,或者是你想一下是IKEA的仓库已经全部索引好了,就是你只要look up一下,然后去对应的那个ISO枣就可以了。但是Data Lake,你可以想一个Lake,就是你有Data就扔进去,有Data就扔进去,所以它这个Data首先更不规则一点,有一个湖吗?你就知道它这个,你可以叫Data Garbage Can,是吧?更不 structure 一点,然后其次没办法,很多时候没有那么好的所以,没有那么 index 好就是写的时候,这个ETL的过程是软的,其实是非常不frequent的,经常是一个小时的,一个小时是一天软一次然后把这个transaction最新的data全部ETL一下,然后放到datawarehouse里面,然后你在这个cory的时候,所有的cory就是读cory了就是read query了,你就不对这个data经营写了然后这个就是Analytic Database里面,它schema也是和普通的schema不一样的像他这种情况下,Schema很多都是Star Schema就是这种看起来就是这种就比如说这个里面,Sales的例子里面,它有Fact和Dimension,Fact就是记载了一个Transaction,比如说卖了一个东西是吧,这种情况下它有一些Key,有一些DateStream,然后DateKey,有一些ProductSKey,然后它这个fact就记载了一个transaction的过程一般来说这个analtic这个fact就是记载transaction的然后它每一个column又可以reference到一个东西不管它reference dimension是data呢,dimension是customer呢Dimension是Promotion,还是Dimension是Product,还是Dimension是Store,它都像一个Entity一样是吧?所以这个就是Fact有点像Transaction,Dimension有点像Entity,就是Fact and Dimension Table。然后它这个形状画出来的很像一个Star,是吧?很像一个Star,或者像一个Snowflake,所以它叫Star Schema或Snowflake Schema。所以为什么这种情况下,我们的analytic database 要用不同的一个设计呢?一美!思考一下,比如说在一个fact table里面,你实际上一个fact table需要100th of columns,如果看那个Airbnb很多的endblock,包括Uber的endblock,你一个fact table经常很容易就100多个column很容易就100多colum,非常容易就100多colum,但是你读的时候,你一般只需要100多个4到5个colum是吧,你从100个多个column,就四到五个column如果是按我们刚才讲过的transactional database,你只要是同一个肉,同一个人它都是放在一起的,所以你如果只要100多个column,从4到5column的话,你其实读一个record,它利用率就只有4%5%你的utilization rate就很低。不管你是用这个我们说的这个MySQL,Transactional Database,还是用Document Database,还是用Graph Database的Entity它的那个这个Data Access Pattern都非常Efficient你的利用率只有4%到5%所以我们这个传统的这个Transactional Database是不meet这个needs的 [65:00] 这个就是非常,performance就非常糟糕这块想提了一下,这个column database不是指Cassandra还是HBase虽然Cassandra和HBase叫wide column database但是它不是column oriented storage它在同一个column family还是一起读取的同一个column family还是一起读取的所以我们这块谈的analytic column storage是完全不同的一个storage完全不同的一个storage比如说这块有个例子就是fax out table在column-oriented storage里面它什么呢它其实date是一个filedate是一个fileproduct是一个filestore是一个filepromotion是一个file所以它每一个column都是一个file然后它这个file里面它这一块假设是个csv的格式它就假设是个csv的格式存在的时候就是, data 里面就是一系列值是吧然后这个 product 是一系列值,然后这个 store 是一系列值,然后 promotion 是一系列值,然后这样子,就是这样存储的,然后这样子,就是这样存储的。然后,Catherine问哪个DB是ColumnOriented?就是HTFS,然后HaiWa,然后我记得ParkWate好像是一种,就是ParkWate是一种,我又忘了ParkWate啥了,它就是一种ColumnOriented的一种Compression,或者是一种一种一种一种一种分别的Column Oriented的一个Compression他就是他定了一个也是非常火的最近非常火的效率非常非常高的一个Compression他就是按这样来Compress的就是按Column Oriented的这个Database来Compress的我记得或者有人更懂跨客的话可以说一张就是对我Uber那一波有用一个叫Auq这个Auq也是一个也是一个开源的一个Compression它有不同的优化一个是Arc然后一个ParkrootFile Format我们可以简单看一下我记得我之前读过一下但我确实忘了什么回事大家有空自己读一下,因为我也没办法解释更多因为我自己忘了怎么回事了有多种Compression,column-oriented database compressionPerkrate.org是比较常见的一个其中Perkrate比较好一点,因为我听过很多人说它很不错然后这种情况下你看就是每一个column就变成一个file了每个column变成一个file了然后你其实可以在这个上面进行一些额外的优化怎么优化呢比如说你可以变成一个bitmap可以变成一个bitmap比如说这是一个productfile就是productcolumn这是一个product的column这个column的file我们可以变成什么呢就是我们可以变成一个bitmap就是product是29的时候在哪里出现了Prodac29只在这一行出现了只在第若干行出现了Prodac30只在这就是这个29之后两行出现了Prodac30也只在这几行出现了所以它就变成了一个beatmap这个效率是非常高的变成这个beatmap呢如果它是一个dense的beatmap你可以这么存如果是个非常sparse的beatmap你还可以用一个encoding来去格外的优化什么优化比如说你可以做一个简单的runlance encodingrunlance encoding比去额外的优化什么优化,比如说你可以做一个简单的run length encodingrun length encoding,比如说9的话就表示前面有9个0然后follow by一个1,然后后面全是0这个的话30就表示前面有10个0,follow by两个1,然后后面全是0这样的话,你如果这个是个非常sparce的一个table的话你其实每一个value这个几个值就搞定了我们可以想一下这个就是我们之前举个例子比如说这个chip的state是吧美国state一共就50个state50个state那你这样的话你这个所有的value就50个然后每50个value然后在你不管是用bitmap存还是runlens存这个encoding的效率都很高就是实际上就是你这个file就变成了50个column是吧就50个row这个file就变成了50个row是吧每一个row就是一个state的值然后它后面不管是bitmap还是runlens存效率也很高其次的话它做这个operation的时候效率也很高这operation有什么operation呢?比如说我们这块做的operation就是你可以做应这个operation就是他们中间的一个是吧比如说你是不管你这个是30,68,69当你做这个operation的时候你实际上就把这个30 [70:00] 是这个肉那个 Bitwisebitwise out了一下68和69就是你bitwise一个操作,效率非常高,你就知道所有这些肉是吧,就是第一个第二个第三个第四个第二个都是满足这个要求的就是你实际上就是把这这三行 bitwise all 了一下就比较效率比较高,然后你比如说你做这个B2S End的时候,就是你找这个product是,比如说最近出来一个新的游戏是吧?Lasso US 是吧?然后你早在San Francisco GameStop 出售的这个那你就把这个product里面last.us找出来,然后就把start的那个里面找出来,它可能是两个beta rate是吧,然后你把这个beta rate进行一个logical end,然后你得出的结果就是那个record就能很快的早见这个效率是非常非常高的,因为你这个效率非常非常高,你不需要把这个fact table 100个column全部读出来,你想如果做的话你要把100个column全部读出来,然后把所有的row读出来,然后进行compress,然后进行and和out的操作,效率非常非常低。然后最后一点是这个操作是要满足一个条件的这个条件是什么呢这个file format是要满足一个条件,这个条件是什么呢?你不能写不能随便的写,为什么呢?思考一下,如果这时候,它这种情况下,它是按date来进行order的如果你写了一个新的Raw,它可能有多个column进行order,先按dataorder,然后再按什么order,如果你写了一个新的照片你是写了一个新的 row,比如说这个date加了一个 row,在这之间加了一个什么1401,102.5假设有102.5是吧那你整个所有的file全部要重写因为你实际上你写了一个新的时候你要对于所有的这个file所有的100多个column的file中间全部加一个,那你所有的后面全部要位移。你思考一下,比如说你加了个140101, worst case,140101,你要在所有的file最前面加个140101,后面全部要平移。这个complicity多少?因为complicity是O大N,是吧?这个大N是所有的column乘以所有的row。这个complicity是非常高的,所以这个analytic database是写的时候是非常infrequent,他可能一小时写一次然后你读的时候是非常frequent并且你的读的call也是非常heavy的,就是一次读可能读所有的tetabase全部读一遍,你读的call非常heavy,然后你写是非常infrequent的。谢谢大家好,最后总结了,所以Transactional Database呢,一般是 user facing 的,所以它可以看到一个 huge volume request, million request per second,这种都常见。然后这种情况下漏的比较高,所以通常只 touch 一个 small record,然后只是TouchSmart Record,然后你就找见你具体的Record,通常你的SickTime是Bottle Nightsick time,就是找件具体的record,所以你需要index,就很快的sick到那个record。然后这个transactional database,因为它是用大量的data读取,是吧?所以你不需要index,你如果一次要读取50%的data,要不要index无所谓。所以你这种情况下,你的disk bandwidth,你要从data,上binion data,读取一半的data,第四个ban位是bottleneck,所以它更讲究的是compress,是吧?compress data,然后更讲究的是怎么样把compress,怎么样用column-oriented的图,你的utilization rate比较高,你要只读四个column,那你就不需要读额外的file,所以这样的优化是,就是专门针对这个analytic use pattern的。这块的话是Column RNT Storage 比如说Redshift是一个就是closed source的,就是紧张大臣在那个redshift的工作是一个closed source的就是Column-oriented storage,它是专门进行优化的,然后这个Hadoop,然后这个Hadoop Hive, ParkWate,这个都是它这个生态系的也是Column-oriented, 专门负责Analytics的这个这是Transactional Database和Analytical Database的区别很多时候这个analytic database 其实用户群还是比较多的,像我之前几次工作其实都是focus on the analytic user,user都是analytic user,工作的话就比较mixed,有时候是transactional database,有时候是analytic database,就是需要你有一种理解就是它两个总体的区别是什么,然后它这个data是怎么样从transactional database flow到analytic database的希望有个大概的理解 [75:00] 如果感兴趣的话相对来说,analytic database 这块比较新一点,就是可能 run path 起来不是很复杂好,今天就到这里吧,就是今天我们如果回顾一下的话我们回到最前面这张structure,主要讲的是两大派的database。一个是analytic database,一个是transactional database,其中transactional database也讲了b-tree和log-structure-merge-tree。然后也各有各样的优势吧,B-Trade是比较老的,它这个比较更稳定一点,然后Transaction handle比较好一点。但是它读的时候,它这个Performance虽然比较稳定,它读的时候它比较fragmented一点,效率比较低。LockStructure Merge Tree,它Performance有时候,如果你没有tune好的话,不predictable,因为它有background process,不停地做compacting。但是它这个RAID的Performance其实很不错的,因为你都是sequentialRAID的话,效率是,理论上是比B-Trade要快一个数量级的。因为这个sequential write 一般是比那个就是这种非常fragmented write快一个数量级。所以就是讲了这三种不同的database。有什么最后的问题吗如果有问题的话回答一下如果没有的话就到这里好了好,看了没什么问题,好,谢谢大家。