Компания
633,28
рейтинг
17 декабря 2015 в 13:10

Разработка → Эволюция структур данных в Яндекс.Метрике

Яндекс.Метрика сегодня это не только система веб-аналитики, но и AppMetrica — система аналитики для приложений. На входе в Метрику мы имеем поток данных — событий, происходящих на сайтах или в приложениях. Наша задача — обработать эти данные и представить их в подходящем для анализа виде.



Но обработка данных — это не проблема. Проблема в том, как и в каком виде сохранять результаты обработки, чтобы с ними можно было удобно работать. В процессе разработки нам приходилось несколько раз полностью менять подход к организации хранения данных. Мы начинали с таблиц MyISAM, использовали LSM-деревья и в конце концов пришли к column-oriented базе данных. В этой статье я хочу рассказать, что нас вынуждало это делать.

Яндекс.Метрика работает с 2008 года — более семи лет. Каждый раз изменение подхода к хранению данных было обусловлено тем, что то или иное решение работало слишком плохо — с недостаточным запасом по производительности, недостаточно надёжно и с большим количеством проблем при эксплуатации, использовало слишком много вычислительных ресурсов, или же просто не позволяло нам реализовать то, что мы хотим.

В старой Метрике для сайтов, имеется около 40 «фиксированных» отчётов (например, отчёт по географии посетителей), несколько инструментов для in-page аналитики (например, карта кликов), Вебвизор (позволяет максимально подробно изучить действия отдельных посетителей) и, отдельно, конструктор отчётов.

В новой Метрике, а также в Appmetrica вместо «фиксированных» отчётов, каждый отчёт можно произвольным образом изменять. Можно добавлять новые измерения (например, в отчёт по поисковым фразам добавить ещё разбиение по страницам входа на сайт), сегментировать и сравнивать (можно сравнить источники трафика на сайт для всех посетителей и посетителей из Москвы), менять набор метрик и так далее. Конечно, это требует совершенно разных подходов к хранению данных.

MyISAM


В самом начале Метрика создавалась, как часть Директа. В Директе для решения задачи хранения статистики использовались MyISAM таблицы, и мы тоже с этого начали. Мы использовали MyISAM для хранения «фиксированных» отчётов с 2008 по 2011 год.

Давайте, я расскажу, какой должна быть структура таблицы для отчёта, например, по географии. Отчёт показывается для конкретного сайта (точнее, номера счётчика Метрики). Значит, в первичный ключ должен входить номер счётчика — CounterID. Пользователь может выбрать произвольный отчётный период. Сохранять данные для каждой пары дат было бы неразумно, поэтому они сохраняются для каждой даты и затем при запросе суммируются для заданного интервала. То есть в первичный ключ входит дата — Date.

В отчёте данные отображаются для регионов в виде дерева из стран, областей, городов, либо в виде списка. Разумно поместить в первичный ключ таблицы идентификатор региона (RegionID), а собирать данные в дерево уже на стороне прикладного кода, а не базы данных.

Ещё считается, например, средняя продолжительность визита. Значит, в столбцах таблицы должно быть количество визитов и суммарная продолжительность визитов.

В итоге, структура таблицы такая: CounterID, Date, RegionID -> Visits, SumVisitTime,… Рассмотрим, что происходит, когда мы хотим получить отчёт. Делается запрос SELECT с условием WHERE CounterID = c AND Date BETWEEN min_date AND max_date. То есть происходит чтение по диапазону первичного ключа.

Как реально хранятся данные на диске?


MyISAM таблица представляет собой файл с данными и файл с индексами. Если из таблицы ничего не удалялось и строчки не меняли своей длины при обновлении, то файл с данными будет представлять собой сериализованные строчки, уложенные подряд в порядке их добавления. Индекс (в том числе, первичный ключ) представляет собой B-дерево, в листьях которого находятся смещения в файле с данными. Когда мы читаем данные по диапазону индекса, из индекса достаётся множество смещений в файле с данными. Затем по этому множеству смещений делаются чтения из файла с данными.

Предположим естественную ситуацию, когда индекс находится в оперативке (key cache в MySQL или системный page cache), а данные не закэшированы в ней. Предположим, что мы используем жёсткие диски. Время для чтения данных зависит от того, какой объём данных нужно прочитать и сколько нужно сделать seek-ов. Количество seek-ов определяется локальностью расположения данных на диске.

События в Метрику поступают в порядке, почти соответствующем времени событий. В этом входящем потоке данные разных счётчиков разбросаны совершенно произвольным образом. То есть, входящие данные локальны по времени, но не локальны по номеру счётчика. При записи в MyISAM таблицу данные разных счётчиков будут также расположены совершенно случайным образом, а это значит, что для чтения данных отчёта необходимо будет выполнить примерно столько случайных чтений, сколько есть нужных нам строк в таблице.

Обычный жёсткий диск 7200 RPM умеет выполнять от 100 до 200 случайных чтений в секунду, RAID-массив при грамотном использовании — пропорционально больше. Один SSD пятилетней давности умеет выполнять 30 000 случайных чтений в секунду, но мы не можем позволить себе хранить наши данные на SSD. Таким образом, если для нашего отчёта нужно прочитать 10 000 строк, то это вряд ли займёт меньше 10 секунд, что полностью неприемлемо.

Для чтений по диапазону первичного ключа лучше подходит InnoDB, так как в InnoDB используется кластерный первичный ключ (то есть, данные хранятся упорядоченно по первичному ключу). Но InnoDB было невозможно использовать из-за низкой скорости записи. Если читая этот текст, вы вспомнили про TokuDB, то продолжайте читать этот текст.

Для того чтобы MyISAM работала быстрее при выборе по диапазону первичного ключа, применялись некоторые трюки.

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

Партиционирование. Таблица разбивается на некоторое количество более маленьких по диапазонам первичного ключа. При этом есть надежда, что данные одной партиции будут храниться более-менее локально, и запросы по диапазону первичного ключа будут работать быстрее. Этот метод можно называть «кластерный первичный ключ вручную». При этом вставка данных несколько замедляется. Выбирая количество партиций, как правило, удаётся достичь компромисса между скоростью вставок и чтений.

Разделение данных на поколения. При одной схеме партиционирования могут слишком тормозить чтения, при другой — вставки, а при промежуточной — и то, и другое. В этом случае возможно разделение данных на несколько поколений. Например, первое поколение назовём оперативными данными — там партиционирование производится в порядке вставки (по времени) или не производится вообще. Второе поколение назовём архивными данными — там оно производится в порядке чтения (по номеру счётчика). Данные переносятся из поколения в поколение скриптом, но не слишком часто (например, раз в день). Данные считываются сразу из всех поколений. Это, как правило, помогает, но добавляет довольно много сложностей.

Все эти трюки (и некоторые другие) использовались в Яндекс.Метрике когда-то давно для того, чтобы всё хоть как-то работало.

Резюмируем, какие имеются недостатки:

  • локальность данных на диске очень сложно поддерживается;
  • таблицы блокируются при записи данных;
  • репликация работает медленно, реплики зачастую отстают;
  • консистентность данных после сбоя не обеспечивается;
  • такие агрегаты, как количество уникальных пользователей, очень сложно рассчитываются и хранятся;
  • сжатие данных использовать затруднительно; оно работает неэффективно;
  • индексы занимают много места и зачастую не помещаются в оперативку;
  • данные необходимо шардировать вручную;
  • много вычислений приходится делать на стороне прикладного кода после SELECT-а;
  • сложная эксплуатация.



Локальность данных на диске, образное представление

В целом использование MyISAM было крайне неудобным. В дневное время серверы работали со 100% нагрузкой на дисковые массивы (постоянное перемещение головок). В таких условиях диски выходят из строя чаще, чем обычно. На серверах мы использовали дисковые полки (16 дисков) — то есть, довольно часто приходилось восстанавливать RAID-массивы. При этом репликация отставла ещё больше и иногда реплику приходилось наливать заново. Переключение мастера крайне неудобно. Для выбора реплики, на которую отправляются запросы, мы использовали MySQL Proxy, и это использование было весьма неудачным (потом мы заменили его на HAProxy).

Несмотря на эти недостатки, по состоянию на 2011 год мы хранили в MyISAM таблицах более 580 миллиардов строк. Потом всё переконвертировали в Metrage, удалили и в итоге освободили много серверов.

Metrage


Мы используем Metrage для хранения фиксированных отчётов с 2010 года по настоящее время. Предположим, у вас имеется следующий сценарий работы:

  • данные постоянно записываются в базу небольшими batch-ами;
  • поток на запись сравнительно большой — несколько сотен тысяч строк в секунду;
  • запросов на чтение сравнительно мало — десятки-сотни запросов в секунду;
  • все чтения — по диапазону первичного ключа, до миллионов строк на один запрос;
  • строчки достаточно короткие — около 100 байт в несжатом виде.

Для такого хорошо подходит достаточно распространенная структура данных LSM-Tree. Она представляет собой сравнительно небольшой набор «кусков» данных на диске, каждый из которых содержит данные, отсортированные по первичному ключу. Новые данные сначала располагаются в какой-либо структуре данных в оперативке (MemTable), затем записываются на диск в новый сортированный кусок. Периодически в фоне несколько сортированных кусков объединяются в один более крупный сортированный (compaction). Таким образом постоянно поддерживается сравнительно небольшой набор кусков.

Среди встраиваемых структур данных LSM-Tree реализуют LevelDB, RocksDB. Она используется в HBase и Cassandra.



Metrage также представляет собой LSM-Tree. В качестве «строчек» в нём могут использоваться произвольные структуры данных (фиксированы на этапе компиляции). Каждая строчка — это пара ключ, значение. Ключ — это структура с операциями сравнения на равенство и неравенство. Значение — произвольная структура с операциями update (добавить что-нибудь) и merge (агрегировать, объединить с другим значением). Короче говоря, это CRDT.

В качестве значений могут выступать как простые структуры (кортеж чисел), так и более сложные (хэш-таблица для рассчёта количества уникальных посетителей, структура для карты кликов). С помощью операций update и merge постоянно выполняется инкрементальная агрегация данных:

  • во время вставки данных, при формировании новой пачки в оперативке;
  • во время фоновых слияний;
  • при запросах на чтение.

Также Metrage содержит нужную нам domain-specific логику, которая выполняется при запросах. Например, для отчёта по регионам ключ в таблице будет содержать идентификатор самого нижнего региона (город, посёлок), и если нам нужно получить отчёт по странам, то доагрегация данных в данные по странам будет произведена на стороне сервера БД.

Перечислю достоинства этой структуры данных:

  • Данные расположены достаточно локально на жёстком диске, чтения по диапазону первичного ключа работают быстро.
  • Данные сжимаются по блокам. За счёт хранения в упорядоченном виде, сжатие достаточно сильное при использовании быстрых алгоритмов сжатия (в 2010 году использовали QuickLZ, с 2011 используем LZ4).
  • Хранение данных в упорядоченном виде позволяет использовать разреженный индекс. Разреженный индекс — это массив значений первичного ключа для каждой N-ой строки (N порядка тысяч). Такой индекс получается максимально компактным и всегда помещается в оперативку.

Так как чтения выполняются не очень часто, но при этом читают достаточно много строк, то увеличение latency из-за наличия многих кусков и разжатия блока данных и чтение лишних строк из-за разреженности индекса не имеют значения.

Записанные куски данных не модифицируются. Это позволяет производить чтение и запись без блокировок — для чтения берётся снапшот данных. Используется простой и единообразный код, но при этом мы можем легко реализовать всю нужную нам domain-specific логику.

Нам пришлось написать Metrage вместо доработки какого-либо существующего решения, потому что какого-либо существующего решения не было. Например, LevelDB не существовала в 2010 году. TokuDB в то время была доступна только за деньги.

Все системы, реализующие LSM-Tree подходили для хранения неструктурированных данных и отображения типа BLOB -> BLOB с небольшими вариациями. Для адаптации подобной к работе с произвольными CRDT потребовалось бы гораздо больше времени, чем на разработку Metrage.

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

После перевода отчётов на Metrage мы сразу же получили преимущество в скорости работы интерфейса Метрики. Так 90% перцентиль времени загрузки отчёта по заголовкам страниц уменьшился с 26 секунд до 0.8 секунд (общее время, включая работу всех запросов к базам данных и последующих преобразований данных). Время обработки запросов самой Metrage (для всех отчётов) составляет: медиана — 6 мс, 90% — 31 мс, 99% — 334 мс.

Мы использовали Metrage в течение пяти лет, и она показала себя как надёжное беспроблемное решение. За всё время было всего лишь несколько незначительных сбоев. Преимущества в эффективности и в простоте использования, по сравнению с хранением данных в MyISAM, являются кардинальными.

Сейчас мы храним в Metrage 3.37 триллиона строк. Для этого используется 39 * 2 серверов. Мы постепенно отказываемся от хранения данных в Metrage и уже удалили несколько наиболее крупных таблиц. Но и у этой системы есть недостаток — эффективно работать можно только с фиксированными отчётами. Metrage выполняет агрегацию данных и хранит агрегированные данные. А для того чтобы это делать, нужно заранее перечислить все способы, которыми мы хотим агрегировать данные. Если мы будем делать это 40 разными способами, значит, в Метрике будет 40 отчётов, но не больше.

OLAPServer


В Яндекс.Метрике объём данных и величина нагрузки являются достаточно большими, чтобы основной проблемой было сделать решение, которое хотя бы работает — решает задачу и при этом справляется с нагрузкой в рамках адекватного количества вычислительных ресурсов. Поэтому зачастую основные усилия тратятся на то, чтобы создать минимальный работающий прототип.

Одним из таких прототипов был OLAPServer. Мы использовали OLAPServer с 2009 по 2013 год в качестве структуры данных для конструктора отчётов.

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

Имеем такой сценарий работы:

  • есть широкая «таблица фактов», содержащая большое количество столбцов (сотни);
  • при чтении вынимается достаточно большое количество строк из БД, но только небольшое подмножество столбцов;
  • запросы на чтение идут сравнительно редко (обычно не более сотни в секунду на сервер);
  • при выполнении простых запросов допустимы задержки в районе 50мс;
  • значения в столбцах достаточно мелкие — числа и небольшие строки (пример — 60 байт на URL);
  • требуется высокая пропускная способность при обработке одного запроса (до миллиардов строк в секунду на один сервер);
  • результат выполнения запроса существенно меньше исходных данных — то есть, данные фильтруются или агрегируются;
  • сравнительно простой сценарий обновления данных, обычно append-only batch-ами; нет сложных транзакций.

Для такого сценария работы (назовём его OLAP сценарий работы), наилучшим образом подходят столбцовые СУБД (column-oriented DBMS). Так называются СУБД, в которых данные для каждого столбца хранятся отдельно, а данные одного столбца — вместе.

Столбцовые СУБД эффективно работают для OLAP сценария работы по следующим причинам:

1. По I/O.

  1. Для выполнения аналитического запроса требуется прочитать небольшое количество столбцов таблицы. В столбцовой БД для этого можно читать только нужные данные. Например, если вам требуется только 5 столбцов из 100, то следует рассчитывать на 20-кратное уменьшение ввода-вывода.
  2. Так как данные читаются пачками, то их проще сжимать. Данные, лежащие по столбцам, также лучше сжимаются. За счёт этого дополнительно уменьшается объём ввода-вывода.
  3. За счёт уменьшения ввода-вывода, больше данных влезает в системный кэш.

Например, для запроса «посчитать количество записей для каждой рекламной системы» требуется прочитать один столбец «Идентификатор рекламной системы», который занимает 1 байт в несжатом виде. Если большинство переходов было не с рекламных систем, то можно рассчитывать хотя бы на десятикратное сжатие этого столбца. При использовании быстрого алгоритма сжатия возможно разжатие данных со скоростью более нескольких гигабайт несжатых данных в секунду. То есть, такой запрос может выполняться со скоростью около нескольких миллиардов строк в секунду на одном сервере.



2. По CPU.
Так как для выполнения запроса надо обработать достаточно большое количество строк, становится актуальным диспетчеризовывать все операции не для отдельных строк, а для целых векторов (пример — векторный движок в СУБД VectorWise) или реализовать движок выполнения запроса так, чтобы издержки на диспетчеризацию были примерно нулевыми (пример — кодогенерация с помощью LLVM в Cloudera Impala). Если этого не делать, то при любой не слишком плохой дисковой подсистеме интерпретатор запроса неизбежно упрётся в CPU. Имеет смысл не только хранить данные по столбцам, но и обрабатывать их по возможности тоже по столбцам.

Существует достаточно много столбцовых СУБД. Это, например, Vertica, Paraccel (Actian Matrix) (Amazon Redshift), Sybase IQ (SAP IQ), Exasol, Infobright, InfiniDB, MonetDB (VectorWise) (Actian Vector), LucidDB, SAP HANA, Google Dremel, Google PowerDrill, Metamarkets Druid, kdb+ и т. п.

В традиционно строковых СУБД последнее время тоже стали появляться решения для хранения данных по столбцам. Примеры — column store index в MS SQL Server, MemSQL, cstore_fdw для Postgres, форматы ORC-File и Parquet для Hadoop.

OLAPServer представляет собой простейшую и крайне ограниченную реализацию столбцовой базы данных. Так OLAPServer поддерживает всего лишь одну таблицу, заданную в compile time, — таблицу визитов. Обновление данных делается не в реальном времени, как везде в Метрике, а несколько раз в сутки. В качестве типов данных поддерживаются только числа фиксированной длины 1-8 байт. А в качестве запроса поддерживается лишь вариант SELECT keys..., aggregates... FROM table WHERE condition1 AND condition2 AND... GROUP BY keys ORDER BY column_nums....

Несмотря на такую ограниченную функциональность, OLAPServer успешно справлялся с задачей конструктора отчётов. Но не справлялся с задачей реализовать возможность кастомизации каждого отчёта Яндекс.Метрики. Например, если отчёт содержал URL-ы, то его нельзя было получить через конструктор отчётов, потому что OLAPServer не хранил URL-ы; не удавалось реализовать часто необходимую нашим пользователям функциональность — просмотр страниц входа для поисковых фраз.

По состоянию на 2013 год мы хранили в OLAPServer-е 728 миллиардов строк. Потом все данные переложили в ClickHouse и удалили.

ClickHouse


Используя OLAPServer, мы успели понять, насколько хорошо столбцовые СУБД справляются с задачей ad-hoc аналитики по неагрегированным данным. Если любой отчёт можно получить по неагрегированным данным, то возникает вопрос, нужно ли вообще предагрегировать данные заранее, как мы это делаем, используя Metrage?

С одной стороны, предагрегация данных позволяет уменьшить объём данных, используемых непосредственно в момент загрузки страницы с отчётом. С другой стороны, агрегированные данные являются очень ограниченным решением. Причины следующие:

  • вы должны заранее знать перечень отчётов, необходимых пользователю;
  • то есть, пользователь не может построить произвольный отчёт;
  • при агрегации по большому количеству ключей объём данных не уменьшается и агрегация бесполезна;
  • при большом количестве отчётов получается слишком много вариантов агрегации (комбинаторный взрыв);
  • при агрегации по ключам высокой кардинальности (например, URL) объём данных уменьшается не сильно (менее чем в 2 раза);
  • из-за этого объём данных при агрегации может не уменьшиться, а вырасти;
    пользователи будут смотреть не все отчёты, которые мы для них посчитаем. — то есть, большая часть вычислений бесполезна;
  • сложно поддерживать логическую целостность при хранении большого количества разных агрегаций.

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

Так, если мы агрегируем данные заранее, то делаем это хоть и постоянно (в реальном времени), но зато асинхронно по отношению к пользовательским запросам. Мы должны всего лишь успевать агрегировать данные в реальном времени — на момент получения отчёта используются уже по большей части подготовленные данные.

Если не агрегировать данные заранее, то всю работу нужно делать в момент запроса пользователя — пока он ждёт загрузки страницы с отчётом. Это значит, что во время запроса может потребоваться обработать многие миллиарды строк и чем быстрее, тем лучше.

Для этого нужна хорошая столбцовая СУБД. На рынке не существует ни одной столбцовой СУБД, которая могла бы достаточно хорошо работать на задачах интернет-аналитики масштаба Рунета и при этом имела бы не запретительно высокую стоимость лицензий. Если бы мы использовали некоторые из решений, перечисленных в предыдущем разделе, то стоимость лицензий многократно превысила бы стоимость всех наших серверов и сотрудников.

В последнее время в качестве альтернативы коммерческим столбцовым СУБД стали появляться решения для эффективной ad-hoc аналитики по данным, находящимся в системах распределённых вычислений: Cloudera Impala, Spark SQL, Presto, Apache Drill. Хотя такие системы могут эффективно работать на запросах для внутренних аналитических задач, достаточно трудно представить их в качестве бэкенда для веб-интерфейса аналитической системы, доступной внешним пользователям.

В Яндексе разработана своя столбцовая СУБД — ClickHouse. Рассмотрим основные требования, которые у нас к ней были до того, как приступить к разработке.

Умение работать с большими данными. В новой Яндекс.Метрике ClickHouse используется для хранения всех данных для отчётов. Объём базы данных на декабрь 2015 составлял 11,4 триллионов строк (и это только для большой Метрики). Строчки — неагрегированные данные, которые используются для получения отчётов в реальном времени. Каждая строчка в наиболее крупных таблицах содержит более 200 столбцов.

Система должна линейно масштабироваться. ClickHouse позволяет увеличивать размер кластера путём добавления новых серверов по мере необходимости. Например, основной кластер Яндекс.Метрики был увеличен с 60 до 394 серверов в течение двух лет. Для отказоустойчивости, серверы располагаются в разных дата-центрах. ClickHouse может использовать все возможности железа для обработки одного запроса. Так достигается скорость более 1 терабайта в секунду (данных после разжатия, только используемые столбцы).

Высокая эффективность работы. Высокая производительность базы является нашим отдельным предметом гордости. По результатам внутренних тестов, ClickHouse обрабатывает запросы быстрее, чем любая другая система, которую мы могли достать. Например, ClickHouse в среднем в 2,8-3,4 раза быстрее, чем Vertica. В ClickHouse нет одной серебряной пули, за счёт которой система работает так быстро.

Функциональность должна быть достаточной для инструментов веб-аналитики. База поддерживает диалект языка SQL, подзапросы и JOIN-ы (локальные и распределённые). Присутствуют многочисленные расширения SQL: функции для веб-аналитики, массивы и вложенные структуры данных, функции высшего порядка, агрегатные функции для приближённых вычислений с помощью sketching и т. п. При работе с ClickHouse вы получаете удобство реляционной СУБД.

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

ClickHouse хорошо подходит для создания всевозможных аналитических инструментов. Действительно, если система успешно справляется с задачами большой Яндекс.Метрики, то можно быть уверенным, что с другими задачами ClickHouse справится с многократным запасом по производительности.

В этом смысле особенно повезло Appmetrica — когда она находилась в разработке, ClickHouse уже был готов. Для обработки данных аналитики приложений мы просто сделали одну программу, которая берёт входящие данные и после небольшой обработки записывает их в ClickHouse. Любая функциональность, доступная в интерфейсе Appmetrica, представляет собой просто запрос SELECT.

ClickHouse используется для хранения и анализа логов различных сервисов в Яндексе. Типичным решением было бы использовать Logstash и ElasticSearch, но оно не работает на более-менее приличном потоке данных.

ClickHouse подходит в качестве базы данных для временных рядов — так, в Яндексе она используется в качестве бэкенда для Graphite вместо Ceres/Whisper. Это позволяет работать более чем с триллионом метрик на одном сервере.

ClickHouse используют аналитики для внутренних задач. По опыту использования внутри компании, эффективность работы ClickHouse по сравнению с традиционными методами обработки данных (скрипты на MR) выше примерно на три порядка. Это нельзя рассматривать как просто количественное отличие. Дело в том, что имея такую высокую скорость расчёта, можно позволить себе принципиально другие методы решения задач.

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

Это возможно лишь в том случае, если скорость анализа данных позволяет проводить исследования в интерактивном режиме. Чем быстрее выполняются запросы, тем больше гипотез можно проверить. При работе с ClickHouse возникает такое ощущение, как будто у вас увеличилась скорость мышления.

В традиционных системах данные, образно выражаясь, лежат мёртвым грузом на дне болота. С ними можно сделать что угодно, но это займёт много времени и будет очень неудобно. А если ваши данные лежат в ClickHouse, то это «живые» данные: вы можете изучать их в любых срезах и «сверлить» до каждой отдельной строчки.

Выводы


Так уж получилось, что Яндекс.Метрика является второй по величине системой веб-аналитики в мире. Объём поступающих в Метрику данных вырос с 200 млн событий в сутки в начале 2009 года до чуть более 20 млрд в 2015 году. Чтобы дать пользователям достаточно богатые возможности, но при этом не перестать работать под возрастающей нагрузкой, нам приходилось постоянно менять подход к организации хранения данных.

Для нас очень важна эффективность использования железа. По нашему опыту, при большом объёме данных стоит беспокоиться не о том, насколько система хорошо масштабируется, а о том, насколько эффективно используется каждая единица ресурсов: каждое процессорное ядро, диск и SSD, оперативка, сеть. Ведь если ваша система уже использует сотни серверов, а вам нужно работать в десять раз эффективнее, то вряд ли вы сможете легко установить тысячи серверов, как бы хорошо система не масштабировалась.

Для достижения максимальной эффективности важна специализация под конкретный класс задач. Не существует структуры данных, которая хорошо справляется с совершенно разными сценариями работы. Например, очевидно, что key-value база не подойдёт для аналитических запросов. Чем больше нагрузка на систему, тем большая специализация будет требоваться, и не стоит бояться использовать для разных задач принципиально разные структуры данных.

Нам удалось сделать так, что Яндекс.Метрика является относительно дешёвой по железу. Это позволяет предоставлять бесплатный сервис даже для самых крупных сайтов и мобильных приложений. На этом поле у Яндекс.Метрики нет конкурентов. Для примера, если у вас есть популярное мобильное приложение, то вы можете бесплатно использовать Яндекс.Метрику для приложений, даже если ваше приложение популярнее, чем Яндекс.Карты.
Автор: @o6CuFl2Q
Яндекс
рейтинг 633,28

Комментарии (20)

  • +3
    Было бы интересно прочитать побольше о архитектуре ClickHouse, а также за счет чего и на каких тестах она работает в 2,8-3,4 раза быстрее HP Vertica
    • +4
      Если смотреть сверху и без рассмотрения деталей, то архитектура ClickHouse не сильно отличается от архитектуры других MPP column-oriented СУБД. Например, можно прочитать про архитектуру Vertica здесь: vldb.org/pvldb/vol5/p1790_andrewlamb_vldb2012
      .pdf

      Если рассматривать детали, то это долго.
      На всякий случай расскажу, какие имеются ввиду бенчмарки, и что значит, что ClickHouse в 2,8-3,4 раза быстрее.

      В качестве тестовых данных, выбрали 1 млрд. строк — хитов из Метрики. Также есть урезанные dataset-ы на 100 млн. и 10 млн.
      Объём данных ограничен необходимостью уменьшить время запуска тестов.

      Составлено 43 SELECT запроса. Каждый запрос выполняется по отдельности, одновременная работа многих запросов не тестируется.
      Из них 7 запросов используют первичный ключ, а остальные — full scan.

      Запросы подобраны с учётом наших задач. Максимальное внимание уделено скорости фильтрации и агрегации.
      Много запросов проверяют всевозможные сочетания типов столбцов при GROUP BY, разные кардинальности множества после GROUP BY, разную селективность условий в WHERE и т. п.

      JOIN-ам, напротив, не уделено внимания — в тестах их нет вообще. В этом смысле, эти бенчмарки отличаются от бенчмарков TPC, где важным является выбранный порядок выполнения JOIN-ов. Конечно, ClickHouse поддерживает JOIN и делает это неплохо.

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

      Мы составили этот бенчмарк осенью 2013 года. Затем несколько раз обновляли результаты, последний раз в 2015.
      Изначально в бенчмарк входили ClickHouse, Vertica, InfiniDB, MonetDB, Infobright, и ради прикола, MySQL и Hive.

      Коротко, результаты в 2013 были такие: ClickHouse и Vertica примерно равны, InfiniDB в ~7 раз хуже и работает только после дополнительной настройки, MonetDB некоторые запросы выполняет прилично, а на некоторых почему-то хуже в сотни раз, Infobright рассматривать не имеет смысла, так как для бенчмарков использовалась community версия с ограничением в один поток на запрос.

      В 2015 году результаты обновили, но только для ClickHouse и Verica (7.1.1). Это связано с тем, что проведение бенчмарков довольно трудоёмкое. Требуется где-то от половины недели до одной недели на каждую систему, и было бы странно тратить на это месяцы рабочего времени. Впрочем, половина систем из 2013 года уже выпадает из рассмотрения (InfiniDB разорились, а MonetDB слишком отстаёт от Actian Vector).

      Для настройки Vertica мы привлекли одного специалиста, который имел с ней дело. На результаты это повлияло не сильно, так как Vertica хорошо работает по-умолчанию. Проекции в Vertica не использовались, так как важно избежать дублирования данных. Отдельные алгоритмы сжатия для каждого столбца подбирались, но не сильно повлияли на результаты.

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

      Каждый запрос запускался как «на холодную» (со сброшенным page cache), так и с данными в кэше.

      Для запросов, использующих первичный ключ (читающих дипазон данных), Vertica существенно медленнее — где-то в 8 раз, как при работе с холоными данными, так и тогда, когда диск не используется. Я не могу точно сказать, с чем это связано. Может быть, на это влияют настройки, до которых мы не дошли. Если исключить эти запросы из рассмотрения, то Vertica всё равно существенно медленнее.

      Для запросов, использующих full scan, важна скорость чтения данных (алгоритм сжатия, реализация чтения — насколько сложно десериализовать данные, нет ли лишних копирований; какие столбцы читаются в первую очередь, есть ли «неявные» индексные структуры для data skipping; локальность данных одного столбца), скорость выполнения выражений и фильтрации (как диспетчеризуются операции, есть ли векторный движок, есть ли кодогенерация), а также, для большинства запросов, скорость выполнения GROUP BY (какая структура данных используется, насколько хорошо она написана, насколько детально рассматриваются различные случаи, как распараллеливается агрегация, как передаются данные по сети при распределённой агрегации, как написан внутренний цикл, как вызываются операции с агрегатными функциями и т. п.)

      А вот хорошая ссылка про столбцовые базы данных — там рассматриваются многие детали:
      www.cs.yale.edu/homes/dna/talks/Column_Store_Tutorial_VLDB09.pdf

      PS. Так как производительность является многогранной величиной, почти всегда можно подобрать запросы, на которых одна система даёт результат лучше другой, и во столько раз, во сколько нужно. Мы постарались этого не делать. Хотя наши тесты нельзя назвать 100% объективными, я могу надеяться, что они по крайней мере, не являются мусором.
      • 0
        Очень интересно было бы результат бенчмарка для Spark.SQL посмотреть
        • 0
          Пока ещё нет, давно хочу сделать.
      • 0
        Спасибо за развернутый ответ.
        Я знаком с архитектурами современных MPP решений. Поэтому и интересно узнать вашу архитектуру, т.к. если ваше собственное решение, написанное за 2 года, обгоняет коммерческий продукт c 10-летней историей, спроектированный небезызвестным Стоунбрейкером, у вас однозначно должны быть какие-то ноу-хау в плане компрессии, обработки сжатых данных, индексов/bloom filters и т.д.
        • 0
          К сожалению, время разработки больше двух лет (хотя с 2012 оно совмещено с использованием в продакшене на части задач).
          Какое-то количество интересных решений имеется. Да, надо будет написать.
  • +1
    В opensource ждать?
    А по какому протоколу идет общение с базой? Сами писали? Или вязли Mysql, Postgres, etc?
    • 0
      Opensource сейчас рассматривается как одно из направлений развития. Но я не могу давать лишние надежды — может быть, ничего не будет.
      На самом деле, у нас есть серьёзные аргументы в пользу выпуска в opensource, которые пока не удалось ничем перекрыть.

      Для общения с базой есть простой HTTP интерфейс. Есть родной протокол для межсерверного взаимодействия, который также используется в клиенте командной строки — он даёт чуть больше, например, показывает прогресс выполнения запроса. Этот протокол ни с чем не совместим.
      Также имеется proof-of-concept ODBC драйвер, который находится в процессе разработки.
      • 0
        Если решитесь выкладывать в opensource, а я очень надеюсь :) Подумайте пожалуйста в сторону использования протокола для драйверов уже готовых MySql (как сделали Memsql) или postgres — это позволит перевести текущие ПО быстрее.
        • 0
          Хорошо. Но стоит иметь ввиду проблему — при таком подходе, программа может думать, что на той стороне настоящий MySQL или Postgres и задавать соответствующие запросы (например, select @@version_comment limit 1). А полную совместимость всё-таки сложно сделать.
          • 0
            По опыту, это все таки проще и меньше написать patch чем совсем уже писать новый механизм взаимодействия.

            А ODBC да очень нужен тоже, всякие там BI: Tableau без них никуда :)
      • 0
        ClickHouse используется для хранения и анализа логов различных сервисов в Яндексе. Типичным решением было бы использовать Logstash и ElasticSearch, но оно не работает на более-менее приличном потоке данных.


        Ну про вставку данных могу поверить, а вот в то, что ClickHouse full text search делает лучше уже сомнительно.
        Расскажите подробнее.
        • 0
          Он не делает full text search лучше, так как в нём нет соответствующих структур.
          Да, удобнее записывать приличный объём логов для последующего анализа. Логи перед записью структурируются скриптом.

          Анализ следующий (примеры):
          — топ IP-адресов, с которых прилетают 503 за последние 1000 сек;
          — показать урлы без параметров для заданного хоста с кодом товета 503 за последние 600 секунд, сортированные по повторяемости;
          — считать по логам квантили и писать их в Графит (который тоже на ClickHouse);
          — найти конкретные медленные запросы и посмотреть на них;

          Возможно, тут имеется ввиду несколько другая ниша.
          • 0
            Ваши примеры работают на таблице предположим из двух из трех столбцов: hostid, timestamp, log_message?
            Или перед тем как положить в базу сообщение парсится и кладется в базу уже по многим столбцам?

            Если первый вариант, то очень даже хорошо.
            • +1
              Сообщения, как правило, разбиваются на много столбцов. Но не всегда — иногда пользователям лениво делать это достаточно детально. Большой стобец типа message обычно остаётся, и становится важно делать brute-force поиск подстроки в строке или регексп.

              Оба этих случая достаточно хорошо оптимизированы. Например, поиск подстроки в строке, при условии, что сжатые данные помещаются в page cache, на одном сервере осуществляется со скоростью более 10 GB/sec.
    • +2
      В open-source выложили сегодня: https://habrahabr.ru/company/yandex/blog/303282/.
  • 0
    Что можете плохого сказать про Hadoop в контексте сравнения с ClickHouse?
    • 0
      Hadoop гораздо лучше подходит для offline-вычислений, когда нужно много ворочать данными. В Hadoop больше инструментов для всесторонней обработки данных. А ClickHouse лучше подходит для онлайн запросов — по хорошо структурированным данным, достаточно быстрых и более-менее простых. При этом, ниша ClickHouse со временем сокращается, так как для Hadoop тоже есть и появляются новые средства, подходящие для онлайн запросов (при некоторых условиях).

      Но для задачи — сделать аналитический инструмент для массовой аудитории, а не для внутренних пользователей, Hadoop использовать сложнее. Ведь придётся решить несколько побочных задач:
      — как реплицировать данные между ДЦ;
      — как обеспечить скорость выборки данных по первичному ключу при условии постоянного обновления данных.

      Если не нужен массовый сервис, то надо пробовать PrestoDB, Drill и другие. Я сам хочу уделить этому больше внимания.
  • 0
    Спасибо за интересный и подробный материал. Понятно, почему вы не использовали Google BigQuery. Но пробовали ли сравнить скорость выполнения одинаковых запросов к одинаковым данным в ClickHouse и Google BigQuery? Если да, какие результаты?
    • 0
      Нет, не пробовали. В качестве тестовых данных мы используем такие данные, которые нельзя загрузить в чужое облако.
      Если сделаем подходящий набор тестовых данных, то надо будет попробовать. Ещё хотелось бы сравнить с Amazon Redshift.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка