Ваш аргумент именно про производительность вставки (и даже проверки).
Структура, которую я описал выше, при прочих равных (и при условии правильного подбора fill factor и длины сигнатуры), может давать меньшую вероятность ошибки, занимать меньше места в памяти, и показывать лучшую производительность, чем фильтры Блума как на вставке, так и на проверке.
Все вместе и одновременно.
Причем, это самая простая в реализации альтернатива фильтрам Блума.
Помимо этого, есть более сложные и еще более эффективные варианты с точки зрения потребления памяти, сравнимые по производительности на проверке:
На самом деле, отдельных статей на эту тему я не видел. Вероятно, потому, что это просто частный случай хэш-таблицы. Причем, один из самых тривиальных по построению.
Для анализа вероятностей с минимальными изменениями работает математика, описанная здесь:
Используется тривиальное зондирование с шагом 1. С учетом того, что нам не требуется (в силу невозможности реализации) удаление ключа из таблицы и изменение её размера, реализуются только упрощенная вставка и поиск. Оба алгоритма тривиальны и представляют собой простой цикл.
На практике я встречал (и сам писал код) для частного случая с фиксированной длиной сигнатуры в 32 бита. В этом случае не надо возиться с битовой арифметикой и алгоритмы становятся совсем тривиальными. 32 бита дают вероятность ошибки примерно в 0,0000001% (один на миллиард), что более чем достаточно для большинства сценариев, и, в качестве бонуса, допускают атомарную вставку.
Технически структура применяться может везде где могут использоваться фильтры Блума, за исключением случаев, где требуется удаление (фильтры с счетчиками) или свойство комбинации фильтров Блума через логическое OR (семантика объединения множеств).
Дополнительно, т.к. результатом поиска/вставки является не только признак успеха, но и индекс в массиве сигнатур, то, структуру, дополнительно, можно использовать как отображение (map), используя этот индекс для доступа к данным в другом массиве. Это хорошо подходит для организации всевозможных кэшей, in-memory key-value хранилищ, баз данных и индексов. Можно использовать везде, где требуется высокая производительность и работа с большими объемами данных.
Например, для реализации операции Hash Join при выполнении запроса в БД.
Думаю, что "бабло", конечно, важный фактор, но, в списке приоритетов при принятии такого решения он не на первом месте, вероятно.
Однако, политика и пиар тут, вероятно, имеют больший приоритет.
Тут "имеет место быть" своеобразная дилемма:
С одной стороны, полное отключение всего (почти) возможно технически, и, вероятно, принесет значительный ущерб "подсанкционным юрисдикциям".
С другой стороны, этот инструмент одноразовой, и, вероятно, не приведет к полному коллапсу. В итоге, будут потеряны бесценные инструменты для мониторинга и слежки (гуглить по словосочетанию third-party doctrine). Будет создан колоссальный стимул для роста "постиндустриального аспекта" и "цифровой" экономики в подсанкционных юрисдикциях. Будет колоссальный ущерб в 3-их странах, которые находятся "в зоне санкционного риска". Со временем будет потерян "политический" эффект.
Так что, политикам, как оказалось, выгоднее всего, чтобы жители подсанкционных юрисдикций, как в старом анекдоте, "плакали, кололись, но, продолжали жрать кактус".
МС, же, претендует на деньги, и, существенно снижает (хоть и не устраняет) репутационный и экономический ущерб.
Замечу, что МС, - Американская компания, а, санкция, - Евросоюза. Так что, скорее всего, просто перекроют каналы поставок, проходящие через Евросоюз, и перенаправят пользователей на дата-центры за пределами ЕС. А остальные каналы, - останутся. Пока, конечно, не изменится политическая ситуация. И, тут, конечно, никто гарантий никогда не даст.
Фильтры Блума, это хорошая структура с красивой математикой, однако, на современных ЦП они являются неэффективными с точки зрения производительности на больших объемах данных. Причин тому две:
Необходимо вычисление большого количества хэш-функций, что создаёт большое количество ситуаций branch-mispredict.
Случайный доступ к одному биту в большом массиве повторяется для каждой хэш-функции. Это генерирует большое количество ситуаций cache-miss и доступов в память, что очень медленно. Это неэффективно расходует пропускную способность шины памяти, т.к. ради одного бита мы читаем из памяти ~256 байт (а то и больше).
Гораздо более эффективно на современных ЦП работает простая хэш-таблица с linear-probing для разрешения коллизий, которая содержит не сами ключи, а их хэши (сигнатуры), посчитанные второй хэш-функцией.
Итого, имеем всего две хэш-функции. Одна для вычисления смещения в массиве сигнатур. Вторая для вычисления самой сигнатуры.
В приведенном выше примере:
Допустим, существует 1 000 000 вредоносных ссылок по 20 символов каждая, что составляет 20 МБ. Однако, если мы готовы принять вероятность ошибки в 0,0001% (1 на миллион), можно использовать фильтр Блума. Это позволит хранить те же данные всего в 3,59 МБ.
С такой структурой нам потребуется всего 3,27 MB для хранения 1 000 000 ключей и обеспечения вероятности ошибки в 0,0001% при заполнении таблицы в 75% и длине сигнатуры 22 бита.
При этом, структура будет работать гораздо быстрее фильтров Блума, т.к. мы будем делать всего 1-2 случайных доступа в память, и считать всего два хэша.
Эта система, по сути, запасает энергию днем, когда тепло, а, потом, медленно отдает её ночью. До тех пор, пока днем будет температура подниматься выше +3-5, запасенной энергии будет хватать, чтобы не дать образоваться гололеду ночью при -3-5.
То есть, значительную часть периода, когда ночью уже минус, а днем еще пока плюс, можно не пользоваться солью и снегоуборочной техникой.
Специально менять нет смысла. А вот при очередном строительстве использовать новые технологии, - вполне. Просто, чтобы расход соли снизить. В зависимости от цены "новых технологий", может окупиться на экономии соли и бензина, который техника снегоуборочная кушает.
Когда регулярно температура переходит через -5 гололед конечно будет, но, это гораздо позже случится чем переход через 0, и, даже самый "слоупочный слоупок" догадается, что пора ставить зимнюю резину, потому, что вокруг снег.
О "сразу" и "всего" никто не говорит. От продуктов МС в госучреждениях они уже давно начали отказываться, но, "по возможности". Спешка и "радикальные решения" здесь не сделают блага.
Но, просто к слову, замечу, что Китай уже достаточно давно производит свои x86 процессоры. Помимо этого, у них даже есть лицензия на ядра AMD Zen2, с возможностью их модификации. Которые они, со временем, возможно, начнут производить на своей промышленной базе.
Я думаю, что даже в условиях РФ оно может быть полезно, хотя бы потому, что предотвращает появление "внезапного утреннего гололеда" на утро после первого заморозка. Что является причиной большого количества аварий.
То есть, в условиях РФ необходимость применения соли на дорогах может сократиться с периода "когда ночью начинает появляться минус" до периода "когда уверенный минус постоянно уже днем", что, согласитесь, колоссальная разница.
Кристалл диск тут использован исключительно по аналогии с автором оригинальной статьи, чтобы показать, что даже такой тест показывает, что у автора там что-то не так совсем.
Это не значит, что я не в курсе, что это далеко не самый подходящий инструмент для измерения скорости RAID массивов. И, что IOPS и Latency Percentiles гораздо практичнее.
Недостатки SSD проявляются при использовании RAID 5/6. При использовании RAID 0/1 они не так заметны. А, если количество зеркал в массиве не больше двух, то и проблема с "самым медленным SSD" не так заметна, т.к. это "самый медленный из пары". Но, это дороже.
Но, рынок диктует свое, и, NVM-E продаются без резервирования потому, что спрос есть. Для пользователей, которые хотят сами сделать поверх него собственный распределенный storage кластер, резервирование не нужно.
Дааа... это, по-моему, палево конкретное.... RND4K Q1T1 у HDD и NVME почти одинаковый!
"HDD" слишком быстрый, задержка на уровне SSD. SSD слишком медленный. NVME на уровне обычного SSD.
Мне кажется, что у всех вариантов там внутри под капотом, - примерно одно и тоже, просто настроены разные политики и разные протоколы доступа торчат в виртуальную машину. А обозначения, - это всего лишь маркетинг.
Я бы еще применил сверточные нейросети для сжатия информации. Причем, с темпоральным компонентом (с учетом предыдущих кадров). Человеческий мозг, в состоянии, со временем, научиться декодировать изображение обратно. Да, и, нужно ли это, например, человеку слепому с рождения, на самом деле? (Наверно все-таки нужно на самом деле, но, не в ущерб эффективности в повседневных задачах, для которых зрение предназначено.)
Я думаю, что эффективность этих 1000 электродов возрастет на порядки.
отказоустойчивость, добавляет дополнительные затраты и требует больше усилий для поддержания.
Это, отчасти, так. Но, бонусы описаны выше. Они тоже есть. Например, решает проблему с отсутствием внешнего IP на домашнем маршрутизаторе. Или отсутствием защиты от DDoS.
Вообще, конечно, в облаке держать все проще, конечно. Но, это дороже, если данных много, и, есть люди, вроде меня, которые данные принципиально в облаках не хранят)
Не стоит смотреть на практическую сторону вопроса! Адепты оптимизации оптимизируют ради оптимизации, и, ни для чего больше!
На практике, с точки зрения экономической целесообразности про этот микросервис можно забыть до тех пор, пока нагрузка на него не вырастет раз в 10-100.
Структура, которую я описал выше, при прочих равных (и при условии правильного подбора fill factor и длины сигнатуры), может давать меньшую вероятность ошибки, занимать меньше места в памяти, и показывать лучшую производительность, чем фильтры Блума как на вставке, так и на проверке.
Все вместе и одновременно.
Причем, это самая простая в реализации альтернатива фильтрам Блума.
Помимо этого, есть более сложные и еще более эффективные варианты с точки зрения потребления памяти, сравнимые по производительности на проверке:
https://en.wikipedia.org/wiki/Cuckoo_filter
https://arxiv.org/abs/1912.08258
Но, там вставка медленная.
На самом деле, отдельных статей на эту тему я не видел. Вероятно, потому, что это просто частный случай хэш-таблицы. Причем, один из самых тривиальных по построению.
Для анализа вероятностей с минимальными изменениями работает математика, описанная здесь:
https://preshing.com/20110504/hash-collision-probabilities/
Для реализации и понимания механизма работы достаточно вот этого:
https://ru.wikipedia.org/wiki/Линейное_зондирование
Используется тривиальное зондирование с шагом 1. С учетом того, что нам не требуется (в силу невозможности реализации) удаление ключа из таблицы и изменение её размера, реализуются только упрощенная вставка и поиск. Оба алгоритма тривиальны и представляют собой простой цикл.
На практике я встречал (и сам писал код) для частного случая с фиксированной длиной сигнатуры в 32 бита. В этом случае не надо возиться с битовой арифметикой и алгоритмы становятся совсем тривиальными. 32 бита дают вероятность ошибки примерно в 0,0000001% (один на миллиард), что более чем достаточно для большинства сценариев, и, в качестве бонуса, допускают атомарную вставку.
Технически структура применяться может везде где могут использоваться фильтры Блума, за исключением случаев, где требуется удаление (фильтры с счетчиками) или свойство комбинации фильтров Блума через логическое OR (семантика объединения множеств).
Дополнительно, т.к. результатом поиска/вставки является не только признак успеха, но и индекс в массиве сигнатур, то, структуру, дополнительно, можно использовать как отображение (map), используя этот индекс для доступа к данным в другом массиве. Это хорошо подходит для организации всевозможных кэшей, in-memory key-value хранилищ, баз данных и индексов. Можно использовать везде, где требуется высокая производительность и работа с большими объемами данных.
Например, для реализации операции Hash Join при выполнении запроса в БД.
Думаю, что "бабло", конечно, важный фактор, но, в списке приоритетов при принятии такого решения он не на первом месте, вероятно.
Однако, политика и пиар тут, вероятно, имеют больший приоритет.
Тут "имеет место быть" своеобразная дилемма:
С одной стороны, полное отключение всего (почти) возможно технически, и, вероятно, принесет значительный ущерб "подсанкционным юрисдикциям".
С другой стороны, этот инструмент одноразовой, и, вероятно, не приведет к полному коллапсу. В итоге, будут потеряны бесценные инструменты для мониторинга и слежки (гуглить по словосочетанию third-party doctrine). Будет создан колоссальный стимул для роста "постиндустриального аспекта" и "цифровой" экономики в подсанкционных юрисдикциях. Будет колоссальный ущерб в 3-их странах, которые находятся "в зоне санкционного риска". Со временем будет потерян "политический" эффект.
Так что, политикам, как оказалось, выгоднее всего, чтобы жители подсанкционных юрисдикций, как в старом анекдоте, "плакали, кололись, но, продолжали жрать кактус".
МС, же, претендует на деньги, и, существенно снижает (хоть и не устраняет) репутационный и экономический ущерб.
Замечу, что МС, - Американская компания, а, санкция, - Евросоюза. Так что, скорее всего, просто перекроют каналы поставок, проходящие через Евросоюз, и перенаправят пользователей на дата-центры за пределами ЕС. А остальные каналы, - останутся. Пока, конечно, не изменится политическая ситуация. И, тут, конечно, никто гарантий никогда не даст.
Фильтры Блума, это хорошая структура с красивой математикой, однако, на современных ЦП они являются неэффективными с точки зрения производительности на больших объемах данных. Причин тому две:
Необходимо вычисление большого количества хэш-функций, что создаёт большое количество ситуаций branch-mispredict.
Случайный доступ к одному биту в большом массиве повторяется для каждой хэш-функции. Это генерирует большое количество ситуаций cache-miss и доступов в память, что очень медленно. Это неэффективно расходует пропускную способность шины памяти, т.к. ради одного бита мы читаем из памяти ~256 байт (а то и больше).
Гораздо более эффективно на современных ЦП работает простая хэш-таблица с linear-probing для разрешения коллизий, которая содержит не сами ключи, а их хэши (сигнатуры), посчитанные второй хэш-функцией.
Итого, имеем всего две хэш-функции. Одна для вычисления смещения в массиве сигнатур. Вторая для вычисления самой сигнатуры.
В приведенном выше примере:
С такой структурой нам потребуется всего 3,27 MB для хранения 1 000 000 ключей и обеспечения вероятности ошибки в 0,0001% при заполнении таблицы в 75% и длине сигнатуры 22 бита.
При этом, структура будет работать гораздо быстрее фильтров Блума, т.к. мы будем делать всего 1-2 случайных доступа в память, и считать всего два хэша.
П.С.
Спасибо фильтрам Блума, но, им пора на пенсию!
Важно то, что есть и такие, и такие. И раньше, в обоих случаях нужна была соль, а теперь только в одном.
Солью не только при гололеде пользуются. А всю зиму. Пока не потеплеет.
Позже начнешь пользоваться, раньше закончишь. Отсюда экономия.
Эта система, по сути, запасает энергию днем, когда тепло, а, потом, медленно отдает её ночью. До тех пор, пока днем будет температура подниматься выше +3-5, запасенной энергии будет хватать, чтобы не дать образоваться гололеду ночью при -3-5.
То есть, значительную часть периода, когда ночью уже минус, а днем еще пока плюс, можно не пользоваться солью и снегоуборочной техникой.
Специально менять нет смысла. А вот при очередном строительстве использовать новые технологии, - вполне. Просто, чтобы расход соли снизить. В зависимости от цены "новых технологий", может окупиться на экономии соли и бензина, который техника снегоуборочная кушает.
Когда регулярно температура переходит через -5 гололед конечно будет, но, это гораздо позже случится чем переход через 0, и, даже самый "слоупочный слоупок" догадается, что пора ставить зимнюю резину, потому, что вокруг снег.
О "сразу" и "всего" никто не говорит. От продуктов МС в госучреждениях они уже давно начали отказываться, но, "по возможности". Спешка и "радикальные решения" здесь не сделают блага.
Но, просто к слову, замечу, что Китай уже достаточно давно производит свои x86 процессоры. Помимо этого, у них даже есть лицензия на ядра AMD Zen2, с возможностью их модификации. Которые они, со временем, возможно, начнут производить на своей промышленной базе.
Я думаю, что даже в условиях РФ оно может быть полезно, хотя бы потому, что предотвращает появление "внезапного утреннего гололеда" на утро после первого заморозка. Что является причиной большого количества аварий.
То есть, в условиях РФ необходимость применения соли на дорогах может сократиться с периода "когда ночью начинает появляться минус" до периода "когда уверенный минус постоянно уже днем", что, согласитесь, колоссальная разница.
Они у меня всегда были.
Просто, та часть, которая не актуальна в контексте разговора выше, была вырезана.
MB/s, вообще, в IOPS легко пересчитываются. Так что, не ясно, в чем смысл таких подробностей, кроме удобства сравнения. И, в чем смысл претензий.
Не стоит переходить на личности. Это не вежливо.
Кристалл диск тут использован исключительно по аналогии с автором оригинальной статьи, чтобы показать, что даже такой тест показывает, что у автора там что-то не так совсем.
Это не значит, что я не в курсе, что это далеко не самый подходящий инструмент для измерения скорости RAID массивов. И, что IOPS и Latency Percentiles гораздо практичнее.
Недостатки SSD проявляются при использовании RAID 5/6. При использовании RAID 0/1 они не так заметны. А, если количество зеркал в массиве не больше двух, то и проблема с "самым медленным SSD" не так заметна, т.к. это "самый медленный из пары". Но, это дороже.
Но, рынок диктует свое, и, NVM-E продаются без резервирования потому, что спрос есть. Для пользователей, которые хотят сами сделать поверх него собственный распределенный storage кластер, резервирование не нужно.
Это Linux software raid 10 на 4 x NVME, порезан на куски при помощи LVM, и проброшен в виртуалку с Windows под qemu/KVM.
Дааа... это, по-моему, палево конкретное.... RND4K Q1T1 у HDD и NVME почти одинаковый!
"HDD" слишком быстрый, задержка на уровне SSD. SSD слишком медленный. NVME на уровне обычного SSD.
Мне кажется, что у всех вариантов там внутри под капотом, - примерно одно и тоже, просто настроены разные политики и разные протоколы доступа торчат в виртуальную машину. А обозначения, - это всего лишь маркетинг.
Я бы еще применил сверточные нейросети для сжатия информации. Причем, с темпоральным компонентом (с учетом предыдущих кадров). Человеческий мозг, в состоянии, со временем, научиться декодировать изображение обратно. Да, и, нужно ли это, например, человеку слепому с рождения, на самом деле? (Наверно все-таки нужно на самом деле, но, не в ущерб эффективности в повседневных задачах, для которых зрение предназначено.)
Я думаю, что эффективность этих 1000 электродов возрастет на порядки.
Это, отчасти, так. Но, бонусы описаны выше. Они тоже есть. Например, решает проблему с отсутствием внешнего IP на домашнем маршрутизаторе. Или отсутствием защиты от DDoS.
Вообще, конечно, в облаке держать все проще, конечно. Но, это дороже, если данных много, и, есть люди, вроде меня, которые данные принципиально в облаках не хранят)
Не стоит смотреть на практическую сторону вопроса! Адепты оптимизации оптимизируют ради оптимизации, и, ни для чего больше!
На практике, с точки зрения экономической целесообразности про этот микросервис можно забыть до тех пор, пока нагрузка на него не вырастет раз в 10-100.
Тут вам DNF в помощь. SAT для выражений в DNF решается за линейное время. Плюс, DNF упрощает реализацию оптимизатора.
Шаг 1. Оптимизировать выражения.
Например, у вас куча условий по акциям, и, где-то в конце списка условий стоит наличие какого-то товара в корзине.
Если начать проверку условий с проверки этого товара, то остальные условия можно не проверять.
Это экономит время на бесполезной работе.
Шаг 2. Масштабирование / слияние выражений:
Предположим, у вас большая часть акций связана с наличием определенного товара.
Создаем таблицу товар->акции.
Пробиваем все товары из корзины по таблице в первую очередь.
Отправляем на дальнейшую обработку только акции из правой части таблицы.
Таким образом, мы за одну операцию проверили сразу все условия на "наличие товара" во всех акциях.
Шаг 3. Пишем свой оптимизатор
Автоматизация процесса на шаге 2.
Пишем свой собственный автоматический оптимизатор выражений / на основе статистики запросов.
Шаг 4. Компиляция в машинный код.
Например, средствами LLVM.
....
Имеем свой собственный оптимизирующий JIT компилятор DSL.