После ревью в Google снова фидбек из которого мне сложно что-то подцепить. Единственный валидный поинт — мало рассказываю обществу о своих идеях. Ну что, давайте расскажу то, от чего просыпаюсь ночью в последнее время.
Предыстория
Начну с не очень связанной истории. В Cloud warehouse аналитике типа BigQuery биллинг не происходит чисто по времени исполнения или ресурсам запроса, такая модель не очень сильно оправдана с бизнесовой точки зрения. Плюс она не способствует инновациям, оптимизируешь время запроса, люди платят меньше деньги. Хоть ты и оказываешься самым быстрым решением на рынке, но если слишком сильно оптимизировать, то доходы упадут, поэтому у разработчиков нет мотивации что-то делать. У этого есть иногда обратная сторона — ты оптимизируешь запросы и люди приходят и кладут ещё больше данных. Как они себя поведут сильно зависит от ситуации, и это требует очень тщательного понимания пользователей. Но это один из немногих примеров, когда сильные оптимизации могут сыграть плохую шутку. Это тонкая грань — кто-то может прийти и отвоевать рынок засчёт скорости и цены, и в итоге придётся понижать цену/делать фичи доступные только для себя и так далее, чтобы удержать клиентов.
Поэтому чтобы поддерживать баланс укрепилась модель обработки данных — вы платите за терабайт данных. Конечно же, вы не хотите платить много, поэтому при написании запроса вы точно думаете, а сколько данных это прочитает (а часто оно вам и говорит). Из-за этого вы делаете некоторые оптимизации:
1. Партицирование по ключу и фильтры. Указываете WHERE/LIKE и так далее. В итоге многие блоки или части можно выкинуть, и с вас снимут меньше денег. Фильтрации любят делать по датам, числам, их легко сравнивать
2. Сэмплирование. Посмотреть как оно работает на 1% данных тоже часто встречается как решение
Тем не менее, не всегда получается сделать партицирование по нужному ключу, а пофильтровать хочется. В итоге платишь полный скан, что выходит достаточно долго и дорого.
Как нам оптимизировать Cloud?
Cloud уже использует эту возможность данных с помощью сжатия. Сжимаем данные — читаем меньше с диска, пытаемся найти баланс между CPU/диском. Вы платите столько же денег, а мы сами разберёмся, как нам тратить меньше ресурсов. У вас быстрее запросы, у нас меньше ресурсов горит, а денег столько же (можно и чуть поменьше, чтобы компенсировать).
Хорошо, есть алгоритмы сжатия, ZSTD, LZ4, ZLIB, ZIP и так далее. Мы их любим, используем, они стали стандартом. Но ни один из них не предназначен для фильтрации, реально, ни один. В итоге фильтрация может произойти только при разжатии. Это фулскан.
Дальше возникает вопрос: а почему мы (Cloud решения) не инвестируем в фильтрации по сжатым данным? Это достаточно неисследованная тема, в моей голове она крутилась рандомно два-три года с какими-то гипотезами, в том числе и провальными.
В последнее время всё больше возникает идея, что надо просто взять и сделать. И несколько исследователей сделали это, опубликовали статью на VLDB 2020. И никто не обратил должного внимания.
Статья называется FSST — Fast Static Symbol Table. Идея такая: давайте наберём словарик из 254 элементов максимум — это часто встречающиеся подстроки в данных и будем при сжатии писать индекс (1 байт). А если что-то несжимаемое, воспользуемся 255м символом, после которого напишем что-то несжимаемое. В итоге на выходе будет словарик из строк, и индексы этих строк описывающих сжатие.
Фильтрация по подстроке без разжатия может происходить так: мы находим все комбинации из словарика которые могут содержать строку, ищем эти комбинации. Если таких нет — мы точно знаем, что этого паттерна нет, иначе разожмём и поищем честно.
С некоторыми деталями как они находят словарик (привет, суффиксные алгоритмы) авторы статьи добились:
1. На warehouse данных быстрее сжатие, чем LZ4
2. Лучше сжатие, чем LZ4
3. Чуть медленнее разжатие, но сопоставимо с LZ4
Поиск, когда паттерн встречается 0-90% в тексте быстрее, чем поиск в разжатых данных. Из негативных результатов — заявленные бенчмарки работают при AVX-512, иначе все помедленнее процентов на 20-30 будет.
Предыстория
Начну с не очень связанной истории. В Cloud warehouse аналитике типа BigQuery биллинг не происходит чисто по времени исполнения или ресурсам запроса, такая модель не очень сильно оправдана с бизнесовой точки зрения. Плюс она не способствует инновациям, оптимизируешь время запроса, люди платят меньше деньги. Хоть ты и оказываешься самым быстрым решением на рынке, но если слишком сильно оптимизировать, то доходы упадут, поэтому у разработчиков нет мотивации что-то делать. У этого есть иногда обратная сторона — ты оптимизируешь запросы и люди приходят и кладут ещё больше данных. Как они себя поведут сильно зависит от ситуации, и это требует очень тщательного понимания пользователей. Но это один из немногих примеров, когда сильные оптимизации могут сыграть плохую шутку. Это тонкая грань — кто-то может прийти и отвоевать рынок засчёт скорости и цены, и в итоге придётся понижать цену/делать фичи доступные только для себя и так далее, чтобы удержать клиентов.
Поэтому чтобы поддерживать баланс укрепилась модель обработки данных — вы платите за терабайт данных. Конечно же, вы не хотите платить много, поэтому при написании запроса вы точно думаете, а сколько данных это прочитает (а часто оно вам и говорит). Из-за этого вы делаете некоторые оптимизации:
1. Партицирование по ключу и фильтры. Указываете WHERE/LIKE и так далее. В итоге многие блоки или части можно выкинуть, и с вас снимут меньше денег. Фильтрации любят делать по датам, числам, их легко сравнивать
2. Сэмплирование. Посмотреть как оно работает на 1% данных тоже часто встречается как решение
Тем не менее, не всегда получается сделать партицирование по нужному ключу, а пофильтровать хочется. В итоге платишь полный скан, что выходит достаточно долго и дорого.
Как нам оптимизировать Cloud?
Cloud уже использует эту возможность данных с помощью сжатия. Сжимаем данные — читаем меньше с диска, пытаемся найти баланс между CPU/диском. Вы платите столько же денег, а мы сами разберёмся, как нам тратить меньше ресурсов. У вас быстрее запросы, у нас меньше ресурсов горит, а денег столько же (можно и чуть поменьше, чтобы компенсировать).
Хорошо, есть алгоритмы сжатия, ZSTD, LZ4, ZLIB, ZIP и так далее. Мы их любим, используем, они стали стандартом. Но ни один из них не предназначен для фильтрации, реально, ни один. В итоге фильтрация может произойти только при разжатии. Это фулскан.
Дальше возникает вопрос: а почему мы (Cloud решения) не инвестируем в фильтрации по сжатым данным? Это достаточно неисследованная тема, в моей голове она крутилась рандомно два-три года с какими-то гипотезами, в том числе и провальными.
В последнее время всё больше возникает идея, что надо просто взять и сделать. И несколько исследователей сделали это, опубликовали статью на VLDB 2020. И никто не обратил должного внимания.
Статья называется FSST — Fast Static Symbol Table. Идея такая: давайте наберём словарик из 254 элементов максимум — это часто встречающиеся подстроки в данных и будем при сжатии писать индекс (1 байт). А если что-то несжимаемое, воспользуемся 255м символом, после которого напишем что-то несжимаемое. В итоге на выходе будет словарик из строк, и индексы этих строк описывающих сжатие.
Фильтрация по подстроке без разжатия может происходить так: мы находим все комбинации из словарика которые могут содержать строку, ищем эти комбинации. Если таких нет — мы точно знаем, что этого паттерна нет, иначе разожмём и поищем честно.
С некоторыми деталями как они находят словарик (привет, суффиксные алгоритмы) авторы статьи добились:
1. На warehouse данных быстрее сжатие, чем LZ4
2. Лучше сжатие, чем LZ4
3. Чуть медленнее разжатие, но сопоставимо с LZ4
Поиск, когда паттерн встречается 0-90% в тексте быстрее, чем поиск в разжатых данных. Из негативных результатов — заявленные бенчмарки работают при AVX-512, иначе все помедленнее процентов на 20-30 будет.