预写日志

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 报警 重新处理消息：重置偏移量

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 进行崩溃恢复，修改的页被写入不同的位置，树中父页的新版本被创建，并指向新的位置。 保存键的缩略信息，可以压入更多的键，保持更高的分支因子，减少层数。 对树进行布局，相邻叶子页按顺序保存在磁盘。 添加额外的指针到树中，如左右兄弟页。 变体，如分形树：借鉴日志结构减少磁盘寻道。