Производительность таблицы диапазонов IP-адресов

Ситуация

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

У вас есть пары начальных и конечных значений; каждый 'элемент' принадлежит такому 'диапазону'. Поэтому интуитивно вы создаете таблицу с началом и концом диапазона, а также информацией об элементе. Ваши запросы включают в себя условие WHERE, которое сравнивает значения, находясь между начальным и конечным значениями.

Проблема

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

Решение

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

Производительность

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

Представленное здесь решение обычно может получить необходимую информацию, извлекая одну строку или небольшое количество строк. Это порядок(1).

В большой таблице «подсчет попаданий в диск» является важной частью производительности. Поскольку используется InnoDB и используется первичный ключ (кластеризованный), большинство операций затрагивают только 1 блок.

Поиск 'блока', в котором находится заданный IP-адрес:

• Для начала блока: одно извлечение одной строки с использованием первичного ключа
• Для конца блока: то же самое. Запись, содержащая это, будет 'смежной' с другой записью.

Для выделения или освобождения блока:

• 2-7 SQL-запросов, обращающихся к кластеризованному первичному ключу для строк, содержащих и непосредственно смежных с блоком.
• Один SQL-запрос — это DELETE; если он обращается к стольким строкам, сколько необходимо для блока.
• Другие запросы обращаются к одной строке каждый.

Принципы проектирования

Это имеет решающее значение для проектирования и его производительности:

• Наличие только одного адреса в строке. Это были альтернативные конструкции; они, похоже, не были лучше и, возможно, хуже:
• Этот один адрес мог быть 'конечным' адресом.
• Параметры процедуры для 'блока' могли быть началом этого блока и началом следующего блока.
• Параметры IPv4 могли быть четырьмя точками; я выбрал, чтобы сохранить упрощенную реализацию эталонной реализации вместо этого.
• Параметры IPv6 — 32-значные шестнадцатеричные, поскольку это было проще, чем BINARY(16) или IPv5 для реализации эталонной реализации.

Интересная работа ведется с Ips, а не со второй таблицей, поэтому я сосредоточился на ней. Неудобства объединения со второй таблицей невелики по сравнению с приростом производительности.

Детали

Будут использоваться две, а не одна, таблицы. Первая таблица (`Ips` в эталонных реализациях) тщательно разработана для оптимизации всех основных операций, необходимых. Вторая таблица содержит другую информацию об 'владельце' каждого 'элемента'. В эталонных реализациях `owner` — это идентификатор, используемый для объединения двух таблиц. Эта дискуссия сосредоточена на `Ips` и том, как эффективно сопоставить IP(ы) с/из владельца(ов). Вторая таблица имеет «первичный ключ(владелец)».

В дополнение к схеме двух таблиц существует набор хранимых процедур для инкапсуляции необходимого кода.

Одна строка Ips представляет один 'элемент' путем указания начального IP-адреса и 'владельца'. Следующая строка указывает начальный IP-адрес следующего "блока адресов", тем самым косвенно предоставляя конечный адрес для текущего блока.

Отсутствие явного указания "конечного адреса" приводит к некоторым неудобствам. Хранимые процедуры скрывают это от пользователя.

Особому владельцу (указанному как '0') выделен 'свободный' или 'непринадлежащий' блок. Таким образом, нет проблем с разреженным выделением блоков адресов.

Ссылаясь ниже, приведены эталонные реализации IPv4 и IPv6. Вам нужно будет внести изменения для ситуаций, не связанных с IP, и, возможно, внести изменения даже для ситуаций с IP.

Вот основные предоставляемые хранимые процедуры:

• IpIncr, IpDecr — для добавления/вычитания 1
• IpStore — для выделения/освобождения диапазона
• IpOwner, IpRangeOwners, IpFindRanges, Owner2IpStarts, Owner2IpRanges — для поиска
• IpNext, IpEnd — IP начала следующего блока или конца текущего блока

Ни одна из предоставленных процедур не объединяется со второй таблицей; вы можете захотеть разработать пользовательские запросы, основанные на предоставленных эталонных хранимых процедурах.

Размер таблицы Ips пропорционален количеству блоков. Миллион 'владеемых' блоков может составлять 20-50 МБ. Это зависит от:

• количества 'свободных' пробелов (от нуля до количества принадлежащих блоков)
• типов данных, используемых для `ip` и `owner`
• накладных расходов InnoDB Даже 100 млн блоков вполне управляемы на современном оборудовании. После кэширования большинство операций занимают несколько миллисекунд. Миллиард блоков будет работать, но большинство операций будут обращаться к диску несколько раз — только несколько раз.

Эталонная реализация IPv4

Это относится к IPv4 (32 бита, типа «196.168.1.255»). Он может обрабатывать все, от 'ничего не назначено' (1 строка) до 'все назначено' (4Б строк) 'одинаково' хорошо. То есть задать вопрос «кто владеет «11.22.33.44»» одинаково эффективно независимо от того, сколько блоков IP-адресов существует в таблице. (Хорошо, кэширование, обращения к диску и т. д. могут немного повлиять.) Единственная функция, которая может варьироваться, — это функция, которая переназначает диапазон новому владельцу. Его скорость зависит от того, сколько существующих диапазонов необходимо обработать, поскольку эти строки будут удалены. (Это помогает, что они по структуре 'кластеризованные').

Примечания к Эталонной реализации IPv4:

• Внешне пользователь может использовать обозначение с точкой (11.22.33.44), но ему нужно преобразовать в INT UNSIGNED для вызова хранимых процедур.
• Пользователь отвечает за преобразование в/из вызывающий тип данных (INT UNSIGNED) при доступе к хранимой процедуре; предлагаю INET_ATON/INET_NTOA.
• Внутренний тип данных для адресов такой же, как и вызывающий тип данных (INT UNSIGNED).
• Добавление и вычитание 1 (простые арифметические операции).
• Тип данных 'владельца' (MEDIUMINT UNSIGNED: 0..16М) — измените, если необходимо.
• Адрес «За пределами конца» (255.255.255.255+1 — представлен как NULL).
• Таблица инициализируется одной строкой: (ip=0, owner=0), что означает, что «все адреса свободны. См. комментарии в коде для получения более подробной информации.

(Эталонная реализация не обрабатывает CDR. Добавьте ее, сначала преобразовав ее в диапазон IP-адресов.)

Эталонная реализация IPv6

Код для обработки IP-адресов сложнее, но общая структура такая же, как и для IPv4. Переходите к нему только в том случае, если вам нужен IPv6.

Примечания к эталонной реализации IPv6:

• Внешне IPv6 имеет сложную строку, VARCHAR(39) CHARACTER SET ASCII. Предоставляется хранимая процедура IpStr2Hex().
• Пользователь отвечает за преобразование в/из вызывающий тип данных (BINARY(16)) при доступе к хранимой процедуре; предлагаю INET6_ATON/INET6_NTOA.
• Внутренний тип данных для адресов такой же, как и вызывающий тип данных (BINARY(16)).
• Общение с хранимыми процедурами происходит через 32-символьные шестнадцатеричные строки.
• Внутри процедур и в таблице Ips адрес хранится как BINARY(16) для повышения эффективности. HEX() и UNHEX() используются на границах.
• Добавление/вычитание 1 довольно сложно (см. код).
• Тип данных 'владельца' (MEDIUMINT UNSIGNED: 0..16М); 'свободный' представлен как 0. Вам может потребоваться тип данных большего размера.
• Адрес «За пределами конца» (ffff.ffff.ffff.ffff.ffff.ffff.ffff.ffff+1 представлен как NULL).
• Таблица инициализируется одной строкой: (UNHEX('00000000000000000000000000000000'), 0), что означает, что «все адреса свободны. См. комментарии в коде для получения более подробной информации.
• Вам может потребоваться выбрать каноническое представление IPv4 в IPv6. См. комментарии в коде для получения более подробной информации.

Функции INET6* были впервые доступны в MySQL 5.6.3 и MariaDB 10.0.3

Адаптация к другим данным диапазона 'адресов', не связанным с IP

• Внешний тип данных для 'адреса' должен быть удобным для приложения.
• Тип данных для 'адреса' в таблице должен быть упорядоченным и максимально компактным.
• Вы должны написать хранимые функции (IpIncr, IpDecr) для инкрементирования/декрементирования 'адреса'.
• 'Владелец' — это идентификатор по вашему выбору, но меньше — лучше.
• Для 'свободного' должен быть предоставлено специальное значение (например, 0 или '').
• Таблица должна быть инициализирована одной строкой: (НаименьшийАдрес, Свободен)

Для 'владельца' необходимо специальное значение для представления «не принадлежит». Эталонные реализации используют «=» и «!=» для сравнения двух 'владельцев'. Числовые значения и строки хорошо работают с этими операторами; NULL нет. Поэтому, пожалуйста, не используйте NULL для «не принадлежит».

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

Код гарантирует, что последовательные блоки никогда не имеют одного и того же 'владельца', поэтому таблица имеет 'минимальный' размер. Ваше приложение может предполагать, что это всегда так.

Postlog

Оригинальное написание — окт. 2012 г.; Примечания по функциям INET6 — май 2015 г.

См. также

• Связанный блог
• Другой подход
• Бесплатные таблицы IP-адресов

Рик Джеймс любезно разрешил нам использовать эту статью в базе знаний.

Сайт Рика Джеймса содержит другие полезные советы, инструкции, оптимизации и советы по отладке.

Исходный источник: http://mysql.rjweb.org/doc.php/ipranges