Какая БД подходит под частые выборки IP

15 запросов в секунду - это очень немного. Какое железо, какие настройки базы, что именно за запросы?

Ещё интересно, в каком формате хранятся адреса и версия MySQL. MySQL поддерживает нативное хранение IPv4.

Какое железо

Облачный vps 1G ram, 1 cpu 2Ghz

какие настройки базы

Не оптимизирована, по умолчанию

что именно за запросы?

SELECT a, b, …. FROM table WHERE ‘IP’ >= A AND ‘ip’ <= B

Ещё интересно, в каком формате хранятся адреса и версия MySQL.

Int

Вообще, конечно, 1Гб для любой серьёзной нагрузки - это мало. И сильно сомневаюсь, что NoSQL при таких исходных поможет. Redis всё в памяти хранит, если что.

Индекс на поля a и b есть?

1 ГБ - это крайне дохренища оперативы. MySQL/InnoDB потянет до десятков тысяч запросов в секунду в простую табличку уровня (key, value, value, value), которая скорее всего 100 раз полностью влезет в память.

хранить ip в int unsigned и преобразовывать через:
INET_ATON()
INET_NTOA()
будет пошустрее работать

увидел название темы, думаю, зайду посоветую redis, а ты уже сам на него подумал. поддерживаю. не только из-за его максимального requests per second, который ты всё равно не утилизируешь, но и по причине удобства, минимализма и простоты настройки.

Автор пишет, что у него уже в int хранятся адреса. Вангую, что индексов нет.

У Redis - не максимальное RPS - он однопоточный, и в реальном highload начинает захлебываться от большого количества запросов. Хотя, да, его хватает на очень и очень большую нагрузку.

С другой стороны, 15 RPS потянет всё, что угодно, включая SQLite.

Недостаток Redis в том, что под него придётся подстраиваться, конструировать очень специфичные структуры данных. Как ты перепишешь, например, запрос из сообщения автора?

тс указал, что они готовы переписать базу чтоб уйти от группировки. в таком случае можно использовать обычные строковые ключи.

группировка тоже возможна. можно создавать хэши по именам октетов, а в них записывать другие октеты.

кстати, morkovkin, «более 255 адресов» это ничего. даже если у тебя таких диапазонов сотни, вряд ли ты выйдешь за пределы нескольких мегабайт.

Сколько хоть записей в таблице?

MaxMind-DB

У Redis - не максимальное RPS - он однопоточный

Ну возьми dragonflydb

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

Ты какую-то дичь лепишь. ip хранить надо в int, все операции тоже int.

А что, для диапазонов int уже не годится?

Годится, если он длинной 8 байт.

Если диапазоны не пересекаются то можно делать select where ip>=start order by start desc limit 1 ну и ключ по полю start (и проверять что ip<=end - уже после запроса, т.к. иначе он будет искать то чего там нет иногда). Если пересекаются то всё сложно.

Кто тебе сказал что int там один? Хранение в int, и хранится диапазон - значит два int-а на запись.

Теперь понял.

Напишите фильтр Блума, если вам не особо нужны диапазоны. Ну или готовый из того же redis возьмите https://redis.io/docs/data-types/probabilistic/bloom-filter/ Если же диапазонов много и они большие попробуйте в том же же MySQL spatial индекс построить по вашим диапазонам

В стандартный Redis фильтр Блюма не входит. Надо брать Redis Stack или самостоятельно устанавливать модуль bloom. Лицензия отличается от лицензии самого Redis, я не понял до конца, можно ли использовать бесплатно.

Да и вообще, для данного случая кажется оверкиллом.

Похоже проблема в индексах, как и писали выше. НО! Введение индексов может снизить скорость UPDATE и DELETE. Точнее индексы станут бесполезными в базе, которая постоянно обновляется и меняется.

Как быть?

DESCRIBE geoip;
+--------------+------------------+------+-----+---------+----------------+
| Field        | Type             | Null | Key | Default | Extra          |
+--------------+------------------+------+-----+---------+----------------+
| id           | int(10) unsigned | NO   | PRI | NULL    | auto_increment |
| ip_min       | int(11)          | NO   |     | 0       |                |
| ip_max       | int(11)          | NO   |     | 0       |                |
| country      | varchar(4)       | NO   |     |         |                |
| city         | varchar(32)      | NO   |     |         |                |
| isp          | varchar(64)      | NO   |     |         |                |
| proxy        | tinyint(1)       | NO   |     | 0       |                |
| org          | varchar(64)      | NO   |     |         |                |
...
+--------------+------------------+------+-----+---------+----------------+
11 rows in set (0.00 sec)

mysql> SHOW INDEX FROM geoip;
+----------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table          | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| geoip |          0 | PRIMARY  |            1 | id          | A         |      152993 |     NULL | NULL   |      | BTREE      |         |               |
| geoip |          0 | id       |            1 | id          | A         |      152993 |     NULL | NULL   |      | BTREE      |         |               |
+----------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
2 rows in set (0.00 sec)

mysql> SELECT COUNT(*) FROM geoip;
+----------+
| COUNT(*) |
+----------+
|   152993 |
+----------+
1 row in set (0.00 sec)

mysql>  SELECT * FROM geoip WHERE 1000000 >= ip_min AND 1000000 <= ip_max;
Empty set (0.16 sec)

mysql>  SELECT * FROM geoip WHERE 531939328 >= ip_min AND 531939328 <= ip_max;
+-------+-----------+-----------+
| id    | ip_min       | ip_max       | 
+-------+-----------+-----------+
1 row in set (0.19 sec)

mysql> SELECT MAX(ip_max) FROM geoip;
+-------------+
| MAX(ip_max) |
+-------------+
|  2130386431 |
+-------------+
1 row in set (0.08 sec)

mysql> SELECT MIN(ip_min) FROM geoip;
+-------------+
| MIN(ip_min) |
+-------------+
| -2147478272 |
+-------------+
1 row in set (0.09 sec)

Ну на ip_min, ip_max индексы создай и всё. Нафига тут редис

Ну на ip_min, ip_max индексы создай и всё. Нафига тут редис

База активная

индексы станут бесполезными в базе, которая постоянно обновляется и меняется

Введение индексов может снизить скорость UPDATE и DELETE. Точнее индексы станут бесполезными в базе, которая постоянно обновляется и меняется.
Как быть?

Избавляться от индексофобии.

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

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

Диапазоны адресов могут пересекаться.

explain запроса сделай, покажи схему данных и ключи. Сколько записей в таблице?
15rqs - это ни о чём по идее.
upd, всё, вижу, что у тебя ключей нет.

База активная

У тебя всего-то 1к update/delete в день. Не такая уж и проблема будут индексы. Когда упрёшься сделай такую же таблицу inmemory, insert/update делай в две таблице, читай только ту, которая в памяти.

explain запроса сделай, покажи схему данных и ключи. Сколько записей в таблице?

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: geoip
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 152352
        Extra: Using where
1 row in set (0.00 sec)

База активная

индексы станут бесполезными в базе, которая постоянно обновляется и меняется

Не нужно все воспринимать все так буквально. А судя по тому что у тебя

Обновления в базе происходят регулярно, до 1000 update, delete в сутки.

можешь, вообще, считать свою таблицу статической.

Тебе правильно уже сказали: добавь индекс на ip_min+ip_max и дело в шляпе.

Ну он у тебя обходит всю таблицу. 15rqs в таких условиях - это очень даже не плохо. Сделай копию базы, добавь индекс, нагрузи её да посмотри, как будет себя вести, если не уверен.

Не нужно все воспринимать все так буквально.

Даже не буквально то его заявление - ни что иное как результат индексофобии и действительности ни разу не соответствует.

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

Если индекс bitmap, то СУБД может их использовать одновременно. Правда для часто меняющейся таблицы bitmap не подходит.

В таком случае индекс хоть и поможет, но не кардинально. Если сейчас у тебя на каждый запрос брутфорсится вся таблица, то с индексом будет просмтриваться в среднем её половина (в зависимости от того какой айпи).

Не знаю какие есть готовые инструменты для идеального решения этой задачи в общем случае, но, оставаясь в рамках sql, можно эту таблицу поделить на 2-3 в зависимости от размера диапазона. Например одну для диапазонов >=0x1000000 адресов, вторую для тех что меньше. Либо вторую для 0x10000..0xFFFFFF и третью для тех что меньше 0x10000. После чего можно будет в первой хоть селект с полным перебором делать (она совсем маленькая), а во второй select where ip_min<=ip and ip_min>=ip-0x1000000 and ip_max>=ip (только переставить поле с int на unsigned int и проверить что там не получается чего-то плохого с переполнениями при вычитании). Суть в том, что база умеет нормально искать диапазон только по одной колонке, и в данном случае это будет ip_min, по которой отсеется почти всё лишнее, а остальное (условие про ip_max) придётся уже сравнивать почти что перебором.

У автора mysql. А ещё я не понял как они тут могли бы помочь.

Я не думаю, что субд настолько тупая, что имея 2 индекса в памяти она еще куда-то полезет. Там сначала она найдет список ид записей из индексов, что больше ip_min, потом список, что меньше ip_max. Т.к они уже отсортированные после btree, там надо будет пройтись по двум спискам ид и все. Сорцев mysql не видел, но кмк, это вполне разумный сценарий работы.

Я тоже так думал. Но попробовал (Постгрес, правда) — не все так просто.

foo=> create index a_idx on foo(a);
CREATE INDEX
foo=> create index b_idx on foo(b);
CREATE INDEX
foo=> explain select a from foo where a > 100 and b < 200;
                              QUERY PLAN                              
----------------------------------------------------------------------
 Bitmap Heap Scan on foo  (cost=9.87..31.16 rows=251 width=4)
   Recheck Cond: (b < 200)
   Filter: (a > 100)
   ->  Bitmap Index Scan on b_idx  (cost=0.00..9.80 rows=753 width=0)
         Index Cond: (b < 200)
(5 rows)

foo=> 

Твой алгоритм тоже медленный. Сортировка не поможет (она будет по разным колонкам и соответственно в разном порядке, максимум можно попытаться сделать из неё какие-нить хинты, и то не уверен), всё равно придётся брутфорсить один из списков на предмет совпадения его элементов со вторым. Брутфорс индекса это конечно чуть быстрее чем брутфорс файла данных, но не прям что бы очень.

А поскольку толку от такого алгоритма почти нет, то его и не делали. Если же колонка была бы одна и та же то это просто штатное использование одного индекса.

Повторю: тут дело не в фичах базы, эта задача (поиск подходящих интервалов, из списка где они могут пересекаться) принципиально затратная, её можно только оптимизировать всякими костылями похожими как я выше предложил, или же, если много памяти, сделать полную карту соответствия айпи->ответ.

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

Лет 10 назад я использовал это в одном проекте, но с тех пор уже все подробности позабыл, помню только, что было удобно и работало быстро, но у меня там были не ip адреса.

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

Диапазоны адресов могут пересекаться.

Действительно МОГУТ или это просто предположение? Если вы грузите себе какую-то чужую geoip-базу, то в реальности пересечений может и не быть и тогда жизнь существенно упрощается.

частые выборки (в пике 15 запросов в секунду) тормозят сервер

Обновления в базе происходят регулярно, до 1000 update, delete в сутки.

хайлоад! предлагаю hadoop и map/reduce

не бойся индексов а сделай замеры с sql_no_cache и сравни как будет бегать один и тот же запрос с индексом и без.

какое соотношение числа селектов к апдейтам? или там селектов тоже до 1000 в сутки?

если селектов больше, значит делай индексы.

Кстати если все пересечения представляют из себя вложенность одного диапазона в другой - то тоже всё просто. Надо только разметить соответствие range -> parent_range везде и искать самый ближайший обычным способом (без учёта второй границы), а затем по цепочке вверх, если она есть.

Действительно МОГУТ или это просто предположение?

Да, действительно пересекаются 15-20%

не бойся индексов а сделай замеры с sql_no_cache и сравни как будет бегать один и тот же запрос с индексом и без.

Индекс сделал как предложил выше firkax по паре ip_min, ip_max Пока результаты такие: время выборки в 2.5 раза снизилось, но общая нагрузка на cpu в пике запросов визуально меньше не стала.

какое соотношение числа селектов к апдейтам? или там селектов тоже до 1000 в сутки?

Селектов очень много 98-99% по отношению к update и delete

Да, действительно пересекаются 15-20%

У нас для определения геолокации IP-шников используется GeoLite2-City-Blocks-IPv4 - там пересечений реально нет (если и могут быть, то в качестве редких, локальных накладок). Поэтому просто загнал все используемые данные в compound index с первым полем «ip_max». Прям из индекса выгребается подходящая запись по заданному IP-шнику и потом она просто проверяется на реальный охват этого IP-шника. При успешной проверке сразу имеем локацию IP-шника.

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

Навешать индексы, хранить либо числом либо специальным типом. 15 запросов в секунду это не нагрузка. Если это тормозит в скуле то в носкуле оно будет подавно тормозить.

Твой алгоритм тоже медленный.

Нормальный.

Сортировка не поможет

Поможет.

она будет по разным колонкам и соответственно в разном порядке

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

всё равно придётся брутфорсить

Да не придётся.

a > 5
b < 17
Записи: 1:[3,4], 2:[5,7], 3:[7,10], 4:[9,15], 5:[14,15], 6:[18, 35], 7:[47, 50]
a: 5,7,9,14,18,47 (ключи: 2,3,4,5,6,7)
b: 15,10,7 (ключи 5,4,3)
Дальше обходим сразу оба массива, b - с конца (развернул, чтобы было понятнее)
i*
[2,3,4,5,6,7]
j*
[3,4,5]
Если i < j в двигаем i, иначе двигаем j, если равны - пушим в результат. И так пока кто-то из них не закончится.

Я считаю тут нужен поиск по префиксу адреса, в порядке уменьшения длины префикса. Кроме min и max каждая строка таблицы должна содержать префикс, покрывающий этот диапазон адресов. Сами адреса можно хранить как строки из шестнадцатиричных цифр printf("%08x", ntohl(in_addr_t)). Префикс адреса получаем, отбрасывая символы строки с конца. Тогда можно сделать индекс по префиксу, заходить в таблицу по индексу без индекс скана, и это будет эффективно сокращать количество сканируемых строк. Правда, заходить в таблицу придётся не один раз, а 6 раз с длинами префикса от 1 до 6. Длины 7 и 8 это последний октет адреса, он наверное для geoip всегда в одном диапазоне.

sqlite> .schema
CREATE TABLE geoip (prefix varchar(8) not null, min varchar(8) not null, max varchar(8) not null);
CREATE INDEX geoip$prefix on geoip (prefix);

sqlite> explain query plan
with p (prefix) as (
    select substr(:ip,1,6) union
    select substr(:ip,1,5) union
    select substr(:ip,1,4) union
    select substr(:ip,1,3) union
    select substr(:ip,1,2) union
    select substr(:ip,1,1)
)
select geoip.*
from p inner join geoip on p.prefix=geoip.prefix
where :ip between min and max
limit 1;

QUERY PLAN
|--MATERIALIZE 6
|  `--COMPOUND QUERY
|     |--LEFT-MOST SUBQUERY
|     |  `--SCAN CONSTANT ROW
|     |--UNION USING TEMP B-TREE
|     |  `--SCAN CONSTANT ROW
|     |--UNION USING TEMP B-TREE
|     |  `--SCAN CONSTANT ROW
|     |--UNION USING TEMP B-TREE
|     |  `--SCAN CONSTANT ROW
|     |--UNION USING TEMP B-TREE
|     |  `--SCAN CONSTANT ROW
|     `--UNION USING TEMP B-TREE
|        `--SCAN CONSTANT ROW
|--SCAN SUBQUERY 6
`--SEARCH TABLE geoip USING INDEX geoip$prefix (prefix=?)

Например, диапазон 187.17.232.0-187.17.233.255 это prefix=«bb11e», min=«bb11e800», max=«bb11e9ff». При поиске адреса 187.17.233.7 (:ip=«bb11e907») эта кверя заходит в таблицу geoip с префиксами «bb11e9», «bb11e», «bb11», «bb1», «bb», «b». Со второго захода (префикс «bb11e») строка найдена, limit 1 прекращает выполнение квери досрочно.