快速查找和持久性

Question

場景數據結構的優化存儲

我有以下幾種方法：

public void AddItemSecurity(int itemId, int[] userIds) 
public int[] GetValidItemIds(int userId) 

起初我想在表單上存儲：

itemId -> userId, userId, userId 

和

userId -> itemId, itemId, itemId 

AddItemSecurity基於我如何從第三方API獲取數據，GetValidItemIds是我想如何在運行時使用它。

有潛在的2000個用戶和1000萬個項目。 商品標識的格式爲：2007123456,20100（10位數字，前四位代表年份）。

AddItemSecurity不一定要執行超快速，但GetValidIds需要亞秒。另外，如果現有的itemId上有更新，我需要刪除不再在列表中的用戶的itemId。

我在想如何以最佳的方式存儲這個。最好在磁盤上（使用緩存），但我希望代碼可以維護和清潔。

如果項目ID從0開始，我想爲每個用戶創建一個長度爲MaxItemId/8的字節數組，並且如果項目存在或不存在，則設置true/false位。這會將陣列長度限制在每用戶1mb以下，並提供快速查找以及更新每個用戶列表的簡單方法。通過堅持這個爲Memory Mapped Files與.Net 4框架，我想我也會得到體面的緩存（如果機器有足夠的內存），而不用自己實現緩存邏輯。解析ID，剝離年份，每年存儲一個數組可能是一個解決方案。

可以將ItemId - > UserId []列表直接序列化到磁盤，並使用正常FileStream進行讀/寫操作，以便在發生更改時保留列表並進行區分。

每次添加新用戶時，所有列表也必須更新，但是這可以在每晚進行。

問題

我應該繼續嘗試這種方法，還是應探索以及有其他路徑？我認爲SQL服務器的執行速度不夠快，而且會給開銷帶來負擔（至少如果託管在另一臺服務器上），但我的假設可能是錯誤的。任何關於此事的想法或見解都值得讚賞。我想嘗試去解決它無需增加太多的硬件:)

[更新2010-03-31]

在下列條件下我現在已經與SQL Server 2008進行測試。

• 表有兩列（用戶ID，項ID）都是詮釋
上兩列
• 增補
• 簇索引〜800.000項180層的用戶 - 144萬行總計
• 分配4GB RAM，用於SQL服務器
• 雙核2.66GHz的筆記本電腦
• SSD磁盤
• 使用SqlDataReader讀取所有的itemid的成列表
• 循環遍歷所有用戶

如果我運行一個線程，它的平均值爲0.2秒。當我添加第二個線程時，它會上升到0.4秒，這仍然可以。從那裏的結果正在下降。添加第三個線程會將查詢的數量增加到2個。第四個線程，最多4秒，第五個線程可以將查詢延伸到50秒。

即使在一個線程中，CPU仍在進行屋頂工作。我的測試應用程序需要一些由於快速循環，其餘的SQL。

這使我得出結論，它不會很好地擴展。至少不是在我測試過的硬件上。有沒有方法來優化數據庫，比如說每個用戶存儲一個int數組而不是每個項目的一個記錄。但是這使得刪除項目變得更加困難。

[更新2010-03-31＃2]

我做了一個快速測試與把它作爲內存映射文件的位相同的數據。它表現更好。六個線程的訪問時間在0.02s和0.06s之間。純粹的內存限制。映射文件由一個進程映射，並由六個人同時訪問。而作爲SQL基地採取4GB，在磁盤上的文件花費了23MB。

Answer 1

經過多次測試後，我最終使用內存映射文件，使用稀疏位（NTFS）標記它們，使用NTFS Sparse Files with C#中的代碼。

維基百科解釋了什麼是sparse file。

使用稀疏文件的好處是我不必關心我的id的範圍是什麼。如果我只寫在2006000000和2010999999之間的id，文件將只分配625,000字節從偏移250,750,000在文件。直到該偏移量的所有空間都未在文件系統中分配。每個ID都作爲一個位存儲在文件中。將其視爲位數組。如果id序列突然改變，那麼它將在文件的另一部分分配。

爲了檢索設置了哪個ID，我可以執行OS調用來獲取稀疏文件的分配部分，然後檢查這些序列中的每一位。同時檢查一個特定的ID是否設置非常快。如果它落在分配的塊之外，那麼它不在那裏，如果它落在內部，它只是一個字節的讀取和一個位掩碼檢查，看看是否設置了正確的位。

因此，對於您希望以儘可能快的速度檢查多個ID的特定場景，這是迄今爲止我找到的最優方式。

好的部分是內存映射文件也可以與Java共享（結果是需要的東西）。 Java也支持Windows上的內存映射文件，並且實現讀/寫邏輯相當簡單。

Answer 2

我真的認爲你應該在做出決定之前嘗試一個不錯的數據庫。從長遠來看，這樣的事情將是一個挑戰。你的用戶基數實際上很小。 SQL Server應該能夠處理你所需要的而沒有任何問題。

Answer 3

2000用戶不算太壞，但有10萬個相關項目，你真的應該考慮把它放到數據庫中。數據庫執行所有你需要的存儲，持久性，索引，緩存等，它們表現得非常好。

它們還可以提高未來的可擴展性。如果您突然需要處理兩百萬用戶，並且具有良好數據庫的數十億設置將會使擴展成爲一個非問題。