struct dive_memo
50 subscribers
8 photos
7 links
Dump of thoughts after readings

Author: @epikhinm
Download Telegram
Channel created
These Rows Are Made for Sorting and That’s Just What We’ll Do
https://ir.cwi.nl/pub/33316/33316.pdf
#cwi #duckdb #sort

Прочитал вчера статью про сортировки для row / column based structures в OLAP от ребят из CWI которые занимаются #duckdb

Conclusion:
При обработке и сортировке данных выгодно конвертировать column-based в row-based.
Если нам нужно отсортировать таблицу с несколькими колонками (особенно если по нескольким колонкам), то перемещения и вставки в column-based формате становятся сложнее и проще сделать дополнительно преобразование column -> row -> sort -> column.

We have shown that, for columnar data, sorting by one column at
a time is much more efficient than sorting by all columns
at once. This efficiency can be attributed to a better cache
performance and fewer branches in the tuple comparison
function. However, we have found that sorting data in a row
format is almost always better than sorting columnar data,
mostly due to an even better cache performance.


В статье как раз микробенчмарки на сравнение форматов и сортировок и разных методов сортировок.
Там немного поругались на std::sort [2], но не акцентировали на этом внимание выбрав сразу разные варианты с RadixSort (+ оптимизации) и pdqsort [4].

Sorting is inherently a row-wise operation, but systems
with a vectorized engine use a columnar data format. For
such systems, it might be beneficial to convert the data to
a row format, also called the N-ary Storage Model (NSM),
and then convert it back to a columnar format, also called
the Decomposition Storage Model (DSM), after completing
the sort. Vectorized engines already do this for hash tables in
joins and aggregations [19].

From the results, it is clear that
sorting the row data format is more efficient than sorting the
columnar data format, as the relative runtime of the row sorting
approaches is greater than 1 for almost all inputs. For smaller
input sizes, sorting rows has a similar performance because
the data fits in the CPU’s cache. Therefore, the random access
incurred by the columnar approach does not affect the runtime
by much.
For larger input sizes, the data does not fit in the
CPU’s cache, and the improved cache locality of the row data
format results in a better performance.
In summary, NSM tuple representation performs much
better when sorting relational data than DSM. This is true
regardless of data distribution, and the performance gain is
especially noticeable when sorting a large number of tuples.
It remains to be seen whether converting to rows, sorting, then
converting back to columns is worth it in a system that uses the
DSM tuple representation in its query execution engine

Интересно что #clickhouse тоже использует связку radix + pdqsort, но по тестам этой статьи немного отстает. Статья кажется немного устарела, часть perf counters приводятся с apple m1.
В #clickhousе приносили предложение использовать vqsort вместо pdqsort, но @danlark упомянул что автор pdqsort написал еще новую версию glidesort, которая может быть интересней.
Автор, кстати, пилит #polars в Netherlands.
Тред не закрыт, но обсуждение интересное.


[2] S. Edelkamp and A. Weiß, “BlockQuicksort: Avoiding Branch Mispredictions in Quicksort,” ACM J. Exp. Algorithmics, vol. 24, Jan. 2019. [Online]. Available: https://doi.org/10.1145/3274660
[4] O. R. L. Peters, “Pattern-defeating Quicksort,” CoRR, vol. abs/2106.05123, 2021. [Online]. Available: https://arxiv.org/abs/2106.05123
Channel photo updated
Why TPC is not enough

An analysis of the Amazon Reshift fleet

Когда работал рядом c Y было интересно наблюдать как растет adoption у #clickhouse и #ydb.
Ребят справали про TPC-H и TPC-DS бенчмарки, как стандарт де-факто для аналитических запросов.

Они к ним относились скептически, я не в вдвался в подробности почему именно, но подозревал что не все запросы хорошо работают и не хотелось показать продукт не с лучшей стороны.

Оно в целом и понятно, когда оттачиваешь одни use-case, то какие-то другие могли страдать.
ClickHouse в итоге пришел к своим тестам, где было меньше джойнов и все влезало в память, которые к слову реально крутые в плане сравнения.
На сайте https://benchmark.clickhouse.com/ можно увидеть сравнения разных баз данных, разных версий, разного железа.
Это очень здорово, потому что позволяет быстро оценить разницу, крутой маркетинговый эффект и наглядность.

Я к этому относился скептически, но в прошлом году прочел интересный paper Why TPC Is Not Enough: An Analysis of the Amazon Redshift Fleet [1] и там на примере #amazon #redshift как раз показывается сравнение реальной нагрузки и TPC-H / TPC-DS.

TL;DR то когда у твоего продукта уже есть пользователи, то лучше оптимизировать performance под текущих и потенциальных пользователей.

Можно преуспеть в TPC, но это не означает что улучшит продукт для основных пользователей.
И в paper как раз показывается что нагрузка очень сильно отличается:
* много простых читающих запросов
* много повторов
* другие случаев, которые люди в TPC не положили.

Свои запросы -- это одна из важных ценностей своего продукта.
Пока она закрыты, то конкурентам без запросов сложней понять как быть лучше Redshift, а самому Redshift проще смотреть на сколько их исполнение запроса быстрее/дешевле чем у конкурента.

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

И этот скепсис к TPC это оказался здоровой и правильной стратегией.
SQLStorm 🌩️

🥼 SQLStorm: Taking Database Benchmarking into the LLM Era
🏗️GitHub: https://github.com/SQL-Storm/SQLStorm

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

Ребята из #TUM и #CWI решили сделать ход конем, поигравшись с LLM.
* Взяли dump database от StackOverflow на разные темы с разным размерами 1GB, 12GB и 220GB.
* Скормили DDL (схему данных) в ChatGPT (openai-4o).
* Попросили сгенерировать кучу разных (читающих) запросов с разными параметрами с SQL синтаксисом PostgreSQL.
* Отфильтровали их, местами подправили.
* Решили использовать их как бенчмарк запросы.

Изначально так же посмотрел скептически, пока не прочел paper.
Думал, "ну человек же лучше сформирует эти запросы и сможет покрытие сделать больше"!
Но нет, LLM может!
🤖

Cгенерировали порядка 18 тысяч запросов, часть запросов отпала на парсинге, какие-то пришлось подправить чтобы они выполнялись в #duckdb и #umbra.
Сoverage получился гигантский, благодаря запросам удалось найти кучу багов где исполнение падало в краши, нашли новые краевые случаи где исполнение запроса выполнялось неожиданно долго.

Получился #fuzzing, который практически невозможно написать вручную, запросов слишком много, даже для простой схемы.
Они постарались отбирать запросы так, чтобы они выполнялись относительно быстро (до 1 минуты), что в результате весь бенчмарк занимает порядка 10 минут, что очень круто для такого покрытия.
Если запускать тесты на 1GB, то весь бенчмарк выполняется быстро и это очень удобно для прекоммитных тестов.

В статье сравнивается только тройка PostgreSQL, duckdb и umbra, т.к. синтаксис более полноценный и поддерживаемый.
Основная гонка как раз между duckdb и umbra, где последняя чаще выигрывает.

Ребята сравнили количестве ExecutePlans от TPC-H / TPC-DS и разница в покрытии огромная (см pic 1)
TPC бенчмарки делают много разных запросов, но реальные execution plans схлопываются на два порядка, и вариантивность там очень малая
• TPC-H 256
• TPC-DS 769
• SQLSTORM 10.7K 😱

В clickhouse benchmark всего 42 🤌

TL;DR мне очень понравилась эта статья, потому что она показывает как с помощью небольших усилий и $15 на ChatGPT можно сделать офигенно большое тестирование, лучше популярного бенчмарк стандарта.

Есть и несколько претензий, но имхо все равно работа невероятно крутая, ни один человек не сможет так легко сделать такое тестирование.

Дамп данных от stackoverflow относительно примитивный.
Основные типы данных там INT, DATE и STRING
В реальности сейчас активно используют и вложенные структуры, и JSON, и UUID, и более удобные functions.
Даже такой большой benchmark set есть куда наполнять дальше.

* Для PostgreSQL не использовались indices на сколько я понимаю.
Тут понятно что postgresql вообще немного в другой категории и больше на OLTP, но запросы в реальности в перемешку.
Но если предсоздать индексы, то очень вероятно что PostgreSQL может заметно ускориться.

На лекции Tobias Schmidt показал еще интересный слайд которого нет в paper, где они решили сравнить разные LLM и посмотреть как будут отличаться generated SQL queries. (см pic 2)
Там видно как более новые версии ChatGPT и Gemini делают запросы еще сложнее и количество операндов в запросе растет.
Непонятно на сколько это хорошо или плохо для воспроизвомости в самих бенчмарках в разрезе скорости, но в разрезе fuzzing это выглядит интересно.

Еще интересный поинт:
В TPC стандартах запросы пишут эксперты, которые знают SQL. В реальности их пишут люди которые могут знать его не очень хорошо, неоптимально и/или используя LLM. Местами с ошибками.
И набор запросов из sqlstorm как раз может в каком-то смысле даже лучше отражать реальность.
🔥2
🧑‍🚒 GPU Reliability in AI Clusters: A Study of Failure Modes and Effects

#gpu #failure #nvidia

🥼 Article из #meta platforms

Cтал работать с железом ближе, решил почитать что есть интересного и как часто они выходят из строя GPU.

В статье проанализировали статистику из 1250 Nvidia GPU в 4 кластерах, вот статистика поломок:

🔥 31% Thermal related failures
Чаще всего карты ломаются из-за перегрева, особенно когда температура окружающей среды свыше 24°C.

🔌 22% Power delivery and regulator failures
Это как правило проблемы подачи питания, как в стойке, так и на самой карте.
Так же сюда попадают всплески.

Карта не любит переключний cpu-bound <==> gpu-bound workload, хотя это может быть частой ситуацией когда выполняется checkpoint модели.
Это вызывает временный простой и резкую нагрузку и voltage regulators не всегда справляются с всплесками.

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

The article observed that rapid fluctuations
between compute-intensive and memory-intensive
phases of AI workloads created voltage transients
that exceeded design tolerances. Particularly
concerning were failures during model checkpoint
operations, where synchronized memory writes
across multiple GPUs created power demand
spikes that voltage regulators struggled to
accommodate.


⚠️ 18% Memory subsystem failures
Если в карте начинают появляться single-bit correctable errors, то как правило они потом через время переходят в uncorrectable.
HBM2 карты чаще дают ошибки памяти чем GDDR из-за перегрева, но при этом могут дольше служить.

🏭 13% Manufactoring and silicon defects
Карта может работать стабильно и сбоить только от специфической нагрузки.
Как правило смена специфики нагрузки тут может помочь, либо замена карты по RMA.

🪛10% Firmware & Driver related issues
Я лично думал что этот пункт будет на втором месте.
Возможно это зависит от конкретной карты, драйверов и ядра, возможно исследователям повезло потому что не было разнообразия драйверов и они выровняли версии.

Как правило такие проблемы видны как resource leak и проявляются в продолжительных сценариях или где есть часто-повторяемые операции.
Т.е. в случае с short-lived os это должно быть реже.

📶 6% Interconnect and communication failures
Этот пункт я ожидал третьим, но он тоже в самом конце. Это как раз износ PCI-порта или проблемы с NIC / NVlink.
2
struct dive_memo
🧑‍🚒 GPU Reliability in AI Clusters: A Study of Failure Modes and Effects #gpu #failure #nvidia 🥼 Article из #meta platforms Cтал работать с железом ближе, решил почитать что есть интересного и как часто они выходят из строя GPU. В статье проанализировали…
Интересные факты:

* Как правило карты деградируют сначала по пропускной способности и потом по ошибкам памяти.
* Карты которые деградировали, но работают, потребляют на 25% больше энергии вызывая деградацию соседних.
* В нормальной ситуации gpu uptime 99.2%, но при перегреве падает до 94.7%
* Средний MTBF для GPU около 7250 часов, но когда у тебя большой кластер (1.250), то GPU failure случается каждые 18 часов.

Mitigation strategies:
* Тесты, которые смотрят на соотношения performance (tokens / s) к {TPU, temperature). Это позволяет находить аномалию троттлинга, проседания производительности еще до реальных видимых ошибок
* Охлаждение с избыточностью. Отдельный контур охлаждения между CPU / GPU позволяет снизить число memory issues на 50%.
* Превентивный мониторинг, который следит за картами и находит аномалии раньше чем начинают сбоит и влиять на соседние карты. Reactive Monitoring не отлавливает 42% GPU issues. Будь проактивным, будь как Петя!

Тоже веселый случай, верхняя треть стойки как правило больше перегревается и GPU сбоит в 2.3 раза чаще чем из нижней трети:

The article conducted a detailed analysis of a
production cluster comprising 2,048 GPUs
(NVIDIA A100 80GB) dedicated to large
language model training. Over six months, this
cluster experienced 137 distinct GPU failures
requiring replacement and 412 recoverable
incidents. The primary failure modes were thermal
degradation (41%) and memory subsystem issues
(28%). Notably, failure rates showed significant
positional dependence within racks, with GPUs in
the upper third of racks failing 2.3x more
frequently than those in the lower third. After
implementing enhanced cooling and predictive
maintenance, unplanned downtime decreased by
68%, and training completion time variability
decreased by 47%


Ну и грустная цитата про охлаждение (не хватает инноваций, ожидаем что проблем будет только больше):

The projection models indicate that without
significant architectural changes or cooling
innovations, large-scale AI training clusters may
see reliability decrease by 15-20% per GPU
generation while maintenance costs increase by 25-30%.


У Cloud Providers AFR довольно низкий, в районе 1-2%.

У Edge Computing на consumer железе меньше проблем из-за того что меньше перегрева, но больше с пылью и питанием:)
🧑‍🚒 Characterizing GPU Resilience and Impact on AI/HPC Systems

#gpu #failure #nvidia #slurm

🥼 Article

Похоже я в ближайшее время попишу про GPU.

Еще одно исследование на тему стабильности использования GPU в кластере.
Анализ кластера ~1K GPU с использованием A100 и H100 на протяжении 2.5 лет из UIUC вместе со Slurm.

В отличии от прошлой статьи они разбирали software related issues и механизмамы починки.

📚Take 1: Memory Issues
Одна H100 владеет 96GB HMB3 памятью, A100 40GB HBM2e.
Ошибки на H100 возникают в 3 раза чаше и они в целом коррелируют с объемом памяти.

Чем больше память на карте, тем больше вероятность Memory Issues.

В основном большая часть проблем с картами это ошибки памяти.
В GPU используется ECC память, но она не всегда помогает.
Есть класс ошибок, при которых драйвер помечает блок как Uncorrectable и требует GPU reset, чтобы карта запомнила что этот блок использовать нельзя.
Для пользователя это выглядит как упавший процесс, при простом перезапуске возможен повтор и помогает только GPU Reset и drain всей ноды.
В качестве примера см pic 1.

🚧 Take 2: Средний uptime карты всего 99.3%
Для A100 -- 99.4%, H100 -- 99.3%.
В H100 есть дополнительные механизмы, которые позволяют часть Memory Issues починить без GPU Reset, но процессы все равно продолжат падать.

99.3% это очень мало, это 9-10 минут downtime на каждой карточке.

4 gpu -- uptime 97.2%, downtime 40 min / day
8 gpu -- uptime 94.5%, downtime 79 min / day

Здесь вопрос к скорости починки, от момента обнаружения (Mean-Time-To-Detect) до самого GPU Reset с освобождением от нагрузки (Mean-Time-To-Recover).
Это напрямую влияет на downtime, и GPU reset на картах не объединенных в кластер делать намного быстрее.

💊 Take 3: Устройство автопочинки

На рисунке 2 изображен путь того как обрабатывают ошибки памяти где есть поддержка online recovery mechanisms в виде error containment и dynamic page offloading.

GPU Memory. Figure 3 shows the uncorrectable ECC memory
error-recovery process [35] for A100 and H100 in more detail. The
primary mechanism for mitigating uncorrectable ECC memory er-
rors for A100 and H100 GPUs is row-remapping, wherein the faulty
memory row is replaced with a spare row, and a row-remapping
event (RRE) is logged. The actual row remapping happens at the
next GPU reset (e.g., during node reboot or maintenance). If there
are no spare memory rows, a row remapping failure (RRF) is indi-
cated [33, 35].
A100 and H100 GPUs support online recovery mechanisms such
as error containment and dynamic page offlining [33, 35] for miti-
gating uncorrectable ECC memory errors with minimal node in-
terruption. The dynamic page offlining marks the faulty memory
page as unusable without requiring a GPU reset to maintain avail-
ability. The error containment procedure terminates user processes
using the faulty memory address to prevent error propagation
to other applications. Successful error containment is logged as
a Contained Memory Error, whereas an unsuccessful error con-
tainment is logged as an Uncontained Memory Error. Failure in
a row-remapping or error containment can cause a GPU failure
that requires a GPU reset or node reboot. Delta SREs monitor row-
remapping failures and replace GPUs that repeatedly emit such
errors.


Т.е. надо внимательно следить за износом и заменять GPU, когда он перестает срабатывать.

🪵 Take 4: System logging

Все события по работе этих меназимов можно взять из системных логов.
Nvidia пишет их в dmesg и исследовали их отбирали прямо по regexp, группируя близкие события.

🔗 Take 5: Nvlink errors has a 54% chance of leading to a job failure
Nvlink нужен для быстрого и прямого обмена данными между GPU.
Nvlink поддерживает CRC и он умеет делать retransmit в случае если CRC не сходится.
Кроме того, у исследователей были случаи ошибок NVlink, когда он не использовался для расчета задачи и это никак не влияло на пользователя.
🥶 Take 5: GSP errors
GPU System Processor, это отдельный чип отвечающий за инициализацию и управление заданиями.
У него есть отдельная прошивка, и эта штука может отдельно ломаться.

Как правило, пробелемы с GSP приводят карту в inoperable state или hung / freeze state

GSP errors can be caused by either GSP firmware bugs [32] or
demanding workload. For example, Delta SREs observed that these
errors were highly correlated with heavy ML benchmarks, and
they suggested that GSP errors are high-impact errors whose recov-
ery requires manual node draining and reboots. Our propagation
analysis confirm that the GSP is a single point of failure on both
A100 GPUs in part because of their spontaneous nature and high
downstream impact (e.g., GPU hangs) on the GPU.


In fact, AWS recom-
mends disabling GSP for stability over performance benefits [4].

🚌 Take 6: GPU fallen Off the Bus
Это скорее типичный износ и перегрев.

GPU Fallen Off the Bus errors were
logged when the GPU driver could not reach the GPU over the
system bus. This error is an integration error often caused by a
loose GPU-motherboard connection or contact failure because of
thermal cycles [49]. Over 99% of the errors of this type lead to
similar errors in close successions and eventually put the GPU into
an error state.
Все эти ваши GPU карты это дорогое и ненадежное оборудование, весь мир сошел с ума.
😁3💯2
⏱️ T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees
#tum #redshift #execution #pipeline #decisiontree #lleaves

🥼 Article

В статье описан механизм оценки времени выполнения запроса, еще до его непосредственного выполнения.

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

🪨 Intro

Сама по себе задача интересная, сложная и полезная в части шедуллера.
Когда у тебя есть база данных и тебе надо примерно оценить сколько времени это займет, на какой иp инстансов отправить, пора ли создавать мастштабировать новый инстанс или нет.

Если неправильно оценивать и рассылать их в round-robin порядке, то они могут конфликтовать между собой и замедлять друг друга.

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

Когда запрос прилетает в БД, он проходит через несколько важных фаз:
* Parsing, запрос разбивается на AST дерево
* Построение и оптимизация Logic Plan, где используется информация о таблицах и линейная алгебра чтобы определить в каком порядке узлы графа стоит исполнять и какие можно оптимизировать.
* Execution Plan можно сказать что это непосредственный план выполнения запросов. Даже 1 логический план можно сконвертировать в несколько разных вариантов исполнения, например используя разные алгоритмы для Join (HashJoin vs SortJoin / Memory Join vs Disk Join)
* Execution или непосредственное исполнение.

Execution Plan выглядит как дерево с Pipelines, это участки исполнения запроса на критическом пути между Pipeline Breakers (когда нельзя начать следующий pipeline, не завершив предыдущий). (pic 1)


💡Idea №1: Давайте оценивать каждый отдельный Pipeline, а суммарно запрос как сумму этих Predicted Times.

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


💡 Idea №2: Давайте для каждого pipeline создадим Feature Vector, который будет хранить в себе описание и научим ML оценивать время этой части.

Выглядит это примерно как на (pic 2), вектор довольно большой, под сотню параметров для описания.
Если так получается что конкретный Pipeline мы плохо оцениваем, то можно всегда углубляться и добавлять новых feature для описания и дообучать систему.
Благодрая этому получается оценивать pipelines как генерализированную сущность, которая не зависит от самих таблиц / данных.
Т.е. не надо дообучаться на данных, чтобы корректно оценивать время.


💡 Idea №3: Теперь для каждого из feature-vector нужно оценить примерное время, для этого попробуем натренировать Decision Tree на feature-vector's от синтетических запросов.

Decision Tree это клевый способ, потому что для некоторых задач позволяет написать очень эффективный и быстрый inference на cpu.
Он отлично подходит для задач категоризации/оценки когда есть подготовленный feature-vector.
Автор гонял обучение на ноуте ночью, и на утро у него было много деревьев которые хорошо могли оценивать время исполнения запросов.


💡 Idea №4: Q-Error as Error Function: Q-Error(predicted, observed) = max( predicted / observed, observed / predicted)

В качестве оценки качества предсказания он раз использовал Q-Error, что выглядит как простая формула, но она очень хорошо сработала на данных.
Физически она означает разницу в порядках между предсказанным и реальным временем выполнения запроса.

💡 Idea №5: Компиляция DecisionTree с помощью lleaves

Используемый LightGBM позволил построить несколько DT, и пробегаться по ним чтобы оценивать время и в среднем это занимало ~22us.
Но есть замечательный https://github.com/siboehm/lleaves, который позволяет скомпилировать дерево в код, который будет исполняться заметно шустрее.
Читать его конечно станет невозможно, но это и ненужно, а время работы 4us. (pic 3)


📝 Conclusions
В результате получилась очень быстрая оценка, которая и по скорости и Q-Error превосходит другие имплементации.
Круто это тем, что теперь в момент построения из Logical Plan -> Execution Plans, можно построить несколько и оценить их все, и выбирать нужный уже по оценке времени исполнения, а не только по фичам как раньше.

Результаты оценок pipelines можно кешировать и так делает AWS Redshift в его реализации Stage. Благодаря этому время оценки удается снизить до ~2us для похожих запросов.

🚫 Limitations
Не смотря на всю крутость, у подхода все равно есть ограничения:
1️⃣ Обучать нужно каждый hardware profile, т.е. для каждого instance-type нужно гонять тесты, которые будут строить нужное Decision Tree.
У автора оно гонялось около 10 часов, но зато его можно использовать для любых запросов/данных в БД.
Так же можно переиспользовать между разными версиями БД / инастансами, просто отдельный динамический ресурс.
2️⃣ В модели никак не учитывались в обучении запросы, которые делают Spill на диск. Это скорее дополнительный набор свойств для feature vector, который нужно тренировать. В целом подход наверняка можно переиспользовать, просто надо добавлять это в feature-vector.
3️⃣ Не учитывалась конкуренция за ресурсы. Во время обучения запрос исполнялся один за одним и все ресурсы были отданы ему одному, в реальной ситуации нужно как-то дополнительно учитывать это.
🤓1