Done 🚀
Implementation of wait-free database catalog in ClickHouse.
Зарезервирована для Александра Токмакова.
Манипуляции с каталогом баз данных: запросы CREATE TABLE, DROP TABLE, RENAME TABLE и DATABASE, требуют синхронизации с помощью блокировок. Эта синхронизация становится весьма сложной, так как на неё полагается много внутренних структур данных.
Предлагается реализовать альтернативный подход, в котором таблицы и базы данных являются всего лишь ссылками на persistent объекты. Подробное описание задачи: ClickHouse/ClickHouse#6787
Done 🚀 only for GROUP BY.
Optimization of GROUP BY, DISTINCT and LIMIT BY operations with respect to table sorting key.
Задача зарезервирована для Дмитрия Рубашкина.
Если таблица имеет ключ сортировки, то возможно эффективное чтение упорядоченных данных. Если запрос содержит операцию GROUP BY, содержащую по крайней мере префикс от ключа сортировки таблицы, либо инъективные функции от него, то возможно более эффективное выполнение GROUP BY: промежуточный результат агрегации финализируется и отправляется клиенту как только в потоке данных при чтении из таблицы встретился следующий ключ.
Аналогичную оптимизацию следует реализовать для DISTINCT и LIMIT BY.
В прошлом году, аналогичное решение сделали для операции ORDER BY.
Done 🚀 by completely different people after two years.
Support for coordination systems alternative to Apache ZooKeeper in ClickHouse.
Зарезервирована для Алексея Лёвушкина.
Для координации реплик в ClickHouse используется ZooKeeper. Многие пользователи ClickHouse хотели бы иметь возможность использовать для координации некоторые другие системы вместо ZooKeeper. Рассматриваемыми вариантами таких систем являются Etcd, Consul, FoundationDB. Это весьма проблематично, так как эти системы существенно отличаются по интерфейсам и возможностям. Тем не менее, для того, чтобы эта задача стала возможной, в ClickHouse обобщён интерфейс взаимодействия с ZooKeeper, и теперь на его место можно подставлять другие реализации.
В прошлом году, Алексей добавил модельную реализацию (mock) интерфейса ZooKeeper для тестирования. Сейчас предлагается сделать реализацию поверх Etcd, а также расширить возможности тестовой реализации.
Спекулятивное выполнение распределённых запросов в ClickHouse. Уменьшение количества потоков при распределённых запросах.
Done 🚀
Speculative execution of distributed queries in ClickHouse for elemination of tail latencies.
Тема свободна.
Если распределённый запрос затрагивает большое количество серверов, то время выполнения запросов часто становится большим из-за tail latencies - случайных редких замедлений отдельных серверов. Эту проблему можно избежать, отправляя один и тот же запрос сразу на несколько реплик, и используя данные с наиболее быстрой.
Задача скрывает в себе много тонкостей, связанных с обработкой стадий выполнения запроса (соединение, обмен handshake, отправка запроса, получение заголовка результата, получение пакетов прогресса, получение данных), правильной возможностью настройки таймаутов, правильной отменой запросов.
Сейчас для распределённых запросов используется по потоку на соединение. Это позволяет хорошо распараллелить вычисления над полученными данными и утилизировать сеть, но становится сильно избыточным для больших кластеров. Для примера, создание 1000 потоков для чтения данных из 1000 серверов кластера - лишь расходует ресурсы и увеличивает время выполнения запроса. Вместо этого необходимо использовать количество потоков не большее количества процессорных ядер, и мультиплексировать в одном потоке общение с серверами. Реализация нетривиальна, так как мультиплексировать необходимо каждую стадию общения по сети, включая установку соединения и обмен handshake.
Done 🚀
Polymorphic data chunks in "MergeTree" tables in ClickHouse.
Зарезервирована для Антона Попова.
Данные в таблицах типа MergeTree в ClickHouse хранятся в виде набора независимых "кусков". Внутри куска, каждый столбец, а также индекс, хранится в отдельных файлах. Это сделано для возможности быстрых манипуляций со столбцами (пример - запрос ALTER DROP COLUMN). При вставке данных (INSERT), создаётся новый кусок. Для таблиц с большим количеством столбцов, запросы INSERT с маленьким количеством строк являются неэффективными, так как требуют создания большого количества файлов в файловой системе. Это является врождённой особенностью ClickHouse - одной из первой проблем, с которыми сталкиваются пользователи. Пользователям приходится буферизовывать данные и собирать их в более крупные пачки перед вставкой в ClickHouse.
Для смягчения эффекта от этой проблемы, в ClickHouse существуют таблицы типа Buffer. Они накапливают данные в оперативке перед записью в другую таблицу. Впрочем, таблицы Buffer не являются полноценным решением проблемы из-за: - наличия блокировок при вставке; - переупорядочивание вставляемых данных; - неатомарность перекладывания данных из Buffer в результирующую таблицу.
Вместо этого предлагается разрешить кускам таблиц типа MergeTree располагать данные в разных форматах. А именно: - в оперативной памяти; - на диске со всеми столбцами в одном файле; - на диске со столбцами в отдельных файлах: в зависимости от размера куска и прошедшего времени. Для размещения кусков в оперативной памяти, придётся также реализовать опциональную поддержку write-ahead log с настраиваемыми правилами по сбросу на диск. Это позволит избавиться от проблем с мелкими вставками для MergeTree таблиц. Для ReplicatedMergeTree таблиц, это решит проблему лишь частично.
Done 🚀
Optimization of sorting operations in ClickHouse.
Зарезервировано для Василия Морозова, Арслана Гумерова, Альберта Кидрачева.
- Оптимизация top sort.
В ClickHouse используется неоптимальный вариант top sort. Суть его в том, что из каждого блока достаётся top N записей, а затем, все блоки мержатся. Но доставание top N записей у каждого следующего блока бессмысленно, если мы знаем, что из них в глобальный top N войдёт меньше. Конечно нужно реализовать вариацию на тему priority queue (heap) с быстрым пропуском целых блоков, если ни одна строка не попадёт в накопленный top.
- Рекурсивный вариант сортировки по кортежам.
Для сортировки по кортежам используется обычная сортировка с компаратором, который в цикле по элементам кортежа делает виртуальные вызовы IColumn::compareAt. Это неоптимально - как из-за короткого цикла по неизвестному в compile-time количеству элементов, так и из-за виртуальных вызовов. Чтобы обойтись без виртуальных вызовов, есть метод IColumn::getPermutation. Он используется в случае сортировки по одному столбцу. Есть вариант, что в случае сортировки по кортежу, что-то похожее тоже можно применить... например, сделать метод updatePermutation, принимающий аргументы offset и limit, и допереставляющий перестановку в диапазоне значений, в которых предыдущий столбец имел равные значения.
- RadixSort для сортировки.
Один наш знакомый начал делать задачу по попытке использования RadixSort для сортировки столбцов. Был сделан вариант indirect сортировки (для getPermutation), но не оптимизирован до конца - есть лишние ненужные перекладывания элементов. Для того, чтобы его оптимизировать, придётся добавить немного шаблонной магии (на последнем шаге что-то не копировать, вместо перекладывания индексов - складывать их в готовое место). Также этот человек добавил метод MSD Radix Sort для реализации radix partial sort. Но даже не проверил производительность.
Наиболее содержательная часть задачи может состоять в применении Radix Sort для сортировки кортежей, расположенных в оперативке в виде Structure Of Arrays неизвестного в compile-time размера. Это может работать хуже, чем то, что описано в пункте 2... Но попробовать не помешает.
- Three-way comparison sort.
Виртуальный метод compareAt возвращает -1, 0, 1. Но алгоритмы сортировки сравнениями обычно рассчитаны на operator< и не могут получить преимущества от three-way comparison. А можно ли написать так, чтобы преимущество было?
- pdq partial sort
Хороший алгоритм сортировки сравнениями pdqsort не имеет варианта partial sort. Заметим, что на практике, почти все сортировки в запросах ClickHouse являются partial_sort, так как ORDER BY почти всегда идёт с LIMIT.
Failed.
Probablistic data structures for approximate filtering in ClickHouse queries.
Зарезервирована для Рузеля Ибрагимова
Частой задачей является выполнение запроса с фильтрацией по множеству, полученному по подзапросу. Пример: найти пользователей, которые заходили на сайт сегодня и заходили неделю назад. Это выражается в виде запроса: SELECT UserID FROM table WHERE EventDate = today() AND UserID IN (SELECT ...). При выполнении этого запроса, сначала выполняется подзапрос в правой части IN и формируется хэш-таблица в оперативке; затем эта хэш-таблица используется для фильтрации.
Иногда объём данных достаточно большой, и хэш-таблица не помещается в оперативку. В этом случае можно рассмотреть в качестве варианта приближённый рассчёт: найти пользователей, которые заходили на сайт сегодня и наверное заходили неделю назад. Для этого можно вместо хэш-таблицы использовать Bloom Filter. Другая задача: найти пользователей, которые встречались, скорее всего, не менее некоторого количества раз. Для этого можно использовать Counting Bloom Filter. Также следует изучить структуры данных Quotient Filter и Cuckoo Filer, а ещё - секретный алгоритм Chaotic Map от Андрея Плахова.
Предлагается реализовать это в языке запросов ClickHouse с помощью специального синтаксиса, например x IN BLOOM FILTER (n, m) (SELECT ...).
Done 🚀
Implementation of min-hash and sim-hash algorithms for semi-duplicate search.
Reserved for https://github.com/ucasFL Institute Of Computing Technology Chinese Academy Of Sciences.
Алгоритмы min-hash и sim-hash позволяют вычислить для текста несколько хэш-значений таких, что при небольшом изменении текста, по крайней мере один из хэшей не меняется. Вычисления можно реализовать на n-грамах и словарных шинглах. Предлагается добавить поддержку этих алгоритмов в виде функций в ClickHouse и изучить их применимость для задачи нечёткого поиска полудубликатов.
Done 🚀
Implementation of a data structure for indexed point-in-polygon search.
Зарезервировано для Андрея Чулкова, Антона Кваша и Артура Петуховского.
ClickHouse не является geospatial СУБД. Тем не менее, в ClickHouse есть несколько функций для таких задач. Например, функция pointInPolygon позволяет быстро проверить попадание точек в полигон на плоскости. При этом, полигон задаётся в явном виде и должен быть константным для вызова функции (то есть - проверяется принадлежность многих точек одному полигону). Эта функциональность нужна, например, для рекламного таргетинга мобильных устройств по координатам.
Похожая, но более сложная задача, которую ClickHouse пока не умеет решать - определение полигона среди множества полигонов, в которые попадают точки. Для примера: определение района города по географическим координатам. Для решения этой задачи нужно будет реализовать поддержку словарей с полигонами, в которых данные проиндексированы для быстрого поиска.
Done 🚀
Implementation of data types for geospatial analysis in ClickHouse.
Зарезервировано для Алексея Корякова и Алексея Илюхова.
Подходит для командной работы.
Реализовать в ClickHouse типы данных для задач обработки геоинформационных данных: Point, Line, MultiLine, Polygon и операции над ними - проверка вхождения, пересечения. Вариантом минимум будет реализация этих операций в евклидовой системе координат. Дополнительно - на сфере и WGS84.
Done 🚀
Implementation of statistical tests as aggregate functions in ClickHouse.
Зарезервировано для Артёма Цыганова. Он не против взять людей в команду.
Подходит для командной работы.
Предлагается реализовать в ClickHouse статистические тесты (Analysis of Variance, тесты нормальности распределения и т. п.) в виде агрегатных функций. Пример: welchTTest(value, sample_idx).
Done 🚀
Support for Apache Avro data format in ClickHouse.
Зарезервирована для Павла Круглова.
Формат Apache Avro является компактным структурированным построчным бинарным форматом данных с внешней схемой. Этот формат часто используется совместно с Kafka и поддержка его в качестве одного из форматов ввода-вывода в ClickHouse является востребованной пользователями.
Done 🚀
Algebraic and peephole query optimizations in ClickHouse.
Зарезервировано для Руслана Камалова и команды.
Подходит для командной работы.
Реализовать в ClickHouse оптимизации запросов, основанные на упрощении отдельных небольших кусков выражений (так называемые "peephole" оптимизации), а также оптимизации, основанные на алгебраических свойствах функций. Примеры:
- Замена цепочек if на multiIf.
- Обращение инъективных функций в сравнениях на равенство.
- Удаление min/max/any-агрегатов от выражений от ключей GROUP BY.
- Вынесение арифметических операций из агрегатных функций;
- Вынесение любых функций наружу any, anyLast.
- Вынесение инъективных функцию наружу uniq.
- Удаление монотонных функций из ORDER BY.
- Удаление избыточных выражений из ORDER BY.
- Удаление из GROUP BY функций от других ключей GROUP BY.
- При GROUP BY по transform или if по строкам, замена строк на Enum.
- Удаление дублирующихся DISTINCT, ORDER BY из подзапросов.
Done 🚀
Optimization of ClickHouse queries using table constraints.
Тема свободна.
Constraints позволяют задать выражение, истинность которого проверяется при вставке данных в таблицу. Предположение о том, что выражение истинно, может использоваться и для оптимизации запросов. Например, встретив в запросе точно такое же выражение, можно заменить его на константу 1.
Если выражение содержит равенство, то встретив в запросе одну из частей равенства, её можно заменить на другую часть равенства, если это сделает проще чтение данных или вычисление выражения. Например, задан constraint: URLDomain = domain(URL). Значит, выражение domain(URL) можно заменить на URLDomain.
Mostly failed.
Fuzz-testing of ClickHouse DBMS.
Зарезервировано для Андрея Некрашевича.
Fuzzing тестирование - это тестирование случайными данными. Мы рассмотрим несколько подходов к этой задачи:
-
Добавление в SQL диалект ClickHouse функций для генерации случайных данных (пример - случайные бинарные строки заданной длины, случайные валидные UTF-8 строки) и "порчи" данных (например, поменять значения случайных бит с заданной частотой). Это будет использовано для тестирования SQL-функций ClickHouse.
-
Использование AFL или LibFuzzer для тестирования отдельных частей кодовой базы ClickHouse.
-
Генерация и выполнение случайных синтаксически корректных запросов на случайных данных.
Done 🚀
Optimization of ClickHouse for modern instruction set architectures.
Зарезервировано для Дмитрия Ковалькова.
Подавляющее большинство кода ClickHouse написана для x86_64 с набором инструкций до SSE 4.2 включительно. Лишь отдельные редкие функции поддерживают AVX/AVX2/AVX512 с динамической диспетчеризацией.
В первой части задачи, следует добавить в ClickHouse реализации некоторых примитивов, оптимизированные под более новый набор инструкций. Например, AVX2 реализацию генератора случайных чисел pcg: https://github.com/lemire/simdpcg
Во второй части задачи, предлагается адаптировать существующие куски кода, использующие SSE intrinsics на AVX/AVX2 и сравнить производительность. Также рассматривается оптимизация под ARM NEON.
Генерация искусственных данных для тестирования заданных запросов. Обфускация запросов для тестирования ClickHouse.
Done 🚀
Automatic generation of random datasets for a query; obfuscation of queries for test generation.
Зарезервирована для Романа Ильговского.
Имея SQL запрос, требуется вывести структуру таблиц, на которых этот запрос будет выполнен, и заполнить эти таблицы случайными данными, такими, что результат этого запроса зависит от выбора подмножества данных.
Для примера, если есть запрос SELECT SearchPhrase, count(*) FROM table WHERE CounterID = 34 AND SearchPhrase LIKE '%ClickHouse%', то мы можем сделать вывод, что CounterID имеет числовой тип, а SearchPhrase - строковый. Заполнить таблицу данными, на которых отдельные условия CounterID = 34 и SearchPhrase LIKE '%ClickHouse%' для некоторых строк выполнены, а для некоторых строк не выполнены.
Обфускация запросов: имея секретные запросы и структуру таблиц, заменить имена полей и константы, чтобы запросы можно было использовать в качестве публично доступных тестов.
Done 🚀
Improving external distionaries in ClickHouse DBMS.
Зарезервировано для Артёма Стрельцова, Николая Дегтеринского и Наталии Михненко.
Подходит для командной работы.
Поддержка Nullable типов данных, Decimal, массивов во внешних словарях в ClickHouse. Тип словарей direct - прямой запрос в источник без кэширования данных в ClickHouse. Возможность (под опцией) строить обратное отображение в памяти и реализовать функции dictGetKeys, dictGetKey для injective случая.
Возможность зарегистрировать некоторые функции, использующие словари, под пользовательскими именами.
Done 🚀
Зарезервировано для Никиты Васильева.
Implementation of cache-type dictionaries with SSD-optimized data structures in ClickHouse.
Реализовать в ClickHouse специализированный движок таблиц, подходящий для быстрых key-value запросов и оптимизированный для расположения данных на SSD. Это может быть: реализация на основе RocksDB; сериализованные RowBinary данные с индексом в оперативке; секретная очень эффективная структура данных, о которой я расскажу.
Использовать эту структуру данных как отдельный вид словарей, как источник для cache словарей или как дополнительный уровень кэширования для cache словарей.
Done 🚀
Support for continuous data import from RabbitMQ in ClickHouse.
Зарезервировано для Ксении Сумароковой.
В ClickHouse часто используется потоковый импорт данных из распределённой очереди. Наиболее популярно использование совместно с Kafka. Эта возможность уже есть.
Следующей по востребованности является система очередей RabbitMQ. Её поддержка в ClickHouse отсутствует.
Done 🚀 for DISTINCT.
Support for DISTINCT and ORDER BY modifiers for every aggregate function in ClickHouse.
Зарезервировано для Софии Борзенковой
В ClickHouse поддерживается вычисление COUNT(DISTINCT x). Предлагается добавить возможность использования модификатора DISTINCT для всех агрегатных функций. Например, AVG(DISTINCT x) - вычислить среднее значение для всех различных значений x. Под вопросом вариант, в котором фильтрация уникальных значений выполняется по одному выражению, а агрегация по другому.
Результат некоторых агрегатных функций зависит от порядка данных. Предлагается реализовать модификатор ORDER BY, задающий порядок явно. Пример: groupArray(x ORDER BY y, z).
Done 🚀
Background data recompression in ClickHouse.
Зарезервировано для Кирилла Барухова.
Алгоритмы сжатия типа LZ77 позволяют потратить больше времени на сжатие данных, чтобы сжать данные сильнее, но при этом без проигрыша по скорости разжатия данных. В частности, этим свойством обладает LZ4 и ZSTD, которые используются в ClickHouse. Это позволяет использовать свободные ресурсы CPU, когда сервер не нагружен, для пережатия данных, чтобы данные занимали меньше места на дисках, и при этом сохранить или даже улучшить скорость обработки запросов.
В то же время, ClickHouse обычно используется для "импульсного" сценария нагрузки. Запрос от пользователя обрабатывается максимально быстро, используя все ресурсы CPU, но в среднем по времени, сервер недостаточно нагружен.
Предлагается добавить в ClickHouse настройки по пережатию данных и фоновые потоки, выполняющие эту задачу.
Done 🚀 and dropped.
Implementation of experimental data compression algorithms in ClickHouse.
Зарезервировано для Руслана Сафронова.
Подходит для командной работы.
ClickHouse поддерживает LZ4 и ZSTD для сжатия данных. Эти алгоритмы являются парето-оптимальными по соотношению скорости и коэффициентам сжатия среди достаточно известных. Тем не менее, существуют менее известные алгоритмы сжатия, которые могут превзойти их по какому-либо критерию. Из потенциально более быстрых по сравнимом коэффициенте сжатия: Lizard, LZSSE, density. Из более сильных: bsc и csc. Необходимо изучить эти алгоритмы, добавить их поддержку в ClickHouse и исследовать их работу на тестовых датасетах.
Failed.
Implementation of codecs for integer sequences in ClickHouse.
Зарезервировано для Вероники Фалчиковой и Лады Торчик.
Подходит для командной работы.
Существуют специализированные алгоритмы кодирования числовых последовательностей: Group VarInt, MaskedVByte, PFOR. Необходимо изучить наиболее эффективные реализации этих алгоритмов. Примеры вы сможете найти на https://github.com/lemire и https://github.com/powturbo/ а также https://github.com/schizofreny/middle-out
Внедрить их в ClickHouse в виде кодеков и изучить их работу на тестовых датасетах.
Done 🚀
Data encryption in ClickHouse.
Тема свободна.
Данные в ClickHouse хранятся без шифрования. При наличии доступа к дискам, злоумышленник может прочитать данные. Предлагается реализовать два подхода к шифрованию:
-
Шифрование отдельных значений. Для этого требуется реализовать функции шифрования и расшифрования, доступные из SQL. Для шифрования реализовать возможность добавления нужного количества случайных бит для исключения одинаковых зашифрованных значений на одинаковых данных. Это позволит реализовать возможность "забывания" данных без удаления строк таблицы: можно шифровать данные разных клиентов разными ключами, и для того, чтобы забыть данные одного клиента, потребуется всего лишь удалить ключ.
-
Шифрование блоков данных. Шифрование данных столбцов на диске требуется реализовать в виде кодеков. Это позволит применять шифрование к отдельным столбцам; применять его после сжатия данных (эффективно, но менее безопасно) или без сжатия. Потребуется проработать работу с ключами: получение ключей из отдельного сервиса, правильная работа с ключами в оперативке. Отдельным вопросом стоит шифрование индексов.
Unfinished.
Implementation of RAID in userspace for ClickHouse.
Задача зарезервирована для Глеба Новикова.
RAID позволяет одновременно увеличить надёжность хранения данных на дисках и увеличить скорость работы дискового массива. Обычно RAID настраивается с помощью встроенных возможностей ядра Linux (mdraid) или с помощью hardware контроллера. У этого есть следующие ограничения:
-
Иногда (в облачной инфраструктуре некоторых компаний) сервер предоставляется с отдельными дисками, подмонтированными в виде отдельных разделов (JBOD), без возможности создания RAID.
-
В ClickHouse для обеспечения избыточности обычно используется репликация между серверами. Но при восстановлении одного из дисков RAID не используются данные с реплик, а в случае отказа одного из дисков в RAID-0, приходится передавать с реплики все данные, а не только данные, соответствующие одному из дисков. Это происходит, потому что RAID не интегрирован в ClickHouse и "не знает" про его особенности.
-
Отсутствуют продвинутые варианты обеспечения избыточности, как например, LRC.
Для преодоления этих ограничений, предлагается реализовать в ClickHouse встроенный алгоритм расположения данных на дисках.
Done 🚀
Replicated database engine in ClickHouse.
Зарезервировано для Валерия Батурина.
Репликация в ClickHouse работает на уровне отдельных таблиц. Это является очень гибким решением: на одном сервере одна из таблиц может быть не реплицирована, другая иметь двухкратную репликацию, а третья - реплицирована по всем серверам. Но если все таблицы в базе данных реплицированы одинаковым образом. то это затрудняет управление кластером. Например, при восстановлени сервера, требуется отдельно создавать реплику для каждой таблицы.
Предлагается реализовать "движок баз данных", который осуществляет репликацию метаданных (множество имеющихся таблиц и лог DDL операций над ними: CREATE, DROP, RENAME, ALTER). Пользователь сможет создать реплицируемую базу данных; при её создании или восстановлении на другом сервере, все реплицируемые таблицы будут созданы автоматически.
Done 🚀
Implementation of PostgreSQL wire protocol in ClickHouse.
Зарезервирована для @sesvom
В ClickHouse в прошлом году добавили поддержку wire-протокола MySQL. PostgreSQL, так же как MySQL, использует несложный протокол общения между клиентом и сервером, но свой собственный. Поддержка этого протокола является востребованной и откроет новые возможности для ClickHouse.
Done 🚀
ClickHouse as a MySQL replica.
Зарезервировано для Ильяса Адюгамова.
Реализовать возможность подписаться на row-based репликацию MySQL и сохранять полученные данные в CollapsingMergeTree или ReplacingMergeTree таблицы. Сторонние решения для этой задачи уже существуют: https://www.altinity.com/blog/2018/6/30/realtime-mysql-clickhouse-replication-in-practice Также существует стороннее решение для PostgreSQL: https://github.com/mkabilov/pg2ch
Встроенная в ClickHouse возможность работать в качестве реплики MySQL даст преимущества для дальнейшего развития.
Done 🚀
Implementation of HTTP/2 or GRPC protocol in ClickHouse.
Зарезервировано для Марии Коньковой.
В ClickHouse есть два основных протокола: родной протокол общения между серверами и HTTP/1.1 протокол. HTTP/1.1 протокол удобен для работы из самых разных языков программирования, но, в отличие от родного протокола, не поддерживает двусторонний обмен информацией во время запроса:
- передачу информации о прогрессе во время выполнения запроса;
- передачу логов во время выполнения запроса;
- отмену выполнения запроса в тот момент как данные ещё не начали передаваться;
Ради эксперимента, это можно реализовать в рамках HTTP/2.
Также рассматривается вариант - поддержка GRPC в ClickHouse. Здесь есть неочевидные моменты, такие как - эффективная передача массивов данных в column-oriented формате - насколько удобно будет обернуть это в GRPC.
Done 🚀
User Defined Functions in ClickHouse.
Зарезервирована для Игоря Минеева
ClickHouse предоставляет достаточно богатый набор встроенных функций языка запросов, но не позволяет пользователю добавлять свои функции без редактировния исходников и перекомпиляции системы. Это мотивировано следующими потенциальными проблемами:
- ClickHouse является array-oriented системой, и все функции внутри кода принимают для обработки целые массивы, а не отдельные значения. Это усложняет внутренний интерфейс и делает его менее удобным для пользователя.
- Предоставление возможности подключения UDF в виде shared библиотек, потребовало бы фиксировать этот интерфейс или поддерживать обратную совместимость, тогда как мы бы хотели, при разработке ClickHouse, менять этот интерфейс по своему усмотрению без оглядки.
- Сложность внутренних структур данных повышает вероятность ошибок типа buffer overflow и повреждения памяти, что сильно затруднит сопровождение ClickHouse с пользовательскими функциями.
Тем не менее, можно выбрать более аккуратный подход, избегающий непосредственной линковки с shared библиотеками.
Сначала можно реализовать поддержку UDF в виде выражений, составленных из простых функций ClickHouse. В ClickHouse есть встроенная кодогенерация на LLVM, что позволит таким функциям работать весьма эффективно. Но этот подход весьма ограничен и поэтому не является исчерпывающим.
Затем предлагается реализовать поддержку UDF в виде исходников на C++, которые компилируются в runtime, с использованием заголовочных файлов ClickHouse. Требование компиляции из исходников вместо shared библиотек, позволит ослабить необходимость в поддержке совместимости ABI.
Для безопасности, потребуется исследовать возможность размещения буферов данных в shared memory для выполнения UDF в отдельных процессах с изоляцией по памяти. Возможно, для этого пригодится интеграция с Apache Arrow.
Также рассматривается возможность написания UDF на Rust, а также использование Web Assembly. Отдельно можно рассмотреть подключение NumPy и R и других технологий, которые предоставляют операции над целыми массивами.
Преднастроенные соединения для внешних источников в ClickHouse. Преднастроенные обработчики для HTTP интерфейса.
Done 🚀
Predefined connections for external data sources in ClickHouse; predefined handlers for ClickHouse HTTP interface.
Задача зарезервирована для Валерия Батурина.
ClickHouse предоставляет возможность обратиться к внешней базе данных из языка запросов. Это реализовано в виде табличных функций. В параметрах к табличной функции указывается адрес удалённой базы данных (хост, порт), а также аутентификационные данные (имя пользователя, пароль). Аутентификационные данные указываются в запросе в открытом виде и, таким образом, попадают в историю запросов и в логи, что компрометирует безопасность системы.
Вместо этого предлагается описывать необходимые данные в конфигурационном файле сервера или в отдельном сервисе и ссылаться на них по именам.
Вторая часть задачи - возможность описать в конфигурационном файле handler (путь в URL) для HTTP запросов к серверу, которому соответствует некоторый параметризованный запрос. Пользователь может вызвать этот обработчик и не должен передавать SQL запрос.
Done 🚀
Improvement of quorum inserts in ClickHouse.
Задача зарезервирована для Александры Латышевой.
Для тех, кого интересуют распределённые системы.
Репликация данных в ClickHouse по-умолчанию является асинхронной без выделенного мастера. Это значит, что клиент, осуществляющий вставку данных, получает успешный ответ после того, как данные попали на один сервер; репликация данных по остальным серверам осуществляется в другой момент времени. Это ненадёжно, потому что допускает потерю только что вставленных данных при потере лишь одного сервера.
Для решения этой проблемы, в ClickHouse есть возможность включить "кворумную" вставку. Это значит, что клиент, осуществляющий вставку данных, получает успешный ответ после того, как данные попали на несколько (кворум) серверов. Обеспечивается линеаризуемость: клиент, получает успешный ответ после того, как данные попали на несколько реплик, которые содержат все предыдущие данные, вставленные с кворумом (такие реплики можно называть "синхронными"), и при запросе SELECT можно выставить настройку, разрешающую только чтение с синхронных реплик.
Если бы свойства линеаризуемости не было, то для трёх серверов A, B, C, значения кворума = 2, и для трёх вставок данных 1, 2, 3, возможна ситуация, что первая вставка прошла на серверы A и B, вторая прошла на серверы B и C, а третья - на серверы A и C, и теперь ни один из серверов не содержит полный набор данных 1, 2, 3.
Как ни странно, такое свойство не нужно большинству пользователей. Оно запрещает параллельно выполняющиеся вставки. А пользователи хотят вставлять данные надёжно (на более чем одну реплику), но не важно, в каком порядке. Предлагается сделать опцию, которая отключает линеаризуемость.
Иногда пользователь хочет реализовать кворумную вставку вручную: просто соединиться с несколькими репликами и вставть на них одинаковые данные (чтобы обеспечить надёжную вставку, не ориентируясь на то, как работает механизм репликации). Сейчас ожидания пользователя не оправдываются. В ClickHouse есть механизм дедупликации для обеспечения идемпотентности вставок. Вторая вставка с такими же данными (пусть даже на другую реплику) будет проигнорирована. Надо сделать так, чтобы вместо этого, вставка одинаковых данных на другую реплику, имела такой же эффект, как если бы эти данные были получены с помощью механизма репликации.
Failed.
Integrated web-application for monitoring and profiling of ClickHouse clusters.
Зарезервировано для Антона Мамонова (graf-m)
Задача не требует знания C++.
Внутри ClickHouse есть богатые возможности по интроспекции и профилированию. Эти возможности доступны через системные таблицы и использовать их приходится путём формулирования SQL запросов. Это неудобно.
Вместо этого предлагается сделать, чтобы ClickHouse отдавал HTML страницу, реализующую интерактивный web-интерфейс со следующими возможностями:
- отображение состояния кластеров (какие кластеры известны, статус каждого сервера);
- графики нагрузки текущего сервера или выбранного сервера кластера;
- обновляемый список запросов;
- просмотр лога запросов с наиболее востребованными фильтрациями по одной кнопке;
- просмотр лога на кластере, например - последние ошибки;
- просмотр метрик использования ресурсов, flame graph и pprof-граф для выбранных запросов;
- отчёт по использованию кластера (пример: количество ядер CPU по пользователям за сегодня).
Development of alternative for readline library in ClickHouse.
Done 🚀
Задача зарезервирована для Тагира Курсакова.
Для ввода запросов в интерактивном режиме в клиенте командной строки clickhouse-client используется библиотека readline или libedit.
Библиотеки readline и libedit обладает следующими недостатками:
- (исправлено в новых версиях readline) Очень низкая производительность вставки больших кусков текста. Вставка каждого следующего символа имеет сложность O(n = количество предыдущих символов) и при вставке 1 МБ текста, скорость падает до десятков байт в секунду.
- Крайне сложно или невозможно реализовать подсветку синтаксиса по мере набора текста, а также autocomplete без нажатия дополнительных клавиш для вызова.
- Лицензия GPL (для readline) препятствует её включению в кодовую базу продукта.
- Плохо работает навигация по истории, если история вкючает запросы, не помещающиеся на экран.
- История сохраняется лишь при завершении работы клиента.
- При параллельной работе нескольких клиентов с одним файлом истории, сохраняется история только одного из клиентов.
- Плохо работает история для многострочных запросов.
- Излишняя экономия пересылаемых данных, что часто приводит к остаткам мусора в терминале.
Кроме того, имеются следующие сложно достижимые достоинства:
- Поддержка right-to-left текста;
- Поддержка editrc конфигураций.
В качестве альтернатив можно рассмотреть следующие варианты:
- Linenoise от Salvatore Sanfilippo. Достоинства: простота и компактность кода; высокая скорость работы. Недостатки: отсутствует поддержка Unicode; отсутствует автоматический перенос текста, что затрудняет работу с многострочными запросами.
- Linenoise с патчами для поддержки Unicode. Недостаток: теряется преимущество по скорости работы.
- Fish shell. Не является библиотекой, но представляет собой отличный пример, как можно реализовать подстветку синтаксиса и удобный autocomplete. Поддерживает Unicode, но работает весьма медленно.
- Python Prompt Toolkit. Не является подходящим решением для интеграции в C++ проект. Хорошие возможности по подсветке синтаксиса и autocomplete.
Вместо этого предлагается в качестве примера изучить прототип текстового редактора Kilo: https://viewsourcecode.org/snaptoken/kilo/ и реализовать всю необходимую функциональность.
Done 🚀
GPU offloading prototype in ClickHouse.
Зарезервирована для Риты Конновой.
В компании nVidia сделали прототип offloading вычисления GROUP BY с некоторыми из агрегатных функций в ClickHouse и обещат предоставить исходники в публичный доступ для дальнейшего развития. Предлагается изучить этот прототип и расширить его применимость для более широкого сценария использования. В качестве альтернативы, предлагается изучить исходные коды системы OmniSci или Alenka или библиотеку CUB https://nvlabs.github.io/cub/ и применить некоторые из алгоритмов в ClickHouse.
Для решения задачи может быть предоставлен сервер с GPU.
Done 🚀
Virtual File System for ClickHouse.
Задача зарезервирована для Олега Ершова.
ClickHouse использует для хранения данных локальную файловую систему. Существует сценарий работы, в котором размещение старых (архивных) данных было бы выгодно на удалённой файловой системе. Если файловая система POSIX совместимая, то это не составляет проблем: ClickHouse успешно работает с Ceph, GlusterFS, MooseFS. Также востребованным является сценарий использования S3 (из-за доступности в облаке) или HDFS (для интеграции с Hadoop). Но эти файловые системы не являются POSIX совместимыми. Хотя для них существуют FUSE драйверы, но скорость работы сильно страдает и поддержка неполная.
ClickHouse использует небольшое подмножество функций ФС, но в то же время, и некоторые специфические части: симлинки и хардлинки, O_DIRECT. Предлагается выделить всё взаимодействие с файловой системой в отдельный интерфейс и сделать его реализацию на основе S3 и HDFS с учётом их особенностей.
Done 🚀 failed, but after two years we've done it: https://benchmark.clickhouse.com/
Performance comparison of modern time-series DBMS.
Зарезервирована для Матвея Бубнова.
Задача не требует знания C++.
Существуют мало известные специализированные СУБД, способные конкурировать с ClickHouse по скорости обработки некоторых классов запросов. Пример: TDEngine и DolphinDB, VictoriaMetrics, а также Apache Doris и LocustDB. Предлагается изучить и классифицировать архитектурные особенности этих систем - их особенности и преимущества. Установить эти системы, загрузить тестовые данные, изучить производительность. Проанализировать, за счёт чего достигаются преимущества.
Functions for time series analysis in ClickHouse.
Тема свободна.
В time-series СУБД нужны функции, которые зависят от последовательности значений. Или даже от последовательности значений и их меток времени. Примеры: moving average, exponential smoothing, derivative, Holt-Winters forecast. Вычисление таких функций поддерживается в ClickHouse лишь частично. Так, ClickHouse поддерживает тип данных "массив" и позволяет реализовать эти функции как функции, принимающие массивы. Но гораздо удобнее для пользователя было бы иметь возможность применить такие функции к таблице (промежуточному результату запроса после сортировки).
Это требует введение нового класса функций (помимо обычных и агрегатных функций) - такие функции будут иметь в коде ClickHouse свой собственный интерфейс, и их вычисление придётся отдельно учитывать в конвейере выполнения запросов. Для примера, вычисление обычных функций тривиально распараллеливается по процессорным ядрам и по серверам; вычисление агрегатных функций распараллеливается с некоторыми особенностями (работа с промежуточными состояниями вычислений, операция merge); а для функций по обработке временных рядов этот вопрос остаётся открытым - возможно, их придётся вычислять на одном сервере и в одном потоке.
Done 🚀
Type inference for data formats by data example.
Задача свободна.
ClickHouse является строго типизированной системой. Для того, чтобы прочитать данные в каком либо формате (например, CSV), требуется заранее указать типы данных. Если при чтении формата выясняется, что данные не могут быть прочитаны в рамках заданных типов, то кидается исключение.
ClickHouse также может использоваться для быстрой аналитики по локальным файлам, без загрузки их в базу данных (программа clickhouse-local). В этом случае, его использование может заменить awk, sed, grep. Но остаётся неудобство - необходимость указания типов данных.
Предлагается реализовать функциональность вывода типов по первому блоку данных путём применения эвристик и постепенного расширения типов.
Другая экспериментальная задача - реализация эвристик для обработки данных в неизвестном построчном текстовом формате. Детектирование CSV, TSV, JSON, детектирование разделителей и форматов значений.
Integration of data cache and memory allocator.
Задача зарезервирована для Михаила Кот.
Требование к задаче: интерес к низкоуровневому коду на C и C++. Для данной задачи потребуется ознакомиться с внутренним устройством аллокаторов памяти (malloc), таким как tcmalloc, jemalloc.
Для выделения памяти, аллокаторы запрашивают её у операционной системы (mmap). Это возможно только для достаточно крупных кусков памяти является довольно медленной операцией. Поэтому, современные аллокаторы кэшируют крупные куски памяти в программе. При вызове free, кусок памяти, как правило, не отдаётся ОС, а остаётся для последующего переиспользования. Для выделения мелких кусков памяти, крупные куски разбиваются с помощью специальных структур данных (free-list, heap, bitmap). Для уменьшения contention в многопоточных программах, эти структуры также делаются thread-локальными.
Часто в программе есть кэши некоторых данных. Например - кэш данных после разжатия, использующийся чтобы сэкономить на повторных запросах одних и тех же данных. При вытеснении из кэша, блок данных освобождается (free) и данные, бывшие в кэше, становятся недоступными для переиспользования. Но если принимать во внимание то, как работает аллокатор памяти, то оказывается, что после освобождения памяти, данные всё ещё остаются доступными в программе. И если этот кусок памяти не будет выделен аллокатором снова, его можно было бы продолжить использовать в качестве кэша. Иными словами, в программе есть domain-specific кэш, а аллокатор имеет свой кэш, и они не знают друг о друге.
Для domain-specific кэшей (как например, кэш разжатых данных) выгодно, чтобы они использовали как можно больший объём свободной памяти. Но в этом случае, памяти может не хватить для других структур данных в программе. Если аллокатор памяти знает про кэш, то выделение памяти можно было бы делать путём вытеснения данных из кэша.
In progress.
Minimal support for transactions in ClickHouse.
Зарезервировано для Максима Кузнецова.
Таблицы типа MergeTree состоят из набора независимых неизменяемых "кусков" данных. При вставках данных (INSERT), формируются новые куски. При модификациях данных (слияние кусков), формируются новые куски, а старые - становятся неактивными и перестают использоваться следующими запросами. Чтение данных (SELECT) производится из снэпшота множества кусков на некоторый момент времени. Таким образом, чтения и вставки не блокируют друг друга.
Если же выполняется несколько запросов SELECT, то чтение данных может осуществляться из снэпшотов по состоянию на несколько разных моментов времени и быть неконсистентным. Пример: пользователю отображается отчёт из нескольких графиков и таблиц, но из-за того, что между разными запросами, данные успели обновиться, отображаемые данные не соответствуют друг другу.
Пример с другой стороны - пользователь хочет осуществить несколько вставок (INSERT) в одну или несколько таблиц, но так, чтобы данные появились в них атомарно с точки зрения других запросов (SELECT).
Для решения этих проблем, предлагается ввести глобальные метки времени для кусков данных (сейчас уже есть инкрементальные номера кусков, но они выделяются в рамках одной таблицы). Первым шагом сделаем эти метки времени в рамках сервера. Вторым шагом сделаем метки времени в рамках всех серверов, но неточные на основе локальных часов. Третьим шагом сделаем метки времени, выдаваемые сервисом координации.
Done 🚀
Implementation of a dashboard for working with pull requests.
Задача свободна.
Задача не требует знания C++.
Над ClickHouse одновременно работает большое количество разработчиков, которые оформляют свои изменения в виде pull requests. Когда непомерженных pull requests много, то возникает сложность с организацией работы - непонятно, на какой pull request смотреть в первую очередь.
Предлагается реализовать простое одностраничное веб-приложение, в котором отображается список pull requests со следующей информацией:
- размер diff - количество изменённых строк;
- как давно было последнее обновление;
- типы изменённых файлов: C++, документация, скрипты сборки;
- наличие добавленных тестов;
- есть ли описание для changelog;
- изменены ли submodules;
- был ли разрешён запуск проверок CI;
- статусы проверок CI;
- количество approve от ревьюеров;
Статусы проверок - наиболее важная часть. Так как для каждого PR выполняется несколько десятков проверок и наиболее медленные работают до нескольких часов, придётся:
- отображать сразу все проверки для каждого PR в виде красивой разноцветной матрицы с информацией по наведению мыши;
- отсортировать проверки по важности: например, если у внешнего разработчика проходят все проверки кроме стиля кода, то мы можем взять это в работу сами;
- если для предыдущего коммита проверка была завершена, а для последнего коммита ещё только идёт - то можно отображать в таблице статус предыдущей проверки более блёклым цветом.
Предлагается реализовать несколько вариантов сортировок. Очевидное - по времени обновления, более интересно - некое ранжирование с целью выяснить, "что лучше взять в работу прямо сейчас".
Похожие продукты уже есть, например: http://prs.mozilla.io/yandex:ClickHouse К сожалению, этот продукт заброшен, да и делает не совсем то, что нужно. По своему усмотрению, можно взять из него что-нибудь полезное.
Done 🚀
Integration of perf events for query performance metrics in ClickHouse.
Зарезервировано для Андрея Скобцова.
В Linux существует возможность получать в программе информацию о счётчиках производительности и событиях, относящихся к CPU и ядру ОС. Подробнее смотрите man perf_event_open. Предлагается добавить эти метрики в ClickHouse для инструментирования запросов.
Done 🚀
Development of the "Play.ClickHouse" website.
Задача зарезервирована для Азата Калмыкова.
Задача не требует знаний C++.
Цель состоит в реализации сайта, на котором можно попробовать задавать произвольные запросы к временному экземпляру ClickHouse и изучать его поведение. Из похожих проектов можно отметить: Compiler Explorer, http://ideone.com/, SQLFiddle, DB-Fiddle.
С помощью такого сайта можно решать следующие задачи:
- ознакомление с языком запросов ClickHouse;
- демонстрация примеров из документации;
- демонстрация скорости работы на тестовых датасетах;
- сравнение поведения разных версий ClickHouse друг с другом;
- демонстрация неожиданного поведения или багов;
Требуется проработать вопрос безопасности и изоляции инстансов (поднятие в контейнерах с ограничениями по сети), подключение тестовых датасетов с помощью copy-on-write файловой системы; органичения ресурсов.
Optimization of parallel GROUP BY with flat combining.
Зарезервировано для Максима Серебрякова.
Бонусная тема. Смотрите видео https://www.youtube.com/watch?v=SrucFOs8Y6c
Done but removed.
Implementation of differential privacy algorithms in ClickHouse.
Зарезервировано для Артёма Вишнякова.
Бонусная тема. Смотрите описание: ClickHouse/ClickHouse#6874 Тема свободна, если до момента выбора не найдётся другого исполнителя.
Done 🚀
Distributed Tracing Infrastructure for ClickHouse.
Бонусная тема.
Задача зарезервирована для Александра Кожихова.
Done 🚀
Infrastructure for training CatBoost models in ClickHouse.
Бонусная тема.
Зарезервировано для Александра Кожихова.
Not merged.
Implementation of compact floating point data types in ClickHouse.
Зарезервировано для Рустама Гусейн-заде
In progress.
Integration of HTTP User Agent processing in ClickHouse.
Зарезервировано для Михаила Филитова.