После ревью в 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 будет.
После ревью в 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 будет.
The public channel had more than 109,000 subscribers, Judge Hui said. Ng had the power to remove or amend the messages in the channel, but he “allowed them to exist.” More>> Step-by-step tutorial on desktop: Invite up to 200 users from your contacts to join your channel Users are more open to new information on workdays rather than weekends.
from us
