Amazon ElastiCache Memcached / Redis: сопоставление диапазона IP-адресов со страной

Только что увидел ваш вопрос, даже если вы давно задали вопрос, у меня есть предложение по использованию Redis.

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

Диапазон поиска по стране

   Lookup |   Range    |     Country
--------|------------+------------------
|     5      |  begin:Country A
L1 >>>           |
|     10     |  end:Country A
|            |
L2 >>>           |
|            |
L2.1>>>   15     |  begin:Country B
|            |
|     20     |  end:Country B
L3 >>>           |
|            |

Уважать L1:

Сделайте поиск числа между [6,10] (здесь включительно ассортимент). В этом случае результат будет end:Country A => IP-адрес принадлежит Страна А. Почему мы начинаем с 6 будет очевидно в L2,

Уважать L2:

Найти число в диапазоне [11, 15] (здесь включительно ассортимент) Результат будет begin:Country B =>

• IF Уважать L2.1
  => Посмотрел номер указывает на начало диапазона, т.е. begin:Country B
  => ОК: iff IP принадлежит Начало: Страна Б оценивать напрямую

• ELSE ОШИБКА: IP не принадлежит ни к одному известному диапазону

Уважать L3:

Результат будет Empty List or Set => ОШИБКА: IP не принадлежит ни одному известному диапазону

Вставка сложнее!

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

   Insert |   Range    |     Country
--------|------------+------------------
|     5      |  begin:Country A
|            |
I1 >>>    8,9    |  !!! Country C !!!
|            |
|     10     |  end:Country A
|            |
|            |
I2 >>>    12,14  |  Country E
|            |
|            |
|     15     |  begin:Country B
|            |
I3 >>>    17,21  |  !!! Country D !!!
|            |
|     20     |  end:Country B
|            |
I4 >>>    22,27  |  Country F
|            |

вставка I1:

Отображает адреса с IP-адресами 6 а также 7 (между 5 а также 8) быть недействительным. => Эффективно Country A диапазон сокращается до одного IP-адреса 10,

вставка I2:

ОК, нет пересечений диапазона

вставка I3:

Оказывает начало из Страна Б недействительный + отдает начало Страна D (17..20) недействительным

вставка I4:

Хорошо

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

Решение на основе Redis

Я бы предложил использовать Redis ZSET для этой цели. Вот наблюдения:

1. Каждый IPv4-адрес может быть представлен как 32-битное целое число, кроме представления десятичной строки с точками.

2. Redis ZSET гарантирует уникальность хранимых членов, дополнительно упорядочивая их с баллами

3. Мы можем искать членов ZSET, используя диапазон баллов, т.е. ZRANGEBYSCORE команда.

Если мы используем числовой IP в качестве оценки ZSET, мы закончили. Уникальность страны обеспечивается путем предварительного begin: а также end: префиксы для определенного диапазона. В реальной жизни одна страна может иметь несколько диапазонов IP-адресов, поэтому вам, вероятно, придется кодировать номер диапазона в название страны, например: begin:r1:Country A а также end:r1:Country A, Вы можете нормализовать это и ввести косвенное обращение. Но чтобы сохранить количество поисков на низком уровне, вам нужно его денормализовать и иметь как можно больше информации при доступе к одной БД. Это связано с тем, что введение нового диапазона происходит гораздо реже, чем поиск, поэтому увеличение количества поисков приведет к снижению производительности.

   Lookup |   Score    |     Country
--------|------------+------------------
|     5      |  begin:Country A
L1 >>>           |
|     10     |  end:Country A
|            |
L2 >>>           |
|            |
L2.1>>>   15     |  begin:Country B
|            |
|     20     |  end:Country B
L3 >>>           |
|            |

Какие Redis команды использовать

Вот простые команды без вашей логики для проверки ошибок во время вставок и т. Д.

• Добавление нового ассортимента

  > ZADD ip-to-country 3232235777 "begin:Country A" 3232235876 "end:Country A"

  Замечания: 3232235777 это IPv4 192.168.1.1 представлен как беззнаковое целое, то же самое относится к 192.168.1.100,

• Проверка, к какому диапазону принадлежит конкретный IP

  > ZRANGEBYSCORE ip-to-country 3232235778 +inf WITHSCORES LIMIT 0 1
  

  Замечания: 3232235778 это IPv4 192.168.1.2 представленный как unsigned int, и мы делаем поиск одного элемента (т.е. LIMIT 0 1) от 192.168.1.8 вперед (т.е. +inf).

• Проверка на Lookup 2.1 посмотрел IP запускает новый ассортимент

   > ZSCORE ip-to-country "begin:Country A"

  Замечания: результат будет 3232235777

Анализ сложности

Космическая сложность: Если в худшем случае мы получим каждый IP, представляющий начало и конец диапазона, нам понадобится O(2*N) пространство, где N 2^32, Но в реальной жизни это число будет намного меньше. В некоторых книгах по алгоритму вы увидите, что 2^32 считается постоянным фактором и, следовательно, будет уменьшен до O(1),

Сложность выполнения: Redis заявляет, что ZRANGEBYSCORE это O(log(N)+M) операция, где M это количество элементов в LIMITт. е. здесь только 1. Если мы имеем максимум 2*2^32 баллы в худшем случае, чем log2(8billion) вокруг 33 Сравнения внутри реализации Redis. Но на самом деле я думаю, что не будет более 2 или 3 тысяч диапазонов, что составляет около 11 сравнения. Redis заявляет для KEYS команда:

Redis, работающий на ноутбуке начального уровня, может сканировать 1 миллион баз данных ключей за 40 миллисекунд.

В общем, ваш поиск будет быстрым!