Во-первых, спасибо за всё, что вы делаете!
Регулярно пользуюсь вашими сервисами.
Исходя из требований и объёма данных, предлагаю перейти на сравнение хэшей.
Каждый домен хэшируется каким-нибудь алгоритмом, например, SHA1.
(Мы не занимаемся проверкой целостности и криптографией, поэтому не имеет смысла брать более мощные алгоритмы. Можно вообще взять MD5 и даже CRC32, хоть он и предназначен для другого.)
Потом берём домен пользователя, хэшируем и сравниваем полученный хэш с таблицей хэшей исходных доменов.
Такой подход используется во многих продуктах, например, Safe Search для AdGuard.
Целые хэши занимают много места, поэтому будем брать их часть - 32 бита.
FIPS.180-4 предлагает брать префикс хэша, то есть просто обрезать остаток строки, получаем 4 байта на домен. Я провел тест на исходных 128к доменах, все 4-байтовые значения получились уникальные. Думаю, вполне хватит 4 байта.
Теперь по хранению всего этого безобразия.
Для ускорения поиска нужно разбить данные на части.
От хэша домена возьмём старший байт, который будет использоваться для индекса.
(Индекс лучше хранить в десятичном виде, занимает меньше места.)
Оставшиеся 3 байта можно закодировать алгоритмом BASE64, который для 3 байт выдаст строку 4 байта.
В эту строку добавим граничный символ “#”, чтобы было проще искать.
В результате получается следующая структура:
domains = {
...
123:"#ABCD#EFGH#...",
124:"#IJKL#MNOP#...",
...
};
Оценка размера структуры.
У нас получается 5 байт на домен и накладные 256 по 8 байт (3 на индекс, 2 на кавычки, 1 на двоеточие, 1 на запятую, 1 на новую строку).
Итого 128000 * 5 + 256 * 8 = 642048 байт.
Алгоритм поиска.
На входе домен пользователя host, считаем от него хэш SHA1(host), берём старшие 4 байта WXYZ.
Байты XYZ кодируем: host64 = BASE64(XYZ).
Добавляем в host64 граничный символ: host64 = “#” + host64.
Если domains[W] существует, тогда в строке domains[W] ищем подстроку host64 с помощью indexOf().
Если значение не равно -1, то хэш найден, домен пользователя в списке.
Оценка реализации.
Получается, что браузеру пользователя нужно посчитать хэш SHA1 для домена, BASE64 для 3 байт хэша и выполнить поиск подстроки в строке.
Это лучше, чем использовать регулярные выражения и алгоритмы сжатия для всей таблицы.
Если предположить, что 128к доменов распределены равномерно по таблице, тогда размер строки равен 128000 * 5 / 256 = 2500 байт.
Пусть даже строка будет в 10 раз длиннее, всё равно поиск будет выполняться достаточно быстро.
Реализация SHA1 занимает около 3 КБ, где-то видел варианты поменьше.
BASE64 в современных браузерах реализован в виде функций atob()/btoa(), для старых можно реализовать отдельно (1, 2).
Думаю, с учётом размера структуры и реализации этих алгоритмов получится вписаться в 700 КБ.
Возможные проблемы.
Из-за коллизии может получиться так, что 32 бита хэша легитимного домена совпадут с таблицей.
На этот случай можно предусмотреть список исключений. Не думаю, что он будет большой.
Реализации SHA1/BASE64 надо тщательно проверять под все версии браузеров, особенно старых.
Оптимизация 1.
Можно отказаться от граничного символа и хранить все хэши подряд “ABCDEFGH…”, это уменьшит размер структуры до 500 КБ.
Но тогда придётся искать все совпадения подстроки и смотреть, чтобы подстрока приходилась на начало блока. Если индекс совпадает с началом блока (index % 4 == 0), тогда хэш найден, иначе искать дальше вплоть до конца строки.
Размер уменьшается, но скорость обработки увеличивается.
Оптимизация 2.
Вариант оптимизации 1 можно улучшить сортировкой хэшей и использованием бинарного поиска.
Думаю, пока можно обойтись без оптимизаций, этого хватит на какое-то время.
Надо бы сделать прототип, но я давно не писал на JS, быстро не получится.
