Самый эффективный способ реализации BlackList

Question

Я разрабатывал Ip-фильтр и догадывался, как можно, используя любой тип структуры данных esque, разработать ОЧЕНЬ эффективный и быстрый фильтр BlackList.

То, что я хочу сделать, - это просто, каждое входящее / исходящее соединение, которое я должен проверить в списке заблокированных IP-адресов.

IP-адреса разбросаны, и использование памяти должно быть линейным (не зависит от количества заблокированных списков, потому что я хочу использовать в ограниченных системах (доморощенные маршрутизаторы)).

У меня есть время и я могу создать что угодно с нуля. Трудность не важна для меня. Если вы можете использовать что-нибудь, что вы должны делать?

Answer 1

«Самый эффективный» - это сложный термин для количественной оценки. Ясно, что если бы у вас было неограниченное количество памяти, у вас была бы корзина для каждого IP-адреса, и вы могли бы сразу индексировать ее.

Распространенным компромиссом является использование структуры данных типа B-дерева. Контейнеры первого уровня могут быть предварительно установлены для первых 8 битов IP-адреса, которые могут хранить указатель и размер списка, содержащего все в настоящее время заблокированные 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-адресов с одинаковыми битами высшего порядка.

Answer 2

Одним из способов повышения производительности такой системы является использование фильтра Блума.Это вероятностная структура данных, занимающая очень мало памяти, в которой возможны ложные срабатывания, а ложные отрицания - нет.

Когда вы хотите посмотреть IP-адрес, вы сначала проверяете фильтр Bloom.Если есть промах, вы можете сразу разрешить движение.Если есть попадание, вам нужно проверить свою авторитетную структуру данных (например, хеш-таблицу или дерево префиксов).

Вы также можете создать небольшой кэш «обращений в фильтре Блума, но фактически разрешенных» адресов, чтобыпроверяется после фильтра Блума, но перед авторитетной структурой данных.

По сути, идея состоит в том, чтобы ускорить быстрый путь (разрешенный IP-адрес) за счет медленного пути (запрещенный IP-адрес).

Answer 3

Hashtables это путь. Они имеют среднюю O (1) сложность для поиска, вставки и удаления! Они, как правило, занимают больше памяти, чем деревья, но гораздо быстрее.

Поскольку вы работаете только с 32-битным целым числом (вы, конечно, можете конвертировать IP в 32-битное целое), все будет удивительно просто и быстро.

Вы можете просто использовать отсортированный массив. Стоимость вставки и удаления равна O (n), но поиск равен O (log n), и особенно объем памяти составляет всего 4 байта для каждого ip. Реализация очень проста, возможно, слишком много: D

Двоичные деревья имеют сложность O (log n) для поиска, вставки и удаления. Однако простого бинарного дерева было бы недостаточно, вам нужно дерево AVL или красное черное дерево, которое может быть очень раздражающим и сложным для реализации. Деревья AVL и RBT могут уравновешивать себя, и нам это нужно, потому что несбалансированное дерево будет иметь наихудшую временную сложность O (n) для поиска, что аналогично простому связанному списку!

Если вместо одного и уникального IP-адреса вам нужно запретить диапазоны IP-адресов, возможно, вам нужна Патриция Три, также называемая Radix Tree, они были изобретены для словарей и словарей IP. Тем не менее, эти деревья могут быть медленнее, если не хорошо написаны \ сбалансированы. Hashtable всегда лучше для простых поисков! Они слишком быстрые, чтобы быть реальными:)

Теперь о синхронизации:

Если вы заполняете черный список только один раз при запуске приложения, вы можете использовать простую хэш-таблицу только для чтения (или основное дерево), у которой нет проблем с многопоточностью и блокировкой.

Если вам нужно обновлять его не очень часто, я бы посоветовал вам использовать блокировки чтения-записи.

Если вам нужны очень частые обновления, я бы посоветовал вам использовать параллельную хеш-таблицу. Предупреждение: не пишите свои собственные, они очень сложные и подвержены ошибкам, найдите реализацию в Интернете! Они часто используют (относительно) новые атомарные операции CAS новых процессоров (CAS означает «Сравнить» и «Поменять местами»). Это специальный набор инструкций или последовательность инструкций, которые позволяют сравнивать и заменять 32-битные или 64-битные поля в памяти за одну атомарную операцию без необходимости блокировки. Их использование может быть сложным, потому что вы должны очень хорошо знать свой процессор, свою операционную систему, свой компилятор и сам алгоритм, что противоречит интуиции. См. http://en.wikipedia.org/wiki/Compare-and-swap для получения дополнительной информации о CAS.

Было изобретено параллельное дерево 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-адреса вам нужно 4 байта для IP-адреса и указателя. Вам также нужен большой массив указателей (или 32-битных целых чисел с некоторыми хитростями), размер которых должен быть простым числом больше, чем количество элементов, которые должны быть сохранены. Hashtables, конечно, может также изменять свой размер, если требуется, но они могут хранить также больше элементов, чем эти простые числа, за счет более медленного времени поиска.

Как для деревьев, так и для хеш-таблицы сложность пространства линейна.

Я надеюсь, что это многопоточное приложение, а не многопроцессорное (fork). Если это не многопоточность, вы не можете быстро и надежно разделить часть памяти.