Comments 25
<>
«B» в названии B-tree означает Block
What, if anything, the B stands for has never been established.
You just have no idea what a lunchtime conversation can turn into. So there we were, [indistinct] and I, at lunch, we had to give the thing a name. And we were, so, B, we were thinking… B is, you know… We were working for Boeing at the time, we couldn't use the name without talking to the lawyers. So, there is a B. It has to do with balance, another B. Bayer was the senior author, who did have several years older than I am and had many more publications than I did. So there is another B. And so, at the lunch table we never did resolve whether there was one of those that made more sense than the rest. What really lies to say is: the more you think about what the B in B-trees means, the better you understand B-trees.
Занятно, www.mccreight.com/people/ed_mcc/index.htm здесь он пишет об этом же. B = block я встречал в литературе, теперь буду вспоминать где именно.
А чтение по неуникальным вторичным ключам ожидаемо работает, или сильно кладет систему?
Т е селекты по диапазону дат, или сообщений по номеру телефона и т д?
Т е селекты по диапазону дат, или сообщений по номеру телефона и т д?
Спасибо за статью, было интересно почитать )
Заголовок не соответствует содержанию
Это название доклада на хайлоад — www.youtube.com/watch?v=u2pju_Hb9Wc
Спасибо за интересную статью. Обращу внимание на ряд моментов касательно сравнения LSM vs BTree:
1) MongoDB использует BTree [1]. «In our testing there are a very limited number of scenarios where MongoDB provides better characteristics when using LSM than the WiredTiger btree implementation»
2) Проблема write amplification в BTree при переходе к LSM превращается в проблему баланса между size amplification и write amplification в зависимости от стратегии. Очень опасно утверждать, что какой-либо из подходов в плане баланса требований к чтениям, записям и capacity является лучше другого в большинстве сценариев
3) Вопрос многоверсионности достаточно слабо связан c форматом хранения, и едва ли может рассматриваться преимуществом LSM
4) Вопрос сжатия раскрыт поверхностно. Упоминается старый table compression MySQL, и PostgreSQL, который просто пошел по пути наименьшего сопротивления. Не упоминается index prefix compression, который есть почти у всех вендоров, и отлично сжимает secondary indexes. Не упоминаются продвинутые техники сжатия data pages, которые есть в MS SQL и Oracle, которые хоть и не даются бесплатно, но все же очень далеки от rocket science.
[1] jira.mongodb.org/browse/SERVER-18396
1) MongoDB использует BTree [1]. «In our testing there are a very limited number of scenarios where MongoDB provides better characteristics when using LSM than the WiredTiger btree implementation»
2) Проблема write amplification в BTree при переходе к LSM превращается в проблему баланса между size amplification и write amplification в зависимости от стратегии. Очень опасно утверждать, что какой-либо из подходов в плане баланса требований к чтениям, записям и capacity является лучше другого в большинстве сценариев
3) Вопрос многоверсионности достаточно слабо связан c форматом хранения, и едва ли может рассматриваться преимуществом LSM
4) Вопрос сжатия раскрыт поверхностно. Упоминается старый table compression MySQL, и PostgreSQL, который просто пошел по пути наименьшего сопротивления. Не упоминается index prefix compression, который есть почти у всех вендоров, и отлично сжимает secondary indexes. Не упоминаются продвинутые техники сжатия data pages, которые есть в MS SQL и Oracle, которые хоть и не даются бесплатно, но все же очень далеки от rocket science.
[1] jira.mongodb.org/browse/SERVER-18396
Спасибо за комментарий. По поводу вывода сделанного в №3: он безапеляционный почему-то, наверное поэтому неправильный ). Нет, конечно же проблема многоверсионности не решается отдельно от формата хранения, как и проблема бэкапа, и LSM предлагают очень элегантное решение для обеих проблем. Префиксная компрессия, да, есть у многих вендоров, нет, «отлично сжимает secondary indexes» — поверхностное утверждение, зависит от index fanout, а главное, что префиксная компрессия усложняет код (удачи в реализации итератора в обратном порядке) при этом с точки зрения сжатия не лучше обычной компрессии при достаточно больших страницах. В общем, мне кажется, Вам стоит покопать дальше, а именно в сторону эксплуатации, чтобы разобраться в ценностях на которые мы ориентировались. Иногда может показаться что чем больше «обвес» в виде разных видов компрессии, кэширования и т.д. тем лучше. Нет, это количественный подход к решению, не качественный. Качественные решения, это например архитектура вторичных ключей и range tuple cache в Vinyl. Это ранжирование, которое позволяет адаптировать compaction для разных нагрузок (в rocksdb для этого в какой-то момент говорили о page stitching, реализовали ли его или нет я не знаю). Наконец, это compaction scheduler, который учитывает характер нагрузки, а не только форму дерева. В общем, одним из посылов статьи было то, что LSM — greenfield в области оптимизации, и обвешивать его btreeшными оптимизациями неправильно.
Я посмотрел недавно выложенное видео с конференции (https://youtu.be/QrNTmBdQMrU) и ещё раз перечитал эту статью. Многое стало понятнее :) Чего лично мне не хватает — реальных примеров использования Винила. Не абстрактных описаний, когда он может быть полезен, а конкретных историй (что именно храним, какой размер записи, как часто читаем и обновляем). Буду рад, если укажете, где такое почитать или посмотреть.
PS Сам я не использую сейчас Тарантул, но в свое время был весьма вдохновлён концепцией неблокирующей однопоточной обработки данных, и рассматриваю его как вариант для будущих проектов.
Привет, очень крутая работа.
Например в cassandra есть только upsert и беда с secondary indexes (понятно почему), а вы умудрились поддержать реляционную модель и range queries!
Вопросов несколько.
1. А вы не думали сделать несколько стратегий compaction для разных кейсов в виде опций? Допустим timeseries и level size based? И может быть скруть за ними некоторые пресеты опций?
2. Как происходит разрешение конфликтов (insert, delete, insert)? Last write win или что-то поумнее?
3. Какая структура используется под tuple cache? Данные уже готовые к отправке по сети, но занимают больше места или сжаты, но размер кеша больше? И в какой момент они попадают в кеш (обновление тоже пачкой?).
4. Partitioning. Идея, которая реализована в vshards, она распрастраняется и на vinyl? Можно чуть подробнее раскрыть тему как партиции «встречаются» с lsm.
5. Range queries. Я правильно понимаю, что worst case, это когда в range ключи из разных партиций и надо сделать поиск еще и на разных машиных, а потом смержить результаты?
6. Secondary indexes. Вставка тапла и обновление вторичного индекса по прежнему атомарны и консистетны, а не как кое-где eventually consistant?
Например в cassandra есть только upsert и беда с secondary indexes (понятно почему), а вы умудрились поддержать реляционную модель и range queries!
Вопросов несколько.
1. А вы не думали сделать несколько стратегий compaction для разных кейсов в виде опций? Допустим timeseries и level size based? И может быть скруть за ними некоторые пресеты опций?
2. Как происходит разрешение конфликтов (insert, delete, insert)? Last write win или что-то поумнее?
3. Какая структура используется под tuple cache? Данные уже готовые к отправке по сети, но занимают больше места или сжаты, но размер кеша больше? И в какой момент они попадают в кеш (обновление тоже пачкой?).
4. Partitioning. Идея, которая реализована в vshards, она распрастраняется и на vinyl? Можно чуть подробнее раскрыть тему как партиции «встречаются» с lsm.
5. Range queries. Я правильно понимаю, что worst case, это когда в range ключи из разных партиций и надо сделать поиск еще и на разных машиных, а потом смержить результаты?
6. Secondary indexes. Вставка тапла и обновление вторичного индекса по прежнему атомарны и консистетны, а не как кое-где eventually consistant?
1) В первом вопросе два вопроса. Первый — про time series support. Для нормальной поддержки time series нужно решить два принципиальных вопроса:
— сжатие временных рядов. Мы используем алгоритм компрессии общего назначения, zstd, но для временных рядов могут использоваться специализированные (дифференциальные) алгоритмы сжатия. Мы не проверяли относительную эффективность специализированных алгоритмов и zstd, пока до этого не дошли руки, возможно там существует принципиальный выигрыш в степени сжатия.
— учёт того что данные во временных рядах не пересекаются по диапазону во время compaction. Этот учёт у нас реализован за счёт функционала Ranges, т.к. каждый range — это отдельное lsm дерево, мы автоматически исключим из compaction старые диапазоны time series. Там ещё возможен тюнинг и дальнейшее снижение compaction overhead — думаю ещё можно выиграть до 50% write bandwidth специализированными алгоритмами, но принципиально этот вопрос учтён.
Резюмируя, таким образом, пригодность винила для time series: эффективность ниже чем у полностью специализированного time series storage engine, по моим оценкам в 1.5-2 раза, тем не менее достаточно высокая в сравнении с lsm общего назначения или тем более btree. Сравнение и бенчмаркинг мы ещё не проводили, поэтому подтвердить свои слова цифрами пока не могу, это оценки на основе понимания внутреннего устройства некоторых time series движков.
— сжатие временных рядов. Мы используем алгоритм компрессии общего назначения, zstd, но для временных рядов могут использоваться специализированные (дифференциальные) алгоритмы сжатия. Мы не проверяли относительную эффективность специализированных алгоритмов и zstd, пока до этого не дошли руки, возможно там существует принципиальный выигрыш в степени сжатия.
— учёт того что данные во временных рядах не пересекаются по диапазону во время compaction. Этот учёт у нас реализован за счёт функционала Ranges, т.к. каждый range — это отдельное lsm дерево, мы автоматически исключим из compaction старые диапазоны time series. Там ещё возможен тюнинг и дальнейшее снижение compaction overhead — думаю ещё можно выиграть до 50% write bandwidth специализированными алгоритмами, но принципиально этот вопрос учтён.
Резюмируя, таким образом, пригодность винила для time series: эффективность ниже чем у полностью специализированного time series storage engine, по моим оценкам в 1.5-2 раза, тем не менее достаточно высокая в сравнении с lsm общего назначения или тем более btree. Сравнение и бенчмаркинг мы ещё не проводили, поэтому подтвердить свои слова цифрами пока не могу, это оценки на основе понимания внутреннего устройства некоторых time series движков.
Второй вопрос состоит в том, задумывались ли мы над различными стратегиями compaction и различными ручками тюнинга. Есть понимание, что различные стратегии сompaction — cassandra-specific костыль родившийся из-за непонимания на этапе реализации LSM в cassandra «общего» случая оценки эффективности LSM деревя для любого workload'а. В настоящее время уже выведено достаточно теории которые позвоялют автоматически выбрать оптимальную стратегию в зависимости от workload'а. Мы тажке решили развиваться по пути автоматического тюнинга compaction strategy. Фактически у нас микс leveled и tiered, на последнем уровне у нас всегда только один run file, за счёт этого достигается минимальный space amplification, за счёт не очень больших дополнительных затрат по write amplification. Также недавно мы добавили compaction randomization — это стратегия, с помощью которой мы снижаем «волновой», «шквальный» эффект который compaction имеет на write bandwidth. У нас реализован write throttling — это автоматическое квотирования новых записей в зависимости от write bandwidth. В общем, мы прикладываем максимум усилий для того чтобы тюнинга много не требовалось.
2) Про разрешение конфликтов. У нас стандартный optimistic transaction scheduler. Это означает, что одновременно с одними и теми же данными могут работать много транзакций. Для «открытых» транзакций в виниле, изменяющих один и тот же ключ, побеждает транзакция первой пришедшая к финишу. Конфликтная транзакция абортится. После коммита мы сохраняем в каждой операции в LSM дереве id транзакции, которая внесла данное изменение. Это позволяет реализовать поддержку consistent snapshot для чтения, и чтения в виниле (Read-only transactions) не блокируют писателей и не оставляют блокировок.
3) Tuple cache. Структура данных — модифицированное дерево отрезков. В tuple cache хранятся уже несжатые данные, но не блоками, а индивидуальными объектами. Если range read читает несколько таплов, они соединяются в цепочку и образуют отрезок. Таким образом, данные уже готовы к отправке по сети. В кэш данные попадают только при чтении. При этом, если читается несуществующее значение, то оно также укладывается в кэш, т.к. чтение несуществующих значений из lsm очень дорогая операция.
При обновлении значения, которое присутствует в кэше, значение из кэша удаляется. Хранить его более не имеет смысла т.к. новое значение присутствует в level0 lsm дерева, Который и так в памяти.
При обновлении значения, которое присутствует в кэше, значение из кэша удаляется. Хранить его более не имеет смысла т.к. новое значение присутствует в level0 lsm дерева, Который и так в памяти.
4) Шардинг, конечно, работает с винилом точно так же как он работает с memtx, т.к. шардинг и как реализация и как концепция находится «поверх» storage engine. Да, выходит так что у нас три уровня шардинга: между несколькими машинами, между несколькими инстансами на одной машине, и между разными range одного space'а. Это всё работает незаметно для пользователя.
5) Обычно sharding мы также делаем range-based, поэтому такой ситуации не возникает, хотя теоретически она возможно если Shard-key — hash-based.
6) Не просто консистентны, транзакционны. Не надо забывать что вторичные индексы в первую очередь хранятся в оперативной памяти. Это просто ещё одно lsm-дерево со своим level0, так что это не сверхзадача — сделать обновление нескольких индексов в памяти по принципу «всё или ничего». Но технически это устроено не так. Фактически при вставке данных в vinyl вставка осуществляется не в lsm, а в transaction-local дерево. То есть в tarantool lsm-дерево никогда не содержит грязных данных. Перемещение из transaction-local памяти в lsm осуществляется при commit'е. Этот подход мы унаследовали от sophia engine, и это, по моим оценкам, было наиболее значимой инновацией в sophia по сравнению с классической архитектурой управления транзакциями. Хотя транзакционный менеджер sophia мы конечно переписали, в нём не было поддержки gap locks.
Sign up to leave a comment.
Хранение данных на Виниле