最佳的數據結構基於價值

Question

我工作的一個項目，我想出來的天空爲樂趣，以更好地瞭解二郎，藥劑和功能性數據結構。我正在問這個問題，以獲得有關以下場景的最佳數據結構的一些洞察，以作爲學習練習，並查看標準庫中是否存在滿足以下場景的單個理想候選者。

我希望保存在內存中存儲。我想知道哪種後臺數據結構適合以下場景的用途：

• 可能有數萬（或更多）條目。
• 頻繁插入和更新每個條目。
• 週期性掃描（認爲GC運行）刪除無用的項目（例如項目未更新最後X秒內）
• 查詢產生子集（例如在過去的X秒內全部更新）

一些背景資料：

• 客戶端服務器方案，其中每個連接的客戶端對應於後備存儲器，其中鍵是客戶端ID的單個條目。
• 每個客戶端會每隔x秒發送更新的數據。 （經常）
• 當客戶端斷開後臺存儲中的項目時將被刪除。如果它沒有在過去的X秒更新
• 後備存儲器中的每個條目也將被刪除。 （要處理刪除舊數據時，沒有收到斷開連接）目前我使用的是HashDict支持的過程，是一個最簡單的一件事，明知有可能是一個潛在的大量條目

，而這將允許快速隨機訪問更新，因爲密鑰將對應於客戶端ID。目前的值是一個Map，它本身將包含「last_updated」時間。

Answer 1

如果計劃具有大量併發連接的客戶端的，然後使用一個單一的過程可以呈現瓶頸。相反，您可以使用ETS表來存儲您的數據。這將允許更好的CPU使用率，因爲多個客戶端可以同時查詢和修改表。

解決這個問題的一種方法是使用每個客戶端的GenServer以及底層依賴於ETS的庫來爲進程提供豐富的別名。所以你可以給你的客戶特定的進程名稱，如{client, 1},{client, 2}等等。然後，當請求到達時，您首先嚐試通過gproc找到客戶端，如果它不存在，則創建它。後一部分必須經過一個明確的單體過程，以避免競爭條件。一旦找到客戶，您只需向該客戶提出請求。

可以實現針對客戶端的過程中，超時邏輯。基本上，從你的handle_ *和init回調中，你可以指定以毫秒爲單位的超時時間。如果新消息沒有在給定時間內到達，您的客戶端進程將收到一條超時消息，您可以在handle_info中處理該消息，並讓接收進程停止。一旦進程停止，它將自動從gproc註冊表註銷。在監督樹中，這些過程顯然應該是臨時工或臨時工，以防止主管重新啓動它們。

另一種選擇是將所有內容都保存在ETS中，而不依賴於客戶端進程。 GC未使用的條目需要某種到期邏輯，並且這是手動完成的。簡單的強力方法是定期遍歷整個表並刪除舊條目。或者你可以設計更聰明的東西。我在以前的項目中使用了這種技術的一個版本，並提供了一個幫助庫here。