Самый длинный поиск префикса с диска

Question

В настоящее время у меня есть некоторая реализация, которая выполняет Longest Prefix Lookup (LPM) из структуры данных радикального дерева. Эта структура данных содержит префиксы IP (основополагающее дерево с максимальной глубиной 128 бит), и в настоящее время она полностью сохраняется в памяти. Данные доступны только для чтения и никогда не изменяются.

К сожалению, данные стали больше, и я больше не могу хранить их в памяти. Я ищу эффективную структуру данных, которая может быть сохранена на диске и обеспечит эффективный поиск. Я планирую использовать какой-то механизм кэширования поверх этого.

Answer 1

эффективная структура данных, которая может храниться на диске и обеспечивает эффективный поиск

Похоже, проблема XY для меня:

1. Мы говорим об IPv6 (128 бит).
2. Мы говорим о маршрутизации IPv6 (Longest Prefix Match).
3. Для соединения со скоростью 10 Гбит / с может быть до 14,8 миллионов поисков маршрута в секунду.
4. Согласно общедоступным данным, на данный момент существует около 50 тыс. Префиксов IPv6.

Если вышеприведенные предположения верны, нам нужно хранить 50К раз 128 бит = 800КБ в радикальном дереве. Это должно легко вписаться в память.

Нам нужно искать эти данные миллионы раз в секунду. Размещение данных на диске замедляется на порядок.

Я думаю, что ваш вопрос не является коренной проблемой, поэтому, пожалуйста:

1. Включите информацию о более широкой картине вместе с любым попытанным решением.
2. Если есть другие решения, которые вы уже исключили, расскажите, почему вы их исключили. Это дает больше информации о ваших требованиях.

ОБНОВИТЬ:

Таким образом, это 2M просмотров IPv6 в час через 20M только для чтения набора префиксов IPv6. Мы до сих пор не знаем, что это за префиксы 20M, так как с практической точки зрения префиксов во всем Интернете не так много. Но в любом случае.

1. 2M просмотров / час составляет ~550 просмотров / сек. Согласно Википедии, традиционные (механические) жесткие диски не могут выдержать такую ​​нагрузку. Поэтому нам нужен SSD-накопитель для хранения базы данных.

2. Согласно Википедии, B-деревья являются хорошими структурами для внешнего поиска.

3. Согласно Википедии, файлы с отображением в памяти используют небольшие объемы ОЗУ даже для очень больших файлов.

Собираем все биты вместе. Эти 20M префиксы IPv6 должны быть организованы как B-дерево с размером узла PAGE_SZIE (обычно 4 КБ) и отображается в виртуальном адресном пространстве процесса. Кеш будет управляться операционной системой, поэтому никакого другого механизма кеширования не требуется.