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

У меня есть база данных MySQL, которая имеет диапазон ip (начало и конец, поэтому два столбца) и код страны (1 столбец). База данных используется для поиска страны по IP-адресу. Это работает, но я хочу ускорить это больше. Идея состоит в том, чтобы хранить данные в Amazon ElastiCache, используя, например, Redis или Memcache. У меня проблема в том, как можно поступить с таким подходом? Redis, как и Memcache, использует значения ключей, что, на мой взгляд, затрудняет хранение диапазона IP-адресов и кода страны. Какой подход вы бы предложили для использования ElastiCache Memcache или Redis?

Диапазон страны будет примерно таким:

  • 192.168.1.1 — 192.168.1.100 (страна A)
  • 192.168.2.1 — 192.168.2.50 (страна B)
  • 192.168.1.150 — 192.168.1.200 (Страна A)

Теперь я получаю IP-адрес, например 192.168.1.160, мне нужно найти это как можно быстрее и вернуть в этом случае страну А.

Ждем ваших идей.

Марк

0

Решение

Только что увидел ваш вопрос, даже если вы давно задали вопрос, у меня есть предложение по использованию 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 миллисекунд.

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

3

Другие решения

Если у вас есть ключ для начального / конечного диапазона (например, «80-255») и значение кода страны, вы можете использовать Memcached или Redis.

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

0