как лучше организовать контейнер для хранения IP адресов (1-3Mb)

Question

[Александр]

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

решение должно быть похожим на мемкеш
быстрым и эффективным!

вход IP — 32-bit число
выход — не более 64 байт — данные фиксированного размера
доп параметр — время доступа

Цель — проверить время последнего доступа.

возможные варианты:
1)
не хотелось бы для вытягивания информации об IP, сканировать всю таблицу адресов.
в этом случае вставка нового IP — вставка в пустой слот данных, вместо первого просроченного слота.
2)
упорядочивание по IP из-за высокой частотностностью обращения не подходит (а может подходит???).
ищем IP методом половинных делений. Если не нашли — вставляем. Какую модель хранения слотов использовать в этом случае?
3)
организовавыть очередь по времени доступа — получается скан всей (части начинающейся с первого не просроченного IP — до него — метод половинных делений) таблицы адресов.
дописываем в конец.

какие есть еще варианты????

Comments

[Dervish66]

Простите, на каком языке решается задача? Я правильно понял, что речь идет о С++?

[Александр]

задача будет решаться на С
но это не принципиально
нужен алгоритм

[Александр]

в качестве примера можно использовать и С++
можно найти исходники аналогов STL контейнеров

Answer 1

[Dervish66]

К одним и тем же данным Вам нужно обращаться двумя способами. Один способ — по IP, второй — по времени доступа. При этом необходимо чтобы поиск изменения в данных (смена IP в слоте данных и смена времени доступа) выполнялись быстро и эффективно.

Я бы решал эту задачу отделив сами данные (массив слотов) от индексов, через которые нужно обращаться. Если брать реализацию на С++ то примерно вот так:

// Описатель слота данных
struct CDataItem {
    __int64 accessTime; // Любое представление времени
    DWORD ip;
    BYTE  userData [64];
};

// Индекс по IP
std::map<DWORD, CDataItem *> ipIndex;

// Индекс по времени доступа
std::map<__int64, CDataItem *> accessIndex;

// Память для хранения массива слотов
CDataItem * dataArray = new CDataItem[32000];

При этом, конечно, после каждого изменения (обновления) слота придется обновлять индексы.

Comments

[Александр]

это хорошая идея, спасибо — я подумаю над реализацией
но весь фокус в том, что будет много разнообразных неповторяющихся IP
и будет много вставок (соответственно апдейтов индексов)
и еще надо будет следить за вытеснением…

Answer 2

[amc]

Не забывайте что IP адрес прекрасно представляется как 4-байтное число.

Comments

[Александр]

это мы даже хотим использовать
просто пока не решили как оптимальней

[Павел Загребелин]

Стоит ли в 2010 году делать приложение, которое стойко уверено в четырёхбайтовости ip-адреса?

[eternals]

> Стоит ли в 2010 году делать приложение, которое стойко уверено в четырёхбайтовости ip-адреса?
О! Обнаружен интеллект!
Я бы только добавил, что уже почти в 2011-м.

[amc]

Товарищи интеллектуалы, а вы уверенны что там будет v6?

[amc]

Тем более автор указал, какой битности у него будет адрес :)

Answer 3

[outself]

Для быстрого поиска, как индекс, можно использовать Фильтр Блума ( en.wikipedia.org/wiki/Bloom_filter )

И Chrome использует фильтры Блума для предварительной оценки того, является ли веб-сайт вредоносным. На практике, — Компактное хранение миллиона адресов в ~ 18-ти мегабайтах.

Comments

[Александр]

ну миллион адресов мне не нужно,
у меня планируется 50, макс 100 тыс посетителей в сутки
т.е. максимально нужно хранить 100 тыс. слотов —

за идею спасибо — почитаю

Answer 4

[Dervish66]

Вряд ли найдется контейнер, который обеспечивал бы эффективный доступ к данным сразу по двум индексам. Зато вместо std::map можно использовать что угодно, например, сбалансированные деревья, тем более что код будет писаться на С. Главная идея моего предложения — разнести индексы и сами данные. Тогда издержки на поиск слотов, вставки слотов и апдейтов индексов можно постараться свести к минимуму.

Вытеснение тоже реализуется довольно просто: по индексу времени доступа находим слот с самым минимальным значением времени доступа (самый давнишний) и заменяем в нем все поля. При этом, конечно, придется обновить оба индекса.

Обновление индекса можно сделать через удаление индексной записи и добавление новой.

Comments

[Dervish66]

Упс, предполагалось что это будет комментарий к предыдущему ответу. Извините.

[Александр]

Вытеснение тоже реализуется довольно просто: по индексу времени доступа находим слот с самым минимальным значением времени доступа (самый давнишний) и заменяем в нем все поля. При этом, конечно, придется обновить оба индекса.

думаю это частая, но тяжелая операция
надо будет как-то запускать ее по реже
например по таймауту…

[Александр]

Обновление индекса можно сделать через удаление индексной записи и добавление новой.

вставка в данном случае операция тяжелая???

[Dervish66]

А зачем Вам вообще нужно вытеснение?

Вставка в двоичное сбалансированное дерево — довольно дешевая операция. Расход времени на добавление нового узла в это дерево состоит из двух частей: поиск места для вставки нового узла и балансировка дерева после вставки. Поиск места по расходу времени примерно аналогичен методу половинных делений, а балансировка дерева состоит в переназначении некоторых указателей в дереве. Дешево и сердито.

Аналогично и с удалением: расходы на удаление состоят из поиска удаляемого элемента, operator delete и балансировка дерева после удаления.

Вообще по сбалансированным деревьям можно почитать уйму материалов в интернете начиная со статей на Хабре и заканчивая Википедией. А в гугле можно найти и реализацию этих деревьев.

[Александр]

спасибо
про деревья я в курсе, но присматрюсь к ним повнимательней!

Answer 5

[shsmad]

а чем собственно не подошел описаный вами же memcached?

Comments

[Александр]

нужно embed решение
будет реализовано как модуль WEB сервера
дергать на какждый запрос мемкеш — глупо

можно вытащить из исходников мемкеша и реализовать только один контейнер
но контейнер мемкеша оптимизирован под другие задачи — хранение средних блоков информации, ориентированные на частое чтение. контейнер мемкеша начинает тупить при частых вставках.

У меня блоки информации маленькие, доступ должен быть быстрым. и вставка информации — тоже.

[shsmad]

мемкэш какбэ и придумывался, чтоб его часть и много дергать… в любом случае хранить данные выгодно в памяти

Answer 6

[eternals]

Если типовые инструменты нельзя использовать, то постройте простейшее бинарное дерево. Лочить при перестроении отдельные ноды.

Comments

[Александр]

а есть типовые инстурменты?

[eternals]

СУБД, «словарь» и прочее.

Answer 7

[catap]

Смесь LRU кеша и какого-нибудь radix32 дерева

Comments

[Александр]

спасибо, почитаю

Answer 8

[Александр]

заинтересованным, решил делать так:

поиск по IP структура в виде b-Tree
далее проверка на время
времена хранятся в ввиде обратного списка
вытесняется самый последний в очереди.

При обновлении IP — переносим значение эл-та в конец списка.