HASH GAME - Online Skill Game GET 300

　　引入了内存索引之后，很自然的一个问题就是机器重启，内存索引丢失怎么办？ 可以重新遍历文件构建索引，后面再讨论其他更合理的方案。 另外，相同的key若有多次写操作，则本地数据文件中也会存在多条记录；因此就有磁盘耗尽的风险；极端情况下，对同一个key持续不断的写入，直到磁盘写满，实际上只有最后一条记录是有效的。磁盘空间放大特别显著； 同时，hash map需要全部存在于内存中，若key的数量超过内存限制，也会有问题

　　当前SSTable只有DataBlock和IndexBlock，后续可能会有更多类型的Block加入进来，就跟操作系统启动时候的BIOS总是从固定地址执行机器指令一样，我们需要在SSTable添加固定的启动位置，即Footer(上图右侧所示)，可以认为其中的IndexBlock索引是B+树的根节点；Footer是固定大小的（48字节),最后的魔数用于验证文件是SSTable类型，中间空余部分填充空序列就好。

　　此时还有一个问题就是：数据初始是写入到：memtable中的，若还没来得及dump到文件中，发生了机器故障，重启之后内存丢失，memtable中写入的值也会丢失。 要想保证不丢失数据必须要落盘，为了保证写入性能不受影响，以及磁盘顺序读写性能是最高的，我们可以引入预写日志(WAL-write ahead log）。 数据首先顺序追加到预写日志中，待数据落盘落盘之后再写入到memtable中，待memtable中的数据持久化到磁盘时，该memtable对应的预写日志也就可以删除了。1.7 LSM Tree

　　一般情况下供分析师使用的表通常很宽(有几百上千个字段/列，经过聚合多个数据源和业务数据得到)，但是每次分析时可能只会使用其中很少的列（比如用户画像表，会有很多字段，但是一次sql可能只是涉及到很少的字段-select max(age) from table where gender = male）；在OLTP数据库中，存储以面向行的方式来布局；为提高查询性能，面向列存储可优化分析场景下的查询性能；列存如下图所示：

　　举个例子，以Twitter查看推文流和发布推文而言:发布推文：平均 4.6K-12K QPS推文流浏览：300K QPS因此消息存储有两种方式：1) 拉模式 2）推模式 拉模式，所有消息放在全局 tweet 表中；用户浏览推文流时，首先查找所有关注对象，再关联到推文，以时间序展示；发布推文只是生成一条记录；压力在查看时的关联查询； 推模式，对每个用户维护一个序列“邮箱”，发推文时，先查询其关注者，再将推文存储到每个关注者的时间线缓存中；查看时只需要遍历自己的“邮箱”即可；压力在发推文时候的“信件投递”twitter开始时使用方案一，但读压力与日俱增；转而采用第二种方案；第二种方案最大的问题是当明星博主拥有超过3000万粉丝时，扇出巨大，需要写巨量的“邮箱”；最终方案融合，大多数博主因为粉丝较少，持续采用第二种方案；少量粉丝巨大的明星博主采用方案一，推文被单独存储，推文展示时合并渲染； 因此，每个用户粉丝的分布情况就是可扩展的关键负载参数；

　　可运维性： 运维更轻松 简单性： 简化复杂度；做好抽象，隐藏细节，对外提供干净/易懂的接口；如高级语言屏蔽此层寄存器/系统调用的复杂度； 可演变性： 易于改变2. 数据复制经过第一部分的讨论，我们在单容器上得到了一个可高效读写的存储引擎，但机器总会故障，如何保证在机器故障的情况下，服务对外提供的读写能力不受到影响？自然就是数据在多个容器上存储多份，待机器故障后，使用其他机器的数据对外提供服务。那如何保证不同机器上有多份数据，且它们是一致的就成为接下来要解决的问题。

　　如上图所示，当从节点向主节点请求数据同步的时候，主节点做两件事情，一个是产生一个数据快照（拥有所有的存量数据）；另一个是记录此刻开始发生的数据更改日志(同步开始后的增量数据)；从节点首先将数据快照应用到自身节点，然后将发起同步请求开始的主节点的数据更改日志（即快照时候的数据变更, 上图中的红色部分）应用到自身；日志同步流中的节点通常称之为LSN( 日志序列号/Log Sequence Number)

　　对外部应用程序来说，逻辑日志格式更容易解析；因此通过接出复制日志，可是方便的将数据库数据同步到离线数仓中除了基于逻辑日志的复制外，还有基于语句的复制和基于 WAL 日志的复制 基于语句的复制主节点记录执行的所有写请求，并将该操作语句作为日志发送给从节点；类同于每个从节点都在执行来自客户端的请求；非首选方案；会存在不适用的场景: 1）非确定性函数的语句，如 Now() Rand()，不同副本会产生不同的值； 2）有副作用的语句，如触发器/用户自定义函数，会在不同副本有不同副作用 基于预写日志(WAL)传输主节点除了将WAL日志写入磁盘之外，还会通过网络将其发送给主节点； 缺点是日志描述的数据非常底层，如哪些磁盘块的哪些字节发生改变；不同版本的存储可能会有差异，无法进行滚动升级，只能停机升级；2.1.2 复制滞后问题

　　3. 数据分片通过第二部分的讨论，我们已经能够在多个容器通过复制技术保存数据的多份副本，在宕机/降低读延迟和读QPS扩展性上有了提升；但现在仍面临一个问题就是：数据在一台机器上存不下怎么办？面对海量数据和非常高的查询压力，只是复制技术还不够，我们还需要将数据拆分成分片，用每个分片去承载部分数据和部分请求；对分片不同系统有不同的称呼，Shard、 Region、 Tablet、 vnode 、vBuciet、 Partition等都是对分片的领域特定称呼3.1 键-值数据的分片