Эффективный способ подсчета количества посещений в диапазоне IP и временном диапазоне

Question

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

Например, у нас есть 10 ¹² запросов в следующем формате:

(IP-адрес, время посещения)

Предположим, мы хотим знать, какмного посещений было из диапазона IP [10.12.72.0, 10.12.72.255] в течение 14:00 и 16:00.

Единственные идеи-кандидаты, о которых я могу подумать:

(1) использовать B-TREE для индексации этого большого набора данных, используя одно измерение, например, построить B-TREE на параметре IP,Используя этот B-TREE, мы можем быстро получить количество запросов, поступающих из любого определенного диапазона IP-адресов, но как мы можем узнать, сколько из этих посещений происходит между 14:00 и 16:00?

(2) использовать BITMAP, но аналогично B-TREE, из-за требований к пространству BITMAP может быть построен только на одном измерении, например, IP-адресе, мы не знаем, сколько из этих запросов выданомежду 14:00 и 16:00.

1016 * Есть ли эффективный алгоритм, спасибо?Количество запросов может быть довольно большим

Answer 1

Ваш первый шаг - выяснить, какая точность вам нужна ...

ВРЕМЯ:

• Вам нужны отметки времени с точностью до миллисекунды или с точностью до часа?
• • Количество часов с 1970 года может составлять менее миллиона, 3 байта ~ целое число
• • Количество миллисекунд и вам нужно 8 байт ~ длиной

IP:

• Все ли ваши IP версии v4 (4 байта) или v6 (16 байтов)?
• Будете ли вы когда-нибудь искать по определенному IP или будете использовать только диапазоны IP-адресов?
• • Если последнее, вы можете просто использовать класс C для каждого IP 123.123.123.X (3 байта)

Предполагая, что:

• Достаточно точна 1 час времени
• 3 байта IP класса C достаточно хороши

Реорганизация ваших данных (2 возможных структуры выбирают одну):

База данных:

• Вы можете использовать реляционную базу данных
• • Таблица: Хиты
• • • IPClassC INT НЕКЛАСТЕРНЫЙ ИНДЕКС
• • • TimeHrsUnix INT НЕКЛАСТЕРНЫЙ ИНДЕКС
• • • Подсчет БОЛЬШОГО ЗНАЧЕНИЯ ПО УМОЛЧАНИЮ (1)

Плоские файлы:

• Вы можете использовать больше плоских файлов
• • Имейте 1 плоский файл для каждого IP класса C, который появляется в ваших журналах (максимум 2 ^ 24)
• • • Каждый файл имеет размер 8B (большой int) * 1MB (часы с 1970 по 2070 годы) = 8MB

Как загрузить новую структуру данных:

База данных:

• Разобрать ваши журналы (читать в памяти по одной строке за раз)
• Преобразование записи в 3-байтовый IP и 3-байтовое время.
• Преобразуйте ваш IP-класс C в целое число, а время в часах - в целое число
• ЕСЛИ СУЩЕСТВУЕТ (ВЫБРАТЬ * ИЗ ХИТОВ, ГДЕ IPClassC = @IP AND TimeHrsUnix = @Time)
• • ОБНОВЛЕНИЯ Хиты УСТАН. Количество = Количество + 1, ГДЕ IPClassC = @IP AND TimeHrsUnix = @ Время
• прочее
• • INSERT INTO Hits VALUES (@IP, @Time)

Плоские файлы:

• Разобрать ваши журналы (читать в памяти по одной строке за раз)
• Преобразование записи в 3-байтовый IP и 3-байтовое время.
• Преобразуйте ваш IP в строку, а ваше время в целое число
• если File.Exist (IP) = False
• • File.Create (IP)
• • File.SetSize (IP, 8 * 1000000)
• CountBytes = File.Read (IP, 8 * Time, 8)
• NewCount = Convert.ToLong (CountBytes) + 1
• CountBytes = Convert.ToBytes (NewCount)
• File.Write (IP, CountBytes, 8 * Time, 8)

Запрос новых структур данных:

База данных:

• ВЫБЕРИТЕ СУММУ (количество) ИЗ ХИТОВ, ГДЕ IPClassC МЕЖДУ @IPFrom И @IPTO И TimeHrsUnix МЕЖДУ @TimeFrom AND @ TimeTo

Плоский файл:

• Всего = 0
• Смещение = 8 * Время от
• Len = (8 * TimeTo) - смещение
• для IP = IP от IP до
• • Если File.Exist (IP.ToString ())
• • • CountBytes = File.Read (IP.ToString (), Offset, Len)
• • • LongArray = Convert.ToLongArray (CountBytes)
• • • Всего = Всего + Математическая сумма (LongArray)
• следующий IP

Некоторые дополнительные советы:

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

Answer 2

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

Answer 3

10 ^ 12 - большое число (TERA) - конечно, слишком большое для обработки в памяти.Я хотел бы сохранить это в реляционной базе данных со звездообразной схемой, использовать измерение времени и предварительно агрегировать по времени суток (например, часовые полосы), IP-подсетям и другим интересующим вас критериям.