用於存儲僅追加消息的數據結構和文件結構？

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，以便您可以在文件全部過期時刪除該文件。

這是一個相當低技術的解決方案，但你可以在一天內編寫它，它的工作原理和性能出奇的好。我已經在幾個項目中使用它，效果很好。