用于存储仅追加消息的数据结构和文件结构？

Question

消息是具有唯一消息ID（整数）的可变大小的数据包。我想有一个设计/数据结构/算法：

1. 能够有效地存储磁盘上的消息，消息的数量可以非常大，长度是可变的。但没有更新或修改存储的。
2. 能够检索带有消息ID的消息，即返回存储的消息。
3. 最近存储的消息比旧的更经常查询
4. 每条信息都有一个TTL，需要一种方法来截断旧的消息

什么是合适的数据结构和文件结构，这需要的文件？

Answer 1

如果我们每秒讲五封邮件，那么您每天的谈话量就是五十万条。

我过去所做的是维护多个文件。如果消息的TTL以天来衡量，那么我每天有一个消息文件。读取和存储消息的过程会为新的第一天的消息创建一个新文件。通过记录收到最后一条消息的日期和时间，这很容易实现。

我还为每个消息文件维护一个配对索引文件。这也是一个简单的顺序文件，它包含每个消息的消息ID和位置。因此，要查找特定日期的消息，请加载当天的文件，对消息ID执行二进制搜索，然后使用相应的位置在消息文件中查找消息。如果消息ID是连续的并且没有数字丢失，那么在索引内查找应该非常快。如果您可以缺少数字，那么二分查找效果很好。只有512K的消息，二进制搜索将会非常快。

要处理多个日期，您需要查找程序的启动顺序扫描所有日常消息索引的目录，并构建一个元索引，其中包含每天第一条消息的ID。

要删除旧邮件，您需要查找程序在启动时删除旧文件，或者每天午夜删除旧文件。那时它也可以在第二天的文件中获得第一条消息的ID。

或者，消息收集器可以生成一个任务，以便在收到第一个消息时删除旧文件。您还可以让它通知新的一天的查找程序，以便查找程序可以更新其元索引。每天只有512K的消息（每秒5次约为每天50万次），你应该可以在内存中保留10天的索引条目，而不会出现任何问题。您的索引将包含消息ID和文件偏移量，因此每个条目的图16字节。 10天时间500万，就像80兆字节：口袋变化。要删除旧条目（每天一次），只需从内存中删除当天的索引。

如果消息有不同的TTL，那么你保留旧的消息但跟踪他们的TTL。当有人查找过期的消息时，您必须在返回之前对过期日期进行第二次检查。当然，您必须跟踪每天的最长TTL，以便您可以在文件全部过期时删除该文件。

这是一个相当低技术的解决方案，但你可以在一天内编写它，它的工作原理和性能出奇的好。我已经在几个项目中使用它，效果很好。