Leslie Lamport 1979 年的论文 How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs 定义： The customary approach to designing and proving the correctness of multiprocess algorithms for such a computer assumes that the following condition is satisfied: the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. A multiprocessor satisfying this condition will be called sequentially consistent. ...

tags: 一致性，Memory Model 当执行给定程序时，硬件和编译器之间的契约，对编译后后的代码对存储在内存中的数据更改的可见性和一致性。 这种契约称为「内存一致性模型（Memeory Consistency Model）」或仅仅是「内存模型（Memory Model）」。 最初目标是定义程序员编写汇编代码时硬件提供的保证，后来用来定义高级编程语言（如 C++ 或 Java）对该语言编写代码的程序员提供的保证。 例如下面变量都初始为 0 的情况下，线程 1 和 2 都运行在自己专用的处理器上，都运行到完成，这个程序能打印 0 吗？ // Thread 1 // Thread 2 x = 1; while(done == 0) { /* loop */ } done = 1; print(x); Memory coherence vs consistency 内存一致性（coherence） 内存顺序一致性（sequential consistency） 硬件 顺序一致性 x86 总存储有序（x86-TSO) ARM/POWER Relaxed Memory Model 弱有序和无数据竞争（DRF） 编程语言内存模型

tags: Memory Model,Computer Systems Hardware Memory Models 硬件内存模型 内存模型 内存一致性模型

tags: Emacs 优化 GC 参考：LSP Mode Performance ;; Optmization ;; Sources: ;; ;; - https://www.reddit.com/r/emacs/comments/ofhket/further_boost_start_up_time_with_a_simple_tweak/ ;; - https://emacs-lsp.github.io/lsp-mode/page/performance/ ;; (setq gc-cons-threshold 32000000) ;; 32mb (setq read-process-output-max (* 1024 1024)) ;; 1mb 将启动速度优化到 3 秒左右。 Dumping Emacs Emacs WIKI: Dumping Emacs Painless Transition to Portable Dumper

为什么不用取模？ 节点数发生变化时，会导致很多关键字需要做节点数据迁移，会大大增加再平衡的成本。 固定数量的分区 创建远超实际节点数的分区数量，然后再为每个节点分配多个分区。 新加入节点 从现有的节点上匀走几个分区，直到分区再次达到平衡。 删除节点 采取和上面相反的过程。 优点 分区总数量不变，也不会改变关键字的分区映射关系。 唯一需要调整的分区与节点的映射关系。 分区和节点的映射关系调整可以逐步完成。 缺点 分区数量需要数据库创建时确定，并不能更改 动态分区 分区数据增长超过一个可配参数的阈值（HBase 10GB），它就拆分为两个分区，相反则合并相邻的分区。过程类似B-trees 的分裂操作。 每个分区总是分配一个节点，一个节点可以承载多个分区。 分区分裂 将其中的一半转移到其他节点以平衡负载。 优点 分区数量可以自动适配数据总量。 空数据库可以配置初始分区解决少量数据集就一个分区避免系统热点（HBase 和 MongoDB） 按节点比例分区 使分区数与集群节点数成正比关系（Cassandra 和 Ketama），就是每个节点具有固定数量的分区。 当节点数不变时，每个分区的大小与数据集大小保持正比增长关系。 新加入节点 随机选择固定数量的现有分区进行分裂，然后拿走这些分区的一半数据量。 优点 较大的数据可以使每个分区的大小保持稳定。 缺点 存在不公平分裂。

对所有数据构建全局索引，为了避免瓶颈，对索引本身进行分区，比如： 将 a～r 开始的关键字放在分区 0 将 s～z 开始的关键字放在分区 1 优点 可以支持高效的区间查询 读取更为高效 缺点 写入速度慢，会引入明显的写入放大 写入逻辑复杂 难以保证索引时刻最新，需要跨多个相关分区的分布式事务支持 实践 对全局二级索引的更新往往都是异步的。

每个分区各自维护自身的二级索引，读取时需要对所有分区节点进行查询然后对结果进行合并。 这种方法虽然二级索引查询代价高，但依然广泛用于实践：MongoDB、Riak、Cassandra、ElasticSearch、SolrCloud 和 VoltDB。

可以基于关键值哈希函数的方式分区，解决基于关键字区间分区数据倾斜与热点的问题。一个好的哈希函数可以处理数据倾斜并使其均匀分布，并且不需要在加密方面很强。 优点 这种方法可以很好的将关键字均匀分配到多个分区中。 缺点 丧失良好的区间查询性能。即使关键字相邻，也会分布在不同的分区上。

为每个分区分配一段连续的关键字或者关键字区间范围。

负载倾斜会导致所有负载都集中在一个分区节点上，这种负载严重不成比例的分区即称为系统热点。 应用层解决 即使通过基于关键字哈希值分区和基于关键字区间分区等策略解决了大部分热点问题，但是极端情况下依然会出现热点，比如社交媒体的热点时间都会导致热点，只能通过应用层解决，一个简单的技术： 关键字开头或结尾添加一个随机数，两位随机数就可以将关键字的写操作分布到 100 个不同的分区上； 读取就必须从所有的 1000 个关键字中读取数据然后进行合并； 通过额外的元数据标记哪些关键字进行了特殊处理。 由于对读取造成的额外开销，所以通常只有对少量的热点关键词附加随机数才有意义。

分区不均匀时出现某些分区节点比其他分区承担更多的数据量和查询负载。倾斜会导致分区效率严重下降。

每一条数据都属于特定的分区，每个分区都是一个小型数据库。 目的 提高扩展性，分散大的数据集和查询负载。 目标 将数据和查询负载均匀的分步在所有节点上。如果分布不均匀会出现负载倾斜和系统热点。 数据分区与数据复制 结合数据复制每个分区在多个节点都有副本，进行冗余提高可用性。 键-值数据的分区 避免系统热点最简单的方法是将记录随机分配给所有节点上，缺点是：没办法知道数据保存在哪个节点上，所以读取时需要查询所有节点。 基于关键字区间分区 基于关键字哈希值分区 负载倾斜与系统热点 分区与二级索引 二级索引不能唯一标识一条记录，比如查询颜色为红色的汽车。二级索引带来的主要挑战是它们不能规整的映射到分区中。 有两种方法来支持对二级索引进行分区： 基于文档分区的二级索引 基于词条的二级索引分区 分区再平衡 动态再平衡策略 自动与手动再平衡操作 请求路由 策略 客户端可以连接任意节点，并由节点做转发不在当前节点的分区请求。 由路由层来充当分区感知的负载均衡器。 客户端直接感知分区和节点分配关系，客户端直连目标节点。 做出路由决策的组件 Zookeeper gossip 协议

syn::Span 代码位置

循环展开 let fields = vec![ syn::Ident::new("foo", syn::Span::call_site()), syn::Ident::new("bar", syn::Span::call_site()), ]; let token = quote!{ #(#fields),* }; // -> foo,bar

准备 解析宏通过两个 crate 进行： quote = “1.0” syn = “1.0” Derive 属性宏 探讨 Rust 宏系统中带属性（Attributes）的 Derive 宏的几种变体，以及如何进行解析。 属性宏的变体 函数调用 #[derive(Custom)] struct Demo { #[attr(arg)] a: i8, } 关键字参数调用 #[derive(Custom)] struct Demo { #[args(name = "val")] b: i8, } 直接赋值 #[derive(Custom)] struct Demo { #[meta = "val"] c: i8, } 函数调用 关键字参数调用 可以从 Struct 解析出各个字段，通过解析各个字段的 attrs 属性，并对 attrs 进行遍历，使用 attr.parse_args()? 即可解析出对应的关键字参数，咱们以前面的代码为例: #[derive(Custom)] struct Demo { #[args(name = "val")] b: i8, } 对应的解析代码为： ...

确定前后关系 服务器为每个主键维护一个版本号，每当主键新值写入时递增版本号，并将新版本号与写入值一起保存。 当客户端读取主键时，服务器将返回所有（未被覆盖的）当前值以及最新的版本号。且要求写入之前，客户端必须先发送读请求。 客户端写主键，写请求必须包含之前读到的版本号，读到的值和新值合并后的集合。写请求的响应可以像读操作一样，会返回所有当前值，这样可以一步步链接起多个写入的值。 当服务器收到带有特定版本号的写入时，覆盖该版本号或者更低版本的所有值，但必须保存更高版本号所有值。 当写请求包含了前一次读取的版本号时，意味着修改时基于以前的状态。否则它将与所有的其他写入同时进行，不会覆盖任何已有值，其传入的值将包含在后续读请求的返回值列表中。 合并同时写入的值 上面算法不会导致数据丢失，但是客户端需要做一些额外的工作：如果多个操作并发发生，则客户端必须通过合并并发写入的值来继承旧值。同时删除需要特殊的墓碑标记，防止被合并回去。 版本矢量 每个副本和每个主键均定义一个版本号，每个副本在处理时增加自己的版本号，并跟踪从其他副本看到的版本号。通过这些信息来指示要覆盖那些值，该保留那些并发值。 所有的版本号集合称为版本矢量。

LWW：最后写入者获胜 Happens-before 关系和并发

当节点不能满足 \(w + r > n\) 时将写请求暂时写入一些可访问的临时节点中，一旦网络问题得到交接，临时节点需要把接收的写入全部发送到原始主节点上。这就是所谓的数据回传（或者暗示移交）。

tags: 一致性 确定读写成功 确定读写节点在多少节点成功才可以认为写入成功：需要保证读取时至少一个包含新值。 n 个副本的情况下，写入需要 \(w\) 个节点确认，读取必须至少查询 \(r\) 个节点，则只要 \(w + r > n\) ，读取的节点中一定会包含最新值。 \(w\) 仲裁写（法定票数写） \(r\) 仲裁读（法定票说读） 一般 \(n\) 设置为奇数： \(w=r=(n+1)/2\) （向上取整）。 可容忍的失效节点数 仲裁条件 \(w+r>n\) 定义了系统可容忍的失效节点数。 \(w<n\) ，如果一个节点不可用，仍然可以处理写入。 \(r<n\) ，如果一个节点不可用，仍然可以处理读取。 \(n=3\),\(w=2\),\(r=2\)，则可以容忍一个节点不可用 \(n=5\),\(w=3\),\(r=3\), 则可以容忍两个节点不可用 局限性 如果采用了 sloppy quorum，写操作的 w 节点和读取的 r 节点可能完全不同，因此无法保证写请求一定存在重叠的节点。 并发无法明确顺序，需要进行合并并发写入。如最后写入者获胜。 同时读写，写操作在一部分节点上完成，则读取新值还是旧值存在不确定性。 部分节点写入成功，但是最终写入失败无法回滚。 新值的节点失效，但恢复数据来自某个旧值，则总的新值节点数低于 w 边界情况

没有主节点，允许任何节点接受来自客户端的写请求。 实现方式 客户端直接将其写请求发送到多节点 一个协调者代表客户端进行写入，与主节点的数据库不同，协调者并不负责写入顺序的维护。 节点失效时写入数据库 客户端将写请求并行发送给三个节点，两个可用节点接受写请求，而不可用副本则无法处理该请求。 现在失效的节点重新上线，客户端可能会读取到旧的值。 为了解决这个问题客户端并行的向多个节点发送读请求，并通过版本号来确定哪个值更新。 读修复与反熵 读修复；客户端并行读取多个节点，检测到过期的返回值，然后用新的返回值写入到返回旧值的副本。 反熵过程：后台不断查找副本之间的差异，将任何缺少的数据从一个节点复制到另一个节点。不保证特定顺序的复制写入，并且会引入明显的复制滞后问题。 Quorum 一致性 检测并发写

最常见的拓扑结构，提供更好的容错。每个节点从其他所有节点同步写入。

通过指定一个根节点，根结点将所有的写操作转发给其他所有节点。

每个节点接收来自前序节点的写入，并将这些写入（加上字节的写入）转发后后序节点。同时通过唯一 ID 防止无限循环。

每个副本总是保存最新值，允许覆盖并丢弃旧值。假定每个写请求都最终同步到所有副本，只要我们有一个明确的方法来确定哪个写入时最新的，则副本可以最终收敛到相同的值。 通过每个请求附加一个时间戳，选择最新即最大的时间戳，丢弃较早的写入。则为最后写入着获胜（last write wins，LWW）。 缺点 会造成数据丢失。 适用场景 缓存系统。 确保安全无副作用 唯一方法是只写入一次然后写入值视为不可变，这样旧避免对同一个主键的并发（覆盖）写。

多个主节点看到的执行顺序不一致，病了同时按照各自看到的写入顺序执行，那么数据库最终将处于不一致状态。 数据库必须以一种趋同的方式来解决冲突。 可能的解决方式 给每个写入分配唯一的 ID，如基于时间戳的最后写入者获胜。 为每个主节点分配一个唯一 ID，序列号高的优先于序列号低的主节点，可能导致数据丢失 以某种方式合并值，如按照字母顺序拼接在一起 利用预定义号的格式记录，然后依靠应用层逻辑，事后解决冲突（可能会提示用户）

应用层保证对特定记录的写请求总是通过同一个主节点，来避免发生些冲突。 如用户更新自己的配置总是路由到特定的数据中心。 缺点 特定数据中心发生故障不得不改变事先指定的主节点。

对于一系列按照某个顺序发生的写请求，同时读取这些内容时也会按照当时写入的顺序。 场景 分区数据库中出现的一个特殊问题。 正常对话： P: C小姐，你能看到多远的文莱？ C：大约 10s，P 先生。 但是由于复制滞后，最终能被观察到的可能是： C：大约 10s，P 先生。 P: C小姐，你能看到多远的文莱？ 解决方案 低效率：具有因果关系的写入都交给一个分区来完成。 新方法：跟踪事件因果关系。

是一种比强一致性弱但是比最终一致性效应强的保证，单调读保证： 如果某个用户依次进行多次读取，则绝不会看到回滚的现象，即在读取到较新的值之后又发生读旧值的情况。 场景 用户刷新网络，读请求被随机路由到某个从节点，先后从两个不同的从节点读取到了不同的内容，比如看到一个新添加的评论一次出现，一次消失。 解决方案 按照用户 ID 进行哈希方法取代随机路由。

也称为「写后读一致性」，解决用户主节点写入后立马从从节点读取不到到情况。只能解决单用户的一致性，但是解决不了多用户的一致性。 场景 用户新提交了评论，但是自己看不到，需要等一会才能看到。 解决方案 记录更新时间戳，在指定时间内从主节点读取。

主从异步复制的情况下会导致数据库中出现明显不一致，此时从不同的从节点读取就会得到不一样的结果。这种不一致只是一个暂时状态，如果停止写入数据，经过一段时间之后，从节点最终会赶上并与主节点保持一致。 这种效应被称为最终一致性。

异步同步的情况下出出现最终一致性效应复制滞后会导致：用户提交了修改到主节点，但是从从节点没有读取到最新的变更，比如看不到自己提交的评论等。 读写一致性：读自己的写 一旦用户的数据最近发生改变则路由用户请求从主节点进行读取，规避复制滞后的问题。 缺点：只保证单一用户写后读的的一致性，但是不保证多个用户的一致性。比如发了一条评论，自己能刷新到但是同在身边的朋友可能就刷新不到。 单调读一致性 前缀一致读 解决方案 应用层可以提供比数据库更强有力的保证。 事务是数据库提供的更强保证的一种方式。

基于语句复制 优点：简单 缺点：语句副作用，或者随时间改变返回值的函数的使用会导致复制的数据产生改变。 基于预写日志（WAL）传输 优点：解决基于语句复制的问题。 缺点：日志描述过于底层：哪些磁盘块的哪些字节发生了改变，和引擎实现高度耦合，不利于模式演进。 基于行的逻辑日志复制 用一系列记录来描述数据表行级别的写请求： 对于插入行，日志包含所有相关列的新值。 对于删除行，标记主键删除。 对于行货更新，记录主键和对应列的新值。 MySQL binlog 基于此模式。 优点：更利于模式演进，支持向后兼容，同时解耦特性引擎便于外部解析。 基于触发器的复制 触发器支持注册自己的应用层代码并在数据发生改变时被调用。 优点：将复制控制交给应用层，支持更高的灵活性。 缺点：开销更大，更容易出错。

主从模式下主节点进行写入，可以从从节点进行读取。 同步复制 主节点写入，并等待从节点写入后再返回写入成功。 半同步复制 主节点写入，选举一个从节点进行同步复制，其他从节点进行异步复制，一旦同步复制的从节点出现性能下降或故障则选用一个新的从节点进行同步复制。 异步复制 主节点写入，不等待从节点写入直接返回写入成功。

主节点与从节点 复制 单个节点可以完整存放所有数据副本，节点间进行主从复制。 配置新从节点 可以通过快照来加速新从节点复制： 对主节点的数据副本产生一个一致性快照，避免长时间锁定数据库。 拷贝快照到从节点 请求快照后面的更改日志 应用数据变更 节点失效 从节点失效：追赶式恢复 主节点失效：节点切换 自动切换 确认失效 选举新的主节点 使主节点生效 挑战 从节点复制不完整 各个数据层数据不一致，如 MySQL 和 Redis 之间 多个主节点选举：脑裂 如何有效检测主节点失效 复制日志实现 复制滞后问题 多主节点复制 使用场景 多数据中心 优点： 性能 容忍数据中心失效 容忍网络问题 缺点：写冲突 离线客户端操作 协作编辑 处理写冲突 同步与异步冲突检测 同步：等待写请求完成对所有主节点的同步再通知用户写入成功。 异步：等待单一主节点写入成功后通知用户卸乳成功，稍后多主节点数据同步的时候才能检测到冲突 避免冲突 收敛于一致的状态 自定义冲突解决逻辑 写入时解决 读取时解决 拓扑结构 环形拓扑 星型拓扑 全部-至-全部型拓扑 无主节点复制

当一个不可能出错的事物出错了，通常也就意味着不可修复 – Douglas Adams，《基本无害》（1992） 关于写文档 There is a secret that needs to be understood in order to write good software documentation: there isn’t one thing called documentation, there are four. They are: tutorials, how-to guides, technical reference and explanation. They represent four different purposes or functions, and require four different approaches to their creation. Understanding the implications of this will help improve most documentation - often immensely.

Actor 模型是用于单个进程中的并发模型。逻辑被封装在 Actor 中。每个 Actor 通常代表一个客户端或实体，可以具备本地状态（不共享），通过发送和接收异步消息与其他 Actor 通信。不保证消息传送：某些错误情况下，消息将丢失。每个 Actor 只处理一条消息，因此可以由框架独立调度。 Actor 框架集成了任务调度和消息流的框架。

两种模式语言：IDL 用于人工编辑，另一种更易于机器读取。 Avro 编码数据中只有对应字段的长度和具体的数据，不包含字段的类型信息。 写模式与读模式 写模式：使用所知道的模式的任何版本来编码数据（可以编译到代码中） 读模式：解码时期望数据符合某个模式，可能是构建过程中基于模式生成 Avro 的关键思想是写模式和读不必完全一样，只需要保持兼容，由读取端解决差异：通过对比查看写模式和读模式并将数据从写模式转换为读模式。 读取数据的代码中遇到出现在写模式但是不在读模式的字段，则忽略。 如果读数据的带代码需要某个字段，但是写模式不包含该字段的名称，则使用在读模式中声明的默认值填充。 模式演化 向前兼容：新版本的模式作为 writer，旧版本的模式作为 reader。 向后兼容：新版本的模式作为 reader，旧版本的模式作为 writer。 同时为了保持兼容性，只能添加莫删除具有默认值的字段。

每个字段一个标记号码，字段名可以随意调整因为编码信息中只有标记号码，没有字段名称，但是标记号码不能随意调整，基于此可以实现： 向前兼容 旧代码忽略不能识别的标记号码，并根据类型的注释来通知解析器跳过特定的字节数。 向后兼容 标记号码不变的情况下新的代码总是能够解析旧代码序列化的数据，但是新添加的字段不能标记为 required，不然会触发运行时错误。 同时为了保证前后兼容，删除字段也不能删除设置为 required 的字段，同时再次新添字段标记号码不能被再次使用。 改变类型同时也会导致前后兼容问题。

模式演化要保证： 向后兼容 较新的代码可以读取旧代码编写的数据 向前兼容 较旧的代码可以读取较新代码编写的数据 数据编码格式 语言特定格式 Python pickle Java java.io.Serializable Ruby Marshal JSON、XML与二进制变体 二进制变体 Message Pack：二进制的 JSON Thrift 与 Protocol Buffers Avro 数据流模式 基于数据库的数据流 不同是写写入不同的值 归档存储 基于服务的数据流：REST 和 RPC RPC 的问题 给人一种本地调用的错觉，却需要面临网络的不确定性：延迟和超时。 基于消息传递的数据流 消息中间件：RabbitMQ、Kafka 分布式Actor 框架：Akka、Erlang OTP

在线分析处理（Online Analytic Processing，OLAP）。

在线事务处理（Online Transaction Processing，OLTP）。

B-tree 是最广泛使用的索引结构。和排序字符串表：SSTables一样，B-tree 保留按键排序的 key-value 对， 这样可以实现高效的 key-value 查找和区间查询。 结构 B-tree 将数据库分解成固定大小的页或块，传统上 4KB，这种设计更接近底层硬件，磁盘也是以固定大小的块排列的。 分页因子 B-tree 中一个页所包含的子页引用数量称为分支因子。 添加新键 找到其范围新键的页 如果页没有足够的可用空间来容纳新键，则将其分裂为两个半满的页，并更新父页以包含新的键范围。 算法确保树保持平衡：具有 n 个键的 B-tree 总是具有 \(O(log n)\) 的深度。大多数据库适合 3~4 层的 B-tree。 分支因子为 500 的 4KB 页的四级树可以存储高达 256TB。 可靠性：WAL B-tree 底层的基本写操作是使用新的数据覆盖磁盘上的旧页。 如果发生页分裂则需要覆盖多个不同的页，同时更新父页，这个操作比较危险，如果此时发生崩溃则会破坏索引。 常见的 B-tree 使用额外的数据结构：预写日志(WAL)： 追加的写 WAL； 每个 B-tree 必须先更新 WAL 然后再修改树本身的页。 通过使用「锁存器」保护进行并发控制，保护 B-tree 页被多个线程访问而看到树不一样的状态。 优化 通过复制方案替代 WAL 进行崩溃恢复，修改的页被写入不同的位置，树中父页的新版本被创建，并指向新的位置。 保存键的缩略信息，可以压入更多的键，保持更高的分支因子，减少层数。 对树进行布局，相邻叶子页按顺序保存在磁盘。 添加额外的指针到树中，如左右兄弟页。 变体，如分形树：借鉴日志结构减少磁盘寻道。

索引 先来看一个世界上由 Bash 实现的最简单的数据库实现： #!/bin/bash db_set() { echo "$1,$2" >> database } db_get() { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1 } 这种数据库通过追加文件尾部的方式高效写入，许多数据库内部都是用日志，日志是一个仅支持追加更新的数据文件。但是 db_get 的性能会随着数据量的变大而下降，为了解决这个问题就需要引入新的数据结构： 索引 。 索引是基于原始数据而派生而来的额外数据结构：适当的索引可以加速读取查询，但是回减慢写速度。 key-value 索引通常使用 hash map 来实现，最简单的索引策略：保存内存中的 hash map，把每个键一一映射到数据文件中特定的字节偏移量。 优化磁盘占用 将日志分解成一定大小的段，当文件达到一定大小时就关闭它，并将后续写入到新的段文件中。 然后可以在这些段上执行压缩：丢弃重复的键，并且只保留每个键最近的更新。 同时将变小后的多个段在后台合并在一起（段在写入后不再会进行修改所以不会出现竞争）。 合并完成后将读取请求切换到新的合并段上，然后可以安全的删除旧的段文件。 实现中面临的问题 文件格式：二进制。 删除记录：通过特殊的墓碑标记。 崩溃恢复：Bitcask 通过将 hash map 快照存储到磁盘。 部分写入：文件校验丢弃损坏的部分。 并发控制：只有一个写线程。 追加的好处 顺序写性能高。 并发控制和崩溃恢复简单。 段合并避免文件碎片化。 局限性 大量的键存储在内存可能导致内存耗尽，同时需要处理哈希冲突 区间查询效率不高。

SSTables 通过按照键的顺序存储在日志段文件中来解决哈希索引面临的一些问题。它要求每个键在每个合并的段文件中只能出现一次（通过压缩确保）。 对比哈希索引的日志段 优点 合并段更加高效，即使文件大于可用内存。类似于归并排序算法中使用的方法。并发读取多个输入段文件，比较每个文件的第一个键，把最小的键拷贝到输出文件，并重复。 解决多个段文件重复：保留最新的值，因为每个段包含在某段时间内写入数据库的所有值，意味着肯定有一个值比其他所有值更新。 基于键有序的特性可以采用稀疏索引避免内存中包含所有键的索引。 将一定范围内的所有键存储到一个块中，便于需要请求范围内多个 key-value，降低磁盘 I/O。 构建和维护 保证顺序 内存中痛哦红黑树或者 AVL 树支持任意顺序插入并以排序后的顺序读取它们。 写入时，将其添加到内存中的平衡树数据结构中，成为内存表。 内存表大于某个阈值（MB级别），将其作为 SSTable 文件写入磁盘。写入同时，写入可以继续添加到一个新的内存表实例中。 处理请求顺序：首先从内存表中查找键 -> 最新的磁盘段文件 -> 次新磁盘段文件，以此类推。 后台进程周期性执行段合并与压缩，合并多个段文件并丢弃被覆盖或着删除的值。 崩溃处理 为了避免数据库崩溃最近的写入（在内存表中尚未写入磁盘）将会丢失的问题： 在磁盘上保留单独的日志，每个写入都会立即追加到该日志。并且无需排序。 内存表写入 SSTable 时，丢弃相应的日志。 使用此技术的数据库 LevelDB RocksDB 类似的 Cassandra HBase

tags: Tree 日志结构合并树（Log-Structured Merge-Tree）：基于合并和压缩排序文件原理的存储引擎通常都被称为 LSM 存储引擎。 压缩排序文件基于排序字符串表：SSTables。 LSM-Tree 基本思想：保存在后台并合并的排序字符串表：SSTables。即使数据集远远大于可用内存，仍然能够正常工作。 基于有序的特性，可以有效的执行区间查询，并且由于磁盘是顺序写入，所以 LSM-Tree 可以支持非常高的写入吞吐量。 性能优化 通过布隆过滤器优化 LSM-Tree 查找不存在的键性能低下的问题。 通过大小分级和分层压缩优化 SSTables 压缩和合并时的具体顺序和时机。 大小分级：较新和较小的 SSTables 被连续合并到较旧和较大的 SSTables。 分层压缩：键的范围分裂成多个更小的 SSTables，就数据被移动到单独的“层级”，这样压缩可以逐步进行并节省磁盘空间。

存储引擎 哈希索引 日志结构存储引擎：LSM-Tree 面向页的存储引擎：B-trees 对比 LSM-Tree 和 B-trees 项目 LSM-Tree B-trees 备注 性能 写入更快，吞吐更高 读取更快 具体场景上需要进行基准测试 存储 可变大小的段，通常 nMB 固定大小的页，传统 4KB 写入 追加，写入更多不利于 SSD 新的数据覆盖磁盘上旧的页 并发控制 后台合并进行原子替换 锁存器 其他索引结构 在索引中存储值 多列索引 全文索引和模糊索引 在内存中保存所有内容 优点：可以支持更复杂的数据结构，而无需考虑数据存储结构。 事务处理与分析处理 事务处理：OLTP 分析处理：OLAP 对比 属性 OLTP OLAP 主要读属性 基于键，每次查询返回少量记录 对于大量记录进行汇总 主要写属性 随机访问，低延迟写入用户的输入 批量导入（ETL）或事件流 典型使用场景 终端用户，通过网络应用程序 内部分析师，为决策提供支持 数据表征 最新的数据状态（当前时间点） 随着事件而变化的所有事件历史 数据规模 GB 到 TB TB 到 PB 数据仓库 星型与雪花型分析模式 星型模型也称为维度建模。 列式存储 列压缩

数据模型 关系模型 突出数据之间的关联。 文档模型 数据来自于包含文档，文档间关联很少。 图状数据模型 针对所有数据都可能互相关联。 数据查询语言 Web 上声明式查询 CSS 选择器。 MapReduce 查询 MapReduce 是一种编程模型，用于在许多机器上批量处理海量数据。 MongoDB 中的 MapReduce db.observations.mapReduce( function map() { // 2 var year = this.observationTimestamp.getFullYear(); var month = this.obbservationTimestamp.getMonth() + 1; emit(year + "-" + month, this.numAnimals); // 3 }, function reduce(key, values) { // 4 return Array.sum(values); // 5 }, { query: {family: "Sharks"}, // 1 out: "monthlySharkReport" // 6 } ); 过滤器声明式执行鲨鱼种类（MongoDB 特有扩展）。 mapper：对于每个匹配的文档都会调用一次这个 JavaScript 函数。 mapper 发射一个「键-值」对，键是 “2013-12” 格式的字符串，值是动物的数量 mapper 发射的键值对按键分组，对于相同键的所有「键-值」对，调用 reduce 函数。 reducer 函数将特定月份的所有观察到的动物数量相加。 最终输出写入到 monthlySharkReport 集合中

可靠性 故障与失效 故障（faults）或者错误：组件偏离其正常规格，可以提供容错（fault-tolerant）机制 失效（failure）意味系统作为一个整体停止 硬件故障 软件错误 人为失误 避免优化方式： 以最小出错方式设计系统。抽象、提供管理界面，使“做正确的事很轻松”，防止限制过多。 分离最容易出错的地方，提供沙箱用以放心尝试。 充分测试。 提供快速恢复机制尽量减少故障影响：快速回滚，提供校验数据的工具。 设置详细而清晰的监控系统 培训和流程 可扩展性 描述负载 QPS 数据库写入比例 同时在线活动用户数 缓存命中率等。 描述性能 吞吐量（throughput）/每秒处理数据量 延迟（latency）/响应时间（response time）：延迟是处理时间，响应时间是客户端看到的。 最好通过百分位数来监控指标：p50/p80/p90/p95/p99/p999，p50 指标表示一半请求在这个指标之下，一半在这个指标之上。 应对负载增加 无状态很方便扩容 但有状态的分布式面临一定的挑战 可维护性 可运维性：运维更轻松 监控、文档、自动化、良好的默认配置、可手动控制系统状态让系统自我修复（比如熔断机制）。 简单性：简化复杂度 抽象！ 可演化性：易于改变 TDD 重构

tags: 读书笔记,Bigdata,分布式,数据库 数据系统基础 可靠、可扩展与可维护的应用系统 数据模型与查询语言 数据存储与检索 数据编码与演化 分布式数据系统 目的：扩展性、容错和高可用、延迟考虑（多机房） 扩展： 垂直扩展：提升单机性能 水平扩展：无共享结构，由软件实现核心逻辑 复制与分区： 复制：多节点冗余 分区：数据库拆分 分片：分区分配给不同的节点 数据复制 数据分区 事务 分布式系统挑战 一致性与共识 派生数据 记录系统：真实数据系统，拥有数据的权威版本。 派生数据系统：从另一个数据系统获取，丢失可以根据数据源重建，如缓存等。 批处理系统 流处理系统