日志结构合并树（Log-Structured Merge-Tree）：基于合并和压缩排序文件原理的存储引擎通常都被称为 LSM 存储引擎。
压缩排序文件基于排序字符串表：SSTables。
LSM-Tree 基本思想：保存在后台并合并的排序字符串表：SSTables。即使数据集远远大于可用内存，仍然能够正常工作。 基于有序的特性，可以有效的执行区间查询，并且由于磁盘是顺序写入，所以 LSM-Tree 可以支持非常高的写入吞吐量。
tags: Starcoin Web3 StarTrek,Sparse Merkle Tree,Merkle tree,LSM-Tree,Account-Model Blockchain Systems source: Gao, Zhenhuan, Yuxuan Hu, and Qinfan Wu. “Jellyfish Merkle Tree,” n.d., 12. JMT(Jellyfish Merkle Tree) a LSM-tree based Implementation of Sparse Merkle Tree Inspired by Patricia Merkle Tree and has been implemented in Rust, but it is language-independent. Merkel tree fits pretty well as an authenticated key-value store holding a huge amount of data in a tamper-proof way. Two major concerns where people have been trying to achieve some enhnacements:...
AMQP/JMS 风格的消息代理 将单个消息分配给消费者，消费者在成功处理后确认每条消息。消息被确认后从代理中删除。 适合作为一种异步 RPC。 RabbitMQ ActiveMQ HornetQ Qpid TIBCO Enterprise MEssage Service IBM MQ Azure Service Bus Google Cloud Pub/Sub 多个消费者 负载均衡式 每一条消息都只被传递给其中一个消费者。 扇出式 每条消息都被传递给所有消费者。 确认和重新传递 为了确保消息不会丢失，消息代理使用确认：客户端必须在处理完消息后显式的告诉代理，以便代理可以将其从队列中移除。 如果客户端的连接关闭或超时，而代理没有收到确认，则认为消息未处理，因此它将消息重新传递给另一个消费者。 消息顺序性 即使消息代理试图保留消息顺序（标准要求），负载均衡与重新传递的组合也不可避免地导致消息被重新排序。 基于日志的消息代理 代理将分区中的所有消息分配给相同的消费者节点，并始终以相同的顺序发送消息。 通过分区机制来实现并行（写在多个磁盘上突破磁盘带宽），消费者通过检查他们处理的最后一条消息的偏移量来跟踪进度。 代理将消息保存在磁盘上，因此如果有必要，可以回退并重新读取旧消息。 代表性的有： Kafka Amazon Kinesis Streams Twitter DistributedLog 基于日志的消息存储 参照 LSM-Tree 和 B-tree 的 WAL，可以使用相同的结构来实现消息代理： 生产者通过将消息追加到日志的末尾来发送消息，消费者通过依次读取日志来接收消息。 如果消费者读到日志的末尾，它就开始等待新消息被追加的通知。 通过对日志进行分区突破单个磁盘所能体能的带宽吞吐上线。 代理为每个消息分区分配了一个单调递增的序列号或偏移量，保证了分区内的消息完全有序。 消费者偏移量：记录哪些消息已经被处理，减少 ACK 开销 磁盘空间：分段，定期删除 消费者跟不上生产者：增加 LAG 报警 重新处理消息：重置偏移量
基于 Hadoop 分布式文件系统使用 SSTables 和 LSM-Tree 实现随机访问的 OLTP 数据库。
tags: Bigdata Hadoop Distributed File System MapReduce MapReduce shuffle 按照 reducer 分区，排序和将数据分区从 mapper 复制到 reducer。（令人困惑的术语，并不完全与洗牌一样，在 MapReduce 中其实没有随机性）。 MapReduce 的分布式执行 Hadoop MapReduce 并行化基于数据分区实现： 输入：通常是 HDFS 中的一个目录。 分区：每个文件或文件块都被视为一个单独的分区。 处理：每个分区由单独的 map 任务来处理。 每个 mapper 都会尽量实现计算靠近数据。 代码复制：JAR 文件。 Reduce 任务的计算也被分隔成块，可以不必与 mapper 任务数量相同，MapReduce 框架使用关键字的哈希值来确保具有相同关键字的键值对都在相同的 reduce 任务中处理。 键值对必须进行排序，排序是分阶段进行的： 每个 map 任务都基于关键字哈希值，按照 reducer 对输出进行分块。 每个分区都被写入 mapper 程序所在的本地磁盘上的已排序文件，参见 SSTables 和 LSM-Tree。 reducer 与每个 mapper 相连接：MapReduce 调度器会在 mapper 写入经过排序的输出文件后，通知 reducer 开始从 mapper 中获取输出文件，框架进行 MapReduce shuffle。 reducer 任务从 mapper 中获取文件并将它们合并在一起，同时保持数据的排序。不同 mapper 使用相同的关键字生成记录，会在合并后的 reducer 输入中位于相邻的位置。 reducer 可以使用任意逻辑来处理这些记录，并且生成任意数量的输出记录。记录被写入分布式文件系统中的文件。 MapReduce 工作流调度器 Oozie Azkaban Luigi Airflow Pinball 对比分布式数据库 MapReduce 中的并行处理和并行 join 算法已经在十多年前所谓的大规模并行处理（MPP）数据库中实现了。...
存储引擎 哈希索引 日志结构存储引擎：LSM-Tree 面向页的存储引擎：B-trees 对比 LSM-Tree 和 B-trees 项目 LSM-Tree B-trees 备注 性能 写入更快，吞吐更高 读取更快 具体场景上需要进行基准测试 存储 可变大小的段，通常 nMB 固定大小的页，传统 4KB 写入 追加，写入更多不利于 SSD 新的数据覆盖磁盘上旧的页 并发控制 后台合并进行原子替换 锁存器 其他索引结构 在索引中存储值 多列索引 全文索引和模糊索引 在内存中保存所有内容 优点：可以支持更复杂的数据结构，而无需考虑数据存储结构。 事务处理与分析处理 事务处理：OLTP 分析处理：OLAP 对比 属性 OLTP OLAP 主要读属性 基于键，每次查询返回少量记录 对于大量记录进行汇总 主要写属性 随机访问，低延迟写入用户的输入 批量导入（ETL）或事件流 典型使用场景 终端用户，通过网络应用程序 内部分析师，为决策提供支持 数据表征 最新的数据状态（当前时间点） 随着事件而变化的所有事件历史 数据规模 GB 到 TB TB 到 PB 数据仓库 星型与雪花型分析模式 星型模型也称为维度建模。 列式存储 列压缩