Перейти к основному содержимому
Перейти к основному содержимому

Стратегии дедупликации

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

ClickHouse построен для повышения скорости при вставке данных. Файлы хранения неизменяемы, и ClickHouse не проверяет наличие существующего первичного ключа перед вставкой строки, поэтому дедупликация требует немного больше усилий. Это также означает, что дедупликация не мгновенна — она будет выполнена позже, что имеет несколько побочных эффектов:

  • В любой момент времени в вашей таблице могут все еще быть дубликаты (строки с одинаковым ключом сортировки)
  • Фактическое удаление дублирующих строк происходит во время слияния частей
  • Ваши запросы должны учитывать возможность наличия дубликатов
Логотип дедупликации
ClickHouse предоставляет бесплатное обучение по дедупликации и многим другим темам. Модуль Обучение удалению и обновлению данных является хорошим местом для начала.

Опции для дедупликации​

Дедупликация реализована в ClickHouse с использованием следующих движков таблиц:

  1. Движок таблиц ReplacingMergeTree: с этим движком дублирующие строки с одинаковым ключом сортировки удаляются во время слияний. ReplacingMergeTree — хорошая опция для эмуляции поведения upsert (когда вы хотите, чтобы запросы возвращали последнюю вставленную строку).

  2. Слияние строк: движки таблиц CollapsingMergeTree и VersionedCollapsingMergeTree используют логику, при которой существующая строка "аннулируется", и вставляется новая строка. Они сложнее в реализации, чем ReplacingMergeTree, но ваши запросы и агрегации могут быть проще в написании, без необходимости беспокоиться о том, были ли данные уже слиты. Эти два движка таблиц полезны, когда вам нужно часто обновлять данные.

Мы рассмотрим обе эти техники ниже. Для получения более подробной информации ознакомьтесь с нашим бесплатным модулем Обучение удалению и обновлению данных.

Использование ReplacingMergeTree для Upsert​

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

CREATE TABLE hackernews_rmt (
    id UInt32,
    author String,
    comment String,
    views UInt64
)
ENGINE = ReplacingMergeTree
PRIMARY KEY (author, id)

Давайте вставим две строки:

INSERT INTO hackernews_rmt VALUES
   (1, 'ricardo', 'This is post #1', 0),
   (2, 'ch_fan', 'This is post #2', 0)

Чтобы обновить колонку views, вставьте новую строку с тем же первичным ключом (обратите внимание на новые значения колонки views):

INSERT INTO hackernews_rmt VALUES
   (1, 'ricardo', 'This is post #1', 100),
   (2, 'ch_fan', 'This is post #2', 200)

Теперь таблица имеет 4 строки:

SELECT *
FROM hackernews_rmt

┌─id─┬─author──┬─comment─────────┬─views─┐
│  2 │ ch_fan  │ This is post #2 │     0 │
│  1 │ ricardo │ This is post #1 │     0 │
└────┴─────────┴─────────────────┴───────┘
┌─id─┬─author──┬─comment─────────┬─views─┐
│  2 │ ch_fan  │ This is post #2 │   200 │
│  1 │ ricardo │ This is post #1 │   100 │
└────┴─────────┴─────────────────┴───────┘

Отдельные ящики выше в выводе демонстрируют две части за кулисами - эти данные еще не были слиты, поэтому дублирующие строки еще не были удалены. Давайте используем ключевое слово FINAL в запросе SELECT, что приведет к логическому слиянию результата запроса:

SELECT *
FROM hackernews_rmt
FINAL

┌─id─┬─author──┬─comment─────────┬─views─┐
│  2 │ ch_fan  │ This is post #2 │   200 │
│  1 │ ricardo │ This is post #1 │   100 │
└────┴─────────┴─────────────────┴───────┘

Результат имеет только 2 строки, и последняя вставленная строка — это строка, которая возвращается.

примечание

Использование FINAL работает нормально, если у вас маленькое количество данных. Если вы имеете дело с большим объемом данных, использование FINAL вероятно, не является лучшим вариантом. Давайте обсудим лучшую опцию для поиска последнего значения колонки.

Избежание FINAL​

Давайте снова обновим колонку views для обеих уникальных строк:

INSERT INTO hackernews_rmt VALUES
   (1, 'ricardo', 'This is post #1', 150),
   (2, 'ch_fan', 'This is post #2', 250)

Теперь таблица имеет 6 строк, потому что фактическое слияние еще не произошло (только слияние во время запроса, когда мы использовали FINAL).

SELECT *
FROM hackernews_rmt

┌─id─┬─author──┬─comment─────────┬─views─┐
│  2 │ ch_fan  │ This is post #2 │   200 │
│  1 │ ricardo │ This is post #1 │   100 │
└────┴─────────┴─────────────────┴───────┘
┌─id─┬─author──┬─comment─────────┬─views─┐
│  2 │ ch_fan  │ This is post #2 │     0 │
│  1 │ ricardo │ This is post #1 │     0 │
└────┴─────────┴─────────────────┴───────┘
┌─id─┬─author──┬─comment─────────┬─views─┐
│  2 │ ch_fan  │ This is post #2 │   250 │
│  1 │ ricardo │ This is post #1 │   150 │
└────┴─────────┴─────────────────┴───────┘

Вместо использования FINAL давайте воспользуемся бизнес-логикой — мы знаем, что колонка views всегда увеличивается, поэтому мы можем выбрать строку с максимальным значением, используя функцию max после группировки по нужным колонкам:

SELECT
    id,
    author,
    comment,
    max(views)
FROM hackernews_rmt
GROUP BY (id, author, comment)

┌─id─┬─author──┬─comment─────────┬─max(views)─┐
│  2 │ ch_fan  │ This is post #2 │        250 │
│  1 │ ricardo │ This is post #1 │        150 │
└────┴─────────┴─────────────────┴────────────┘

Группировка, как показано в запросе выше, может быть фактически более эффективной (с точки зрения производительности запроса), чем использование ключевого слова FINAL.

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

Использование CollapsingMergeTree для частого обновления колонок​

Обновление колонки включает в себя удаление существующей строки и замену ее новыми значениями. Как вы уже видели, этот тип мутации в ClickHouse происходит в конечном итоге — во время слияний. Если у вас много строк для обновления, фактически может быть более эффективно избежать ALTER TABLE..UPDATE и вместо этого просто вставить новые данные наряду с существующими данными. Мы могли бы добавить колонку, которая указывает, является ли данными устаревшими или новыми... и на самом деле есть движок таблицы, который уже прекрасно реализует это поведение, особенно учитывая, что он автоматически удаляет устаревшие данные за вас. Давайте посмотрим, как это работает.

Предположим, мы отслеживаем количество просмотров, которые имеет комментарий Hacker News, с помощью внешней системы, и каждые несколько часов мы отправляем данные в ClickHouse. Мы хотим, чтобы старые строки были удалены, а новые строки отражали новое состояние каждого комментария Hacker News. Мы можем использовать CollapsingMergeTree для реализации этого поведения.

Давайте определим таблицу для хранения количества просмотров:

CREATE TABLE hackernews_views (
    id UInt32,
    author String,
    views UInt64,
    sign Int8
)
ENGINE = CollapsingMergeTree(sign)
PRIMARY KEY (id, author)

Обратите внимание, что таблица hackernews_views имеет колонку Int8 с именем sign, которая называется колонкой знака. Название колонки знака произвольно, но тип данных Int8 является обязательным, и обратите внимание, что имя колонки было передано в конструктор движка таблицы CollapsingMergeTree.

Какова колонка знака таблицы CollapsingMergeTree? Она представляет состояние строки, и колонка знака может быть только 1 или -1. Вот как это работает:

  • Если две строки имеют одинаковый первичный ключ (или порядок сортировки, если он отличается от первичного ключа), но различные значения колонки знака, то последняя вставленная строка с +1 становится состоянием строки, а другие строки аннулируются
  • Строки, которые аннулируют друг друга, удаляются во время слияний
  • Строки, не имеющие соответствующей пары, сохраняются

Давайте добавим строку в таблицу hackernews_views. Поскольку это единственная строка для этого первичного ключа, мы устанавливаем ее состояние в 1:

INSERT INTO hackernews_views VALUES
   (123, 'ricardo', 0, 1)

Теперь предположим, что мы хотим изменить колонку просмотров. Вы вставляете две строки: одну, которая аннулирует существующую строку, и одну, которая содержит новое состояние строки:

INSERT INTO hackernews_views VALUES
   (123, 'ricardo', 0, -1),
   (123, 'ricardo', 150, 1)

Теперь таблица имеет 3 строки с первичным ключом (123, 'ricardo'):

SELECT *
FROM hackernews_views

┌──id─┬─author──┬─views─┬─sign─┐
│ 123 │ ricardo │     0 │   -1 │
│ 123 │ ricardo │   150 │    1 │
└─────┴─────────┴───────┴──────┘
┌──id─┬─author──┬─views─┬─sign─┐
│ 123 │ ricardo │     0 │    1 │
└─────┴─────────┴───────┴──────┘

Обратите внимание, что добавление FINAL возвращает текущую строку состояния:

SELECT *
FROM hackernews_views
FINAL

┌──id─┬─author──┬─views─┬─sign─┐
│ 123 │ ricardo │   150 │    1 │
└─────┴─────────┴───────┴──────┘

Но, конечно, использование FINAL не рекомендуется для больших таблиц.

примечание

Значение, переданное для колонки views в нашем примере, на самом деле не нужно, и оно не обязательно должно совпадать с текущим значением views старой строки. Фактически, вы можете аннулировать строку только с помощью первичного ключа и -1:

INSERT INTO hackernews_views(id, author, sign) VALUES
   (123, 'ricardo', -1)

Обновления в реальном времени из нескольких потоков​

С таблицей CollapsingMergeTree строки аннулируют друг друга, используя колонку знака, и состояние строки определяется последней вставленной строкой. Но это может быть проблемой, если вы вставляете строки из разных потоков, где строки могут быть вставлены вне порядка. Использование "последней" строки не работает в этой ситуации.

Здесь приходит на помощь VersionedCollapsingMergeTree — он аннулирует строки так же, как и CollapsingMergeTree, но вместо того, чтобы сохранять последнюю вставленную строку, он сохраняет строку с наибольшим значением колонки версии, которую вы указываете.

Рассмотрим пример. Предположим, мы хотим отслеживать количество просмотров наших комментариев Hacker News, и данные часто обновляются. Мы хотим, чтобы отчет использовал последние значения, не заставляя ждать слияний. Мы начинаем с таблицы, похожей на CollapsedMergeTree, за исключением того, что добавляем колонку для хранения версии состояния строки:

CREATE TABLE hackernews_views_vcmt (
    id UInt32,
    author String,
    views UInt64,
    sign Int8,
    version UInt32
)
ENGINE = VersionedCollapsingMergeTree(sign, version)
PRIMARY KEY (id, author)

Обратите внимание, что таблица использует VersionsedCollapsingMergeTree в качестве движка и передает колонку знака и колонку версии. Вот как работает таблица:

  • Она удаляет каждую пару строк, которые имеют одинаковый первичный ключ и версию, и разные знаки
  • Порядок, в котором строки были вставлены, не имеет значения
  • Обратите внимание, что если колонка версии не является частью первичного ключа, ClickHouse добавляет ее в первичный ключ неявно как последнее поле

Вы используете ту же логику при написании запросов — группируйте по первичному ключу и используйте умную логику, чтобы избежать строк, которые были аннулированы, но еще не удалены. Давайте добавим несколько строк в таблицу hackernews_views_vcmt:

INSERT INTO hackernews_views_vcmt VALUES
   (1, 'ricardo', 0, 1, 1),
   (2, 'ch_fan', 0, 1, 1),
   (3, 'kenny', 0, 1, 1)

Теперь мы обновляем две строки и удаляем одну из них. Чтобы аннулировать строку, обязательно укажите предыдущий номер версии (так как он является частью первичного ключа):

INSERT INTO hackernews_views_vcmt VALUES
   (1, 'ricardo', 0, -1, 1),
   (1, 'ricardo', 50, 1, 2),
   (2, 'ch_fan', 0, -1, 1),
   (3, 'kenny', 0, -1, 1),
   (3, 'kenny', 1000, 1, 2)

Мы выполним тот же запрос, что и раньше, который хитро суммирует и вычитает значения на основе колонки знака:

SELECT
    id,
    author,
    sum(views * sign)
FROM hackernews_views_vcmt
GROUP BY (id, author)
HAVING sum(sign) > 0
ORDER BY id ASC

Результат — две строки:

┌─id─┬─author──┬─sum(multiply(views, sign))─┐
│  1 │ ricardo │                         50 │
│  3 │ kenny   │                       1000 │
└────┴─────────┴────────────────────────────┘

Давайте принудительно выполним слияние таблицы:

OPTIMIZE TABLE hackernews_views_vcmt

В результате должно быть только две строки:

SELECT *
FROM hackernews_views_vcmt

┌─id─┬─author──┬─views─┬─sign─┬─version─┐
│  1 │ ricardo │    50 │    1 │       2 │
│  3 │ kenny   │  1000 │    1 │       2 │
└────┴─────────┴───────┴──────┴─────────┘

Таблица VersionedCollapsingMergeTree весьма полезна, когда вы хотите реализовать дедупликацию, вставляя строки из нескольких клиентов и/или потоков.

Почему мои строки не дублируются?​

Одна из причин, по которой вставленные строки могут не быть дублированными, заключается в том, что вы используете недетерминированную функцию или выражение в своем операторе INSERT. Например, если вы вставляете строки с колонкой createdAt DateTime64(3) DEFAULT now(), ваши строки гарантированно будут уникальными, поскольку каждая строка получит уникальное значение по умолчанию для колонки createdAt. Движок таблиц MergeTree / ReplicatedMergeTree не будет знать, как дедуплицировать строки, так как каждая вставленная строка будет генерировать уникальную контрольную сумму.

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