Не слишком глупые указатели в ClickHouse

Не слишком глупые указатели
в ClickHouse

Основа ClickHouse — столбцы

На диске — столбцы.
Данные хранятся по столбцам.

В оперативке — столбцы.
Данные обрабатываются по столбцам.

Как хранятся столбцы в оперативке

В виде кусочков столбцов — например, 65 536 элементов.

Размер кусочка — зависит от многих вещей.

При SELECT — см. настройку max_block_size.

Как хранятся столбцы в оперативке

Представлены в виде объектов с интерфейсом IColumn.

Варианты — ColumnVector<T>, ColumnString, ColumnArray...

ColumnVector<T> — почти как std::vector<T>.
Но под интерфейсом IColumn.
И вместо std::vector<T> — PODArray<T> (зачем?).

Как хранятся столбцы в оперативке

Раньше был std::vector. PODArray — просто оптимизация.

PODArray:
— нет лишнего memset;
— есть padding 15 байт на конце;
— использует интерфейс аллокатора, отличный от std::allocator, который позволяет иногда делать mremap.

Как хранятся столбцы в оперативке

ColumnString — из двух компонент:

1. Байты, уложенные подряд.
2. Смещения до i+1 строки.

h e l l o \0 w o r l d \0 6 12

Как хранятся столбцы в оперативке

ColumnConst

Из одного вложенного столбца,
содержащего одно значение.

Что даёт интерфейс IColumn

Базовые операции:
— cut — вырезать часть столбца, для реализации LIMIT;
— filter — для реализации WHERE;
— compareAt, permute — для реализации ORDER BY;
...

Почти все операции immutable

virtual Ptr filter(const Filter & filt, ssize_t result_size_hint) const = 0;

Вместо модификации содержимого, создают
и возвращают новый объект-столбец.

Это нормально, так как операции "крупные".

Но есть также "мелкие", мутирующие операции.

IColumn, за что отвечает:

— хранение данных в оперативке;
— общие операции над столбцами.

IColumn, на что похоже:

— Apache Arrow;
— массивы в NumPy;
— массивы APL, J, K.

Мотивация

Изолировать максимально эффективные
внутренние циклы от кода-обвязки.

Код не обязан быть эффективным целиком.

Оптимизируемые места должны быть локализуемы.

«векторный движок»

Бонус:
— SIMD инструкции;
— хитрые оптимизации для однородных данных
(IColumn::filter, реализация функции LIKE);

Common Subexpression Elimination

SELECT f(x + y), g(x + y)

x + y — одинаковое выражение, встречающееся несколько раз.

SELECT x + y AS a, x + y AS b

a и b — на самом деле одни и те же столбцы.

Простое, изящное и неправильное решение:
— использовать shared_ptr<IColumn>.

Столбцы a и b будут просто ссылаться на одно и то же.

Common Subexpression Elimination

SELECT f(x + y), g(x + y)

AST запроса тоже можно склеить — превратить из дерева в DAG:

  x   y   x   y              x   y
   ↘ ↙     ↘ ↙                ↘ ↙
    +       +                  +
    ↓       ↓      −−−>       ↙ ↘
    f       g                f   g
     ↘     ↙                 ↓   ↓
      SELECT                 SELECT

Использовать для узлов shared_ptr<IAST> и расшарить одинаковые узлы.

Все вычисления функций immutable

Вычисления:

c1 = x;
c2 = y;
c3 = plus(c1, c2);
c4 = f(c3);
c5 = g(c3);

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

Проблемы использования shared_ptr

Часть операций mutable.

Например:
IColumn::insert — вставить в конец столбца одно значение;
IColumn::insertRangeFrom — вставить в конец столбца кусок другого.

Пример использования:

INSERT INTO table SELECT a, b FROM other

— склейка мелких блоков в более крупные при INSERT;
— но mutable операции нельзя применять к shared данным.

Persistent data structures?

Проблемы использования shared_ptr

Если AST склеено в DAG с помощью shared_ptr,
то переписывание одного куска запроса меняет другой.

Очевидное решение

Использовать shared_ptr<const T> для разделяемых данных
и unique_ptr<T>, когда данные надо менять.

Пример:

// Создаём объект и меняем его. std::unique_ptr<T> u{std::make_unique<T>()}; u->modify(); // Когда объект готов, его можно разделять. std::shared_ptr<const T> s1{std::move(u)}; std::shared_ptr<const T> s2 = s1; // Разделяемый объект никто не может менять.

Очевидное решение

Если нужно поменять разделяемый объект?
— просто клонируем его:

// Создаём объект и меняем его. std::unique_ptr<T> u{std::make_unique<T>()}; u->modify(); // Когда объект готов, его можно разделять. std::shared_ptr<const T> s1{u.release()}; std::shared_ptr<const T> s2 = s1; // Разделяемый объект никто не может менять. // Но может клонировать, а потом менять новую копию. std::unique_ptr<T> u2{s2->clone()}; u2->modify();

Очевидное решение

Склейка мелких блоков в более крупные.

Было:

result->insertRangeFrom(*source, 0, length);

Стало:

result_mutable = result->clone(); result_mutable->insertRangeFrom(*source, 0, length); result = result_mutable;

Лишнее копирование, даже если refcount == 1.
В случае многих итераций, все копирования кроме первого,
будут гарантированно лишними.

Очевидное решение

Лишнее копирование, даже если refcount == 1.

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

 

Можно ли клонировать объект только если refcount > 1 а иначе
магическим образом преобразовывать shared_ptr в unique_ptr?

Нет, потому что у них разные memory layout и вообще всё.

sizeof(unique_ptr<T>) == sizeof(void*)
sizeof(shared_ptr<T>) == 2 * sizeof(void*)

(в реализации libc++ или libstdc++)

Copy-on-write?

Техника copy-on-write печально известна
по старым реализациям std::string.

Пример: libstdc++ с old C++ ABI по-умолчанию в gcc до 5.1.

CoW-строки тормозят.

https://www.youtube.com/watch?v=rJWSSWYL83U

Copy-on-write?

Почему CoW-строки — не очень хорошо:

— реализация CoW требует подсчёта refcount, что требует атомарных операций в многопоточных программах;

— но в типичных случаях, большинство строк мелкие и их копирование (при наличии SSO или хорошего аллокатора) дешевле изменения refcnt;

— копирование при модификации осуществляется неявным образом, что требует крайне сложного кода;

— в особенности для корректной поддержки non-const iterator
и non-const operator[];

— начиная с C++11, move заменяет копирования временных объектов;

Copy-on-write?

CoW не нужно использовать:

1. Для мелких объектов, которые легко копировать.

но если объект тяжёлый, то лучше его разделять
и увеличивать refcount вместо копирования
.

Пример: fbstring использует CoW для длинных строк и SSO для мелких.

2. Если копирование выполняется неявно.

но можно сделать один метод, который даёт доступ
к non-const части интерфейса (подготовить объект к изменению)
клонировать, если refcount > 1 или "reinterpret_cast" иначе
.

Разумный CoW

// Creating and assigning to immutable ptr. COW<T>::Ptr x = COW<T>::create(1); // Sharing single immutable object in two ptrs. COW<T>::Ptr y = x; // Now x and y are shared. // Change value of x. { // Creating mutable ptr. // It can clone an object under the hood if it was shared. COW<T>::MutablePtr mutate_x = std::move(*x).mutate(); // Using non-const methods of an object. mutate_x->set(2); // Assigning pointer 'x' to mutated object. x = std::move(mutate_x); } // Now x and y are unshared and have different values.

Разумный CoW

COW<T>::Ptr — ведёт себя аналогично std::shared_ptr<const T>

COW<T>::MutablePtr — ведёт себя аналогично std::unique_ptr<T>

Преобразование mutable в immutable:

COW<T>::MutablePtr x; COW<T>::Ptr y = std::move(x);

Преобразование immutable в mutable:

COW<T>::Ptr x; COW<T>::MutablePtr y = std::move(*x).mutate();

— выполняет копирование, если refcount > 1.

Разумный CoW

std::move(*x).mutate();

или

std::move(x)->mutate();

?

1. В C++ нет rvalue qualified operator->
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3723.html

2. Хотим инвалидировать само значение, а не Ptr.
(у Ptr мы ещё можем использовать оператор присваивания)
Update после доклада: на самом деле нет проблем с вызовом
оператора присваивания после move.

Реализация

template <typename Derived> class COW : public boost::intrusive_ref_counter<Derived>

— будем использовать интрузивный указатель
— добавляем к объекту refcount.

class IColumn : public COW<IColumn> { private: friend class COW<IColumn>; virtual MutablePtr clone() const = 0;

— метод COW<T>::mutate будет вызывать T::clone, если надо.

Реализация

template <typename Derived> class COW : public boost::intrusive_ref_counter<Derived> { template <typename T> class IntrusivePtr : public boost::intrusive_ptr<T> {...} protected: template <typename T> class mutable_ptr : public IntrusivePtr<T> {...} public: using MutablePtr = mutable_ptr<Derived>; protected: template <typename T> class immutable_ptr : public IntrusivePtr<const T> {...} public: using Ptr = immutable_ptr<Derived>; }
template <typename T> class mutable_ptr : public IntrusivePtr<T> { ... public: /// Copy: not possible. mutable_ptr(const mutable_ptr &) = delete; /// Move: ok. mutable_ptr(mutable_ptr &&) = default; mutable_ptr & operator=(mutable_ptr &&) = default; /// Initializing from temporary of compatible type. template <typename U> mutable_ptr(mutable_ptr<U> && other) : Base(std::move(other)) {} mutable_ptr() = default; mutable_ptr(std::nullptr_t) {} };
template <typename T> class immutable_ptr : public IntrusivePtr<const T> { ... public: /// Copy from immutable ptr: ok. immutable_ptr(const immutable_ptr &) = default; immutable_ptr & operator=(const immutable_ptr &) = default; template <typename U> immutable_ptr(const immutable_ptr<U> & other) : Base(other) {} /// Move: ok. immutable_ptr(immutable_ptr &&) = default; immutable_ptr & operator=(immutable_ptr &&) = default; /// Initializing from temporary of compatible type. template <typename U> immutable_ptr(immutable_ptr<U> && other) : Base(std::move(other)) {} /// Move from mutable ptr: ok. template <typename U> immutable_ptr(mutable_ptr<U> && other) : Base(std::move(other)) {} /// Copy from mutable ptr: not possible. template <typename U> immutable_ptr(const mutable_ptr<U> &) = delete; immutable_ptr() = default; immutable_ptr(std::nullptr_t) {} };
class COW : public boost::intrusive_ref_counter<Derived> { protected: MutablePtr shallowMutate() const { if (this->use_count() > 1) return derived()->clone(); else return assumeMutable(); } public: MutablePtr mutate() const && { return shallowMutate(); } MutablePtr assumeMutable() const { return const_cast<COW*>(this)->getPtr(); } Derived & assumeMutableRef() const { return const_cast<Derived &>(*derived()); }

Наследование

template <typename Base, typename Derived> class COWHelper : public Base class IColumn : public COW<IColumn> { friend class COW<IColumn>; virtual MutablePtr clone() const = 0; virtual ~IColumn() {} }; class ConcreteColumn : public COWHelper<IColumn, ConcreteColumn> { friend class COWHelper<IColumn, ConcreteColumn>; };

Наследование

Диаграмма наследования:

boost::intrusive_ref_counter<IColumn>
                
          COW<IColumn>
                
             IColumn
                
   COWHelper<IColumn, ConcreteColumn>
                
          ConcreteColumn

Композиция / агрегация

class ColumnPair final : public COWHelper<IColumn, ColumnPair> { private: SomePtr a; SomePtr b; }

Непонятно, делать ли члены класса MutablePtr или Ptr?

Композиция / агрегация

Подход 1: immutable члены.

Объект содержит внутри себя immutable члены.
Во всех non-const методах вызывается mutate,
производятся изменения и присваивание обратно.

Недостатки:

Лишние проверки и атомарные операции
при каждом вызове non-const методов.

Композиция / агрегация

Подход 2: mutable члены.

Объект содержит внутри себя mutable члены.
Два объекта не могут иметь разделяемые члены класса.

Недостатки:

Разделяемые члены класса нужны.
Пример: столбцы с массивами, имеющими совпадающие длины.

Композиция / агрегация

Подход 3: immutable члены и deep-мутация.

Объект содержит внутри себя immutable члены.
Метод mutate делает глубокую мутацию всех членов класса,
что гарантирует их уникальность в mutable объектах.
Во всех non-const методах используется assumeMutableRef.

Недостатки:

Сложная реализация.
Метод assumeMutableRef небезопасен.

Композиция / агрегация

std::experimental::propagate_const

Композиция / агрегация

Подход 4: chameleon_ptr.

Объект содержит внутри себя chameleon члены.
Которые ведут себя как immutable, если объект const
и как mutable, если объект не const.

template <typename T> class chameleon_ptr { private: immutable_ptr value; public: const T & operator*() const { return *value; } T & operator*() { return value->assumeMutableRef(); } ... }

Полиморфизм типов по const

using T = X; using const T = Y;

Где X и Y — разные типы с одинаковым memory layout.
T работает примерно как union { X x; Y y; }.

template <typename T> using COWPtr<T> = mutable_ptr<T>; template <typename T> using const COWPtr<T> = immutable_ptr<T>;

Полиморфизм типов по const

Вряд ли стоит делать это в C++.

C++ и так уже слишком сложный :)

https://github.com/yandex/ClickHouse/
    blob/master/dbms/src/Common/COW.h

— 300 строк кода, из них 40% — комментарии.

.