實現BlackList的最有效的方法

我開發了一個Ip過濾器，並且猜測如何使用任何類型的esque數據結構開發一個非常高效和快速的BlackList過濾器。實現BlackList的最有效的方法

我想要做的事情很簡單，我必須檢查阻止的IP列表中的每個傳入/傳出連接。

IP分散，內存使用應該是線性的（不依賴於阻塞列表的數量，因爲我想在有限的系統（自制軟件路由器）上使用）。

我有時間並且可以創建零之間的任何東西。困難對我來說並不重要。如果你可以使用任何東西，你應該做什麼？

來源

2011-10-26 bratao

如果你變得更具體，例如，它會非常有幫助。描述一些性能將很重要的場景。如果需要，它將完全採用不同的實現。你是針對整個IP範圍，如果你的目標是「分散的」單個IP地址。 – Jon

謝謝jon提示，我指定了更多！ – bratao

如果內存使用量保持不變，那麼很明顯會對黑名單中可能存在的最大IP數量施加限制。 –

提高此類系統性能的一種方法是使用Bloom Filter。這是一種概率數據結構，佔用很少的內存，其中可能出現誤報，但是假陰性則不可能。

當你想查找一個IP地址，你首先檢查在布隆過濾器。如果有一個錯過，你可以立即允許交通。如果遇到問題，您需要檢查您的權威數據結構（例如哈希表或前綴樹）。

您還可以創建一個小的緩存「在布隆過濾器命中，但實際上允許」地址，在布隆過濾器後，但在權威數據結構之前被選中。

基本思路是加快在慢速路徑的代價（允許的IP地址）的快速路徑（IP地址被拒絕）。

來源

2011-10-27 05:14:37 caf

Thnak你，那就是我想要的。 – bratao

散列表是要走的路。他們平均O（1）查找，插入和刪除的複雜性！他們往往比樹木佔用更多的內存，但速度要快得多。

由於您只是使用32位整數（當然，您可以將IP轉換爲32位整數），事情會非常簡單快速。

您可以使用排序後的數組。插入和移除成本是O（n），但查找是O（log n），特別是每個ip的內存僅爲4個字節。實現非常簡單，可能太多了：D

二叉樹的複雜度爲O（log n），用於查找，插入和刪除。但是，一個簡單的二叉樹是不夠的，你需要一個AVL樹或一個紅黑樹，這可能非常煩人而且很難實現。 AVL和RBT樹能夠自我平衡，我們需要這樣做，因爲不平衡樹的查找時間複雜度爲O（n），這與簡單的鏈表相同！

如果不是單一和唯一的IP你需要禁止IP範圍，可能你需要一個Patricia Trie，也稱爲基數樹，它們是爲詞典和IP詞典而發明的。但是如果寫得不好，平衡的話，這些樹可能會變慢。對於簡單的查找，散列表總是更好！他們太快是真實:)

現在關於同步：

如果您在應用程序啓動填補了黑名單隻有一次，你可以用一個簡單的只讀哈希表（或基數樹），唐」沒有關於多線程和鎖定的問題。

如果您需要不經常更新它，我建議您使用讀寫器鎖。

如果你需要非常頻繁的更新，我會建議你使用併發散列表。警告：不要自己寫，它們非常複雜，容易出錯，在網上找到一個實現！他們使用很多（相對）新的原子CAS操作的新處理器（CAS意味着比較和交換）。這些是一組特殊的指令或指令序列，它們允許比較內存上的32位或64位字段，並在單個原子操作中進行交換，而無需鎖定。使用它們可能很複雜，因爲你必須非常清楚你的處理器，操作系統，編譯器和算法本身是否違反直覺。有關CAS的更多信息，請參閱http://en.wikipedia.org/wiki/Compare-and-swap。

併發AVL樹被髮明，但它是如此複雜，我真的不知道該說這些:)例如什麼，http://hal.inria.fr/docs/00/07/39/31/PDF/RR-2761.pdf

我剛剛發現，併發基數樹存在： ftp://82.96.64.7/pub/linux/kernel/people/npiggin/patches/lockless/2.6.16-rc5/radix-intro.pdf但也很複雜。

並行排序數組不存在，當然，你需要更新一個讀寫鎖。

也是內存來處理非併發哈希表所需要的量可以說是相當少考慮：對於每個IP您需要的IP和指針4字節。你還需要一個大數組指針（或一些技巧的32位整數），其大小應該是比應該存儲的項目數大的素數。當需要時，如果需要，哈希表當然也可以調整自己的大小，但是它們可以存儲比該素數更多的項目，代價是查找速度較慢。

對於樹和散列表，空間複雜度都是線性的。

我希望這是一個多線程的應用程序，而不是多進程應用程序（叉）。如果不是多線程，則不能以快速可靠的方式共享部分內存。

來源

2011-10-26 23:36:15

「最高效」是一個難以量化的術語。顯然，如果你有無限的內存，你將有一個垃圾箱爲每個IP地址，並可以立即索引到它。

一個常見的折衷是使用B樹型數據結構。第一級容器可以預設爲IP地址的前8位，這可以存儲指向包含所有當前阻止的IP地址的列表的大小和大小。第二個列表將被填充以防止不必要的memmove()調用並可能排序。（具有大小和在存儲器中列表的長度允許的列表中輕微昂貴的插入時間上就地二進制搜索。）

例如：

127.0.0.1 =insert=> { 127 :: 1 } 
127.0.1.0 =insert=> { 127 :: 1, 256 } 
12.0.2.30 =insert=> { 12 : 542; 127 :: 1, 256 }

這樣的開銷數據結構最小，總存儲大小是固定的。顯然，最壞的情況將是具有相同最高位的大量IP地址。

來源

2011-10-26 23:49:03 utopianheaven

實現BlackList的最有效的方法

回答

相關問題