Алгоритмы, лежащие в основе современных систем хранения

• Оригинальный адрес:Algorithms Behind Modern Storage Systems
• Оригинальный автор:Alex Petrov
• Перевод с:Программа перевода самородков
• Постоянная ссылка на эту статью:GitHub.com/rare earth/gold-no…
• Переводчик:LeopPro
• Корректор:zephyrJS FesonX

Различное использование B-деревьев, оптимизированных для чтения, и LSM-деревьев, оптимизированных для записи.

Автор: Алексей Петров

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

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

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

В этой статье подробно обсуждаются две конструкции систем хранения, используемые в большинстве современных баз данных — оптимизированная для чтенияB-Tree ^[1]и написать оптимизациюLSM(log-structured merge)-Tree ^[5]- и опишите их варианты использования и компромиссы.

B-Tree

B-дерево — это популярная индексная структура данных, оптимизированная для чтения, которая представляет собой обобщение двоичных деревьев. Он имеет множество вариантов и используется в различных базах данных (включаяMySQL InnoDB ^[4],PostgreSQL ^[7])четноеФайловая система(ВФС+^[8], HTrees ext4^[9]). в B-деревеBавтор, представляющий исходную структуру данныхBayer, или компания, в которой он работал в то времяBoeing.

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

Один из способов сбалансировать бинарное дерево — это то, что называется вращением: переставить узлы, подтолкнув родителя более глубокого поддерева ниже его дочернего элемента и подтянув этот дочерний элемент вверх, поместив его на место исходного родителя. На рис. 1 показан пример поворота в сбалансированном бинарном дереве. После добавления узла 2 слева бинарное дерево становится несбалансированным. Чтобы сбалансировать дерево, поверните его вокруг узла 3 (дерево вращается вокруг него). Затем узел 5 (который был корневым узлом и родителем узла 3 до поворота) становится его дочерним. После завершения вращения глубина левого поддерева уменьшается на 1, а глубина правого поддерева увеличивается на 1. Максимальная глубина дерева была уменьшена.

Двоичное дерево является наиболее полезной структурой данных в памяти. Однако из-за баланса (минимальная глубина всех поддеревьев) и низкой степени выхода (максимум два потомка на узел) они не акклиматизируются на диске. B-деревья позволяют каждому узлу хранить более двух указателей и работать с блочными устройствами, сопоставляя размер узла с размером страницы (например, 4 КБ). В некоторых современных реализациях будут использоваться узлы большего размера, охватывающие несколько страниц.

B-Tree обладает следующими свойствами:

• Упорядоченный. Это позволяет выполнять последовательное сканирование и упрощает поиск.

• Самобалансирующийся. Нет необходимости балансировать дерево при вставке и удалении: когда узел B-Tree заполнен, он разделяется на две части, а когда использование соседних узлов падает ниже определенного порога, два узла объединяются. Это также означает, что каждый конечный узел находится на одинаковом расстоянии от корневого узла, и количество шагов для поиска в процессе поиска одинаково.

• Логарифмическая временная сложность поиска. Время поиска очень важно, что делает B-деревья идеальными для индексов баз данных.

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

Дерево B+, обсуждаемое в этой статье^[3]— это современный вариант B-Tree, часто используемый для хранения базы данных. B+Tree по сравнению с оригинальным B-Tree^[1]Отличие в том, что: (1) он использует дополнительно связанные листовые узлы для хранения значений; (2) значения нельзя хранить на внутренних узлах.

Анатомия B-дерева

Давайте подробнее рассмотрим структуру B-Tree, как показано на рисунке 2. Существует несколько типов узлов B-Tree: корневые узлы, внутренние узлы и конечные узлы. Корневой узел (верхний) — это узел, у которого нет родителей (т. е. он не является потомком какого-либо узла). Внутренние узлы (посередине) имеют родителей и детей, они соединяют корневые и конечные узлы. Листовые узлы (внизу) содержат данные и не имеют потомков. На рис. 2 показано B-дерево с коэффициентом ветвления 4 (4 указателя, 3 ключа во внутренних узлах и 4 пары ключ/значение в листьях).

Характеристики B-дерева следующие:

• коэффициент ветвления - количество указателей на дочерние узлы (N). В дополнение к указателям корневой узел и внутренние узлы также содержат ключи N-1.

• Использование — отношение количества указателей на дочерние узлы, которые в настоящее время удерживаются узлом, к максимально доступному. Например, если коэффициент ветвления дереваN, и один из узлов в настоящее время содержитN/2указатель, использование узла составляет 50%.

• Высота — порядок величины B-дерева, указывающий, сколько указателей должно быть передано во время поиска.

Каждый нелистовой узел в дереве может содержать не болееNключи (элементы указателя), которые делят дерево наN+1поддеревья, которые можно найти по соответствующим указателям. пунктK_iуказатель вiуказывает на поддерево, содержащее всеK_i-1 <= K_Цель < K_i(вKявляется индексной записью для набора ключей). Указатели головы и хвоста являются особыми, все элементы в поддереве, на которые они указывают, меньше или равны самому левому дочернему узлу.K₀или больше, чем самый правый ребенокK_N-1. Листовой узел также содержит указатели своих дочерних узлов до и после, образуя двусвязный список между дочерними узлами. Ключи во всех узлах всегда упорядочены.

найти

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

Что касается сложности, B-Tree гарантирует, что временная сложность запросаlog(n), потому что для поиска ключей в узле используется бинарный поиск, как показано на рис. 4. С точки зрения непрофессионала бинарный поиск можно объяснить как поиск слов, начинающихся с определенной буквы в словаре, и все слова в словаре отсортированы в алфавитном порядке. Сначала вы открываете страницу прямо в середине словаря. Если слово, которое вы ищете, находится в алфавитном порядке меньше (перед) текущей страницы, вы продолжаете искать левую половину словаря; в противном случае вы продолжаете искать правую половину. Вы продолжаете делить оставшийся диапазон номеров страниц пополам, выбирая одну сторону, пока не найдете нужную букву. Каждый шаг сокращает диапазон поиска вдвое, поэтому временная сложность поиска является логарифмической. Ключи в узлах B-дерева упорядочиваются и сопоставляются с использованием алгоритма бинарного поиска, поэтому сложность поиска B-дерева является логарифмической. Это также иллюстрирует важность поддержания высокого уровня использования и единообразного доступа к дереву.

вставить, обновить, удалить

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

LSM-Tree

Структурированное дерево слияния журналов — это неизменяемая дисковая структура данных, оптимизированная для записи. Он подходит для сценариев, в которых записи выполняются чаще, чем операции запросов. LSM-дерево привлекло больше внимания, потому что оно позволяет избежать случайных вставок, обновлений и удалений.

Анатомия LSM-дерева

Чтобы разрешить последовательную запись, LSM-Tree выполняет пакетную запись и обновление таблицы в памяти (обычно с использованием структуры данных, которая поддерживает логарифмическую временную сложность для поиска, например, двоичные деревья поиска или таблицы пропуска), когда ее размер Записывается на диск, когда порог достигнут (эта операция называется промывкой). Извлечение данных требует поиска во всех частях дерева на диске, изучения таблиц в памяти, объединения их содержимого и возврата результатов. На рис. 5 показана структура LSM-дерева: таблица для записи в памяти. Как только том memtable достигает определенного уровня, memtable записывается на диск. При чтении считываются таблицы диска и памяти, консолидируя данные посредством операции слияния.

упорядоченный серийный список

Из-за простоты SSTables (упорядоченные последовательные таблицы) (легко писать, искать и читать) и производительности слияния (во время слияния исходная SSTable сканируется, а результат слияния записывается последовательно), большинство современных реализаций LSM-Tree (НапримерRocksDBиApache Cassandra) все используют SSTable в качестве таблицы жесткого диска.

SSTable — это упорядоченная неизменяемая структура данных на жестком диске. Структурно SSTable можно разделить на две части: блок данных и блок индексов, как показано на рисунке 6. Блок данных содержит уникальные пары ключ-значение, записанные в ключевом порядке. Блок индекса содержит ключи, которые сопоставляются с указателями блоков данных, указывающими на местоположение фактической записи. Для быстрого поиска индексы обычно реализуются с использованием оптимизированных структур, таких как B-деревья или хэш-таблицы для точечных запросов. Каждое значение в SSTable имеет соответствующую метку времени. Временные метки фиксируют время вставки, обновления (обычно неразличимого) и удаления.

SSTable имеет следующие преимущества:

• Быстрые точечные запросы (например, поиск значений по ключу) могут быть выполнены путем запроса индекса первичного ключа.

• Сканирование (например, обход заданного диапазона пар ключ-значение) может быть выполнено простым последовательным чтением пар ключ-значение в блоке данных.

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

Запрос

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

Этап слияния также необходим для обеспечения корректной работы операций удаления и обновления. В LSM-Tree путем вставки заполнителей (часто называемыхнадгробие), чтобы указать, какой ключ помечен для удаления. Аналогично, операция обновления просто фиксирует запись с более поздней отметкой времени. Во время чтения записи, помеченные для удаления, пропускаются и не возвращаются клиенту. Операция обновления аналогична: из двух записей с одинаковым ключом возвращается только запись с более поздней отметкой времени. На рис. 7 показана операция слияния для консолидации данных для одного и того же ключа, хранящихся в разных таблицах: как показано, запись Alex имеет отметку времени 100, а затем новый телефон обновляется с отметкой времени 200; записи John были удалены. Два других элемента не изменяются, поскольку они не переопределяются.

Чтобы уменьшить количество поисковых таблиц SSTable и предотвратить поиск ключа в каждой SSTable, многие системы хранения используют метод, называемыйФильтр Блума ^[10]структура данных. Это вероятностная структура данных, которую можно использовать для проверки принадлежности элемента множеству. Он потенциально может давать ложноположительные результаты (т. е. судить о том, что элемент является членом множества, но не является им), но не может давать ложноотрицательные результаты (т. е. если возвращается отрицательный результат, элемент не должен быть членом множества). из набора). Другими словами, фильтр Блума используется для определения того, находится ли ключ «вероятно в SSTable» или «определенно не в SSTable». Во время поиска SSTables, в которых фильтр Блума возвращает отрицательные результаты, будут пропущены.

Обслуживание LSM-дерева

Так как SSTableнеизменный, поэтому они записываются последовательно, и нет зарезервированного пустого места для модификации. Это означает, что операции вставки, обновления или удаления потребуют перезаписи всего файла. Все операции, которые изменяют состояние базы данных, "пакетируются" в таблицы памяти. Со временем количество дисковых таблиц будет увеличиваться (данные для одного и того же ключа в нескольких разных файлах, несколько разных версий одной и той же записи, удаление избыточных записей), а накладные расходы на операции чтения будут становиться все больше и больше.

Чтобы уменьшить нагрузку на чтение, консолидировать пространство, занимаемое удаленными записями, и уменьшить количество дисковых таблиц, LSM-Tree требуеткомпрессияоперации, считывает полный SSTable с диска и объединяет их. Поскольку SSTable сортируется по ключу, его работа по сжатию аналогична сортировке слиянием, которая является очень эффективной операцией: чтение записей из нескольких исходных упорядоченных последовательностей, и объединенный вывод немедленно добавляется к файлу результатов, а затем к файлу результатов. . Одним из преимуществ сортировки слиянием является то, что она эффективно работает даже при объединении больших файлов, которые не помещаются в памяти. Полученная таблица сохраняет порядок исходного SSTable.

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

Атомарность и долговечность

Чтобы уменьшить количество операций ввода-вывода и заставить их выполняться последовательно, как B-Tree, так и LSM-Tree выполняют пакетные операции в памяти перед фактическим обновлением. Это означает, что в случае сбоя целостность данных,атомарность(чтобы придать атомарность ряду операций, рассматривайте их как одну операцию, либо все, либо ничего),Упорство(В случае сбоя процесса или сбоя питания можно гарантировать, что данные достигнут постоянного хранилища) Не гарантируется.

Для решения этой проблемы в большинстве современных систем хранения используется WAL (Write Ahead Log). Основная идея WAL заключается в том, что все изменения состояния базы данных сначала сохраняются в журнале только для добавления на диск. Если во время работы происходит сбой процесса, журнал будет переназначен, чтобы гарантировать, что никакие данные не будут потеряны, а все изменения будут атомарными.

В B-Tree использование WAL можно понимать как запись операции записи в файл данных только после того, как она была зарегистрирована. Как правило, системы хранения B-Tree имеют относительно небольшой размер журнала: пока изменения применяются к постоянному хранилищу, они могут быть объявлены устаревшими. WAL также действует как резервная копия для операций во время выполнения: любые изменения, не примененные к страницам данных, могут быть повторены на основе записей журнала.

В LSM-Tree WAL используется для хранения изменений, которые находятся в таблицах памяти, но еще не были полностью сброшены на диск. Пока memtable сбрасывается и заменяется, операции чтения могут выполняться во вновь созданной SSTable, а часть изменений в WAL, которая была сброшена из memtable на диск, может быть отброшена.

Суммировать

Одним из самых больших различий между структурами данных B-Tree и LSM-Tree является цель их оптимизации и результаты оптимизации.

Давайте сравним функции B-Tree и LSM-Tree. В целом, B-Tree имеет следующие характеристики:

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

• Он оптимизирован для чтения, что означает, что ему не нужно читать из нескольких источников (и не нужно объединять), что упрощает путь чтения.

• Операции записи могут привести к каскадному разбиению узлов, что делает операции записи дорогостоящими.

• Он оптимизирован для среды подкачки (блочное хранилище) и исключает операции позиционирования байтов.

• Фрагментация, фрагментация, вызванная частыми обновлениями, может потребовать дополнительного обслуживания и перезаписи блоков. Однако обслуживание B-дерева обычно меньше, чем обслуживание LSM-дерева.

• Изоляция параллельного доступа для чтения и записи, включающая защелки и цепочки.

LSM-дерево обладает следующими свойствами:

• Это неизменно. После того, как SSTable будет записан на диск, он не изменится. Операции сжатия используются для консолидации посадочных мест, удаления записей и объединения данных с одним и тем же ключом в разных файлах данных. В рамках операции уплотнения после успешного слияния исходный SSTable устаревает и удаляется. Эта неизменность дает нам еще одно полезное свойство: к обновленной таблице можно обращаться одновременно.

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

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

• Требуется техническое обслуживание/сжатие, поскольку буферизованные записи сбрасываются на диск.

Оцените системы хранения

Разработка систем хранения всегда сталкивается с одними и теми же проблемами и учитывает одни и те же факторы. Решение, в каком направлении оптимизировать, может оказать большое влияние на результаты. Вы можете потратить больше времени на размещение структур во время записи для более эффективного чтения, зарезервировать место для обновлений на месте или буферизовать данные, чтобы обеспечить последовательную запись для более быстрой записи. Однако сделать все сразу невозможно. Идеальная система хранения должна иметь самую низкую стоимость чтения, самую низкую стоимость записи и не иметь дополнительных накладных расходов. Но на самом деле структуры данных могут быть обменены только между несколькими факторами. Важно понимать эти компромиссы.

Исследователи из Гарвардской лаборатории DASlab (Лаборатория систем данных) обобщили три ключевых момента в направлении оптимизации системы баз данных: накладные расходы на чтение, накладные расходы на обновление и накладные расходы памяти (или сокращенно RUM). При выборе структур данных, методов доступа и даже подходящих для определенных рабочих нагрузок следует понимать, какие параметры наиболее важны для вашего варианта использования, поскольку алгоритмы заточены под конкретные варианты использования.

РУМ-гипотеза ^[2]Верхний предел устанавливается для двух видов накладных расходов, описанных выше, а нижний предел устанавливается для третьего. Например, B-деревья оптимизированы для чтения за счет увеличения накладных расходов на запись, зарезервированного пространства (а также накладных расходов на память). LSM-Tree меняет высокие накладные расходы на чтение, связанные с необходимостью доступа к многодисковым таблицам, на низкие накладные расходы на запись. Из трех параметров конкурирующего треугольника улучшение с одной стороны может означать уступку с другой. Рисунок 9 иллюстрирует гипотезу RUM.

B-Tree оптимизирует производительность чтения: индекс расположен таким образом, что требования к доступу к диску для обхода дерева сведены к минимуму. Данные можно найти, обратившись к индексному файлу. Это достигается за счет постоянного обновления индексного файла, но это также увеличивает нагрузку на запись из-за разделения и слияния узлов, перемещений и обслуживания, связанного с фрагментацией и дисбалансом. Чтобы сгладить стоимость обновления и уменьшить количество разбиений, B-Tree резервирует дополнительное пространство на узлах на всех уровнях. Это помогает задержать рост накладных расходов на запись до насыщения узла. Короче говоря, B-Tree жертвует производительностью обновления и памяти ради лучшей производительности чтения.

LSM-Tree оптимизирует производительность записи. И обновления, и удаления требуют обнаружения данных на диске (то же самое для B-деревьев), и это гарантирует последовательную запись за счет кэширования всех вставок, обновлений и удалений в таблице в памяти. Это связано с более высокими затратами на обслуживание и требованиями к сжатию (что является единственным способом смягчить растущие накладные расходы на чтение и уменьшить количество дисковых таблиц) и более высокой стоимостью чтения (поскольку данные должны считываться из нескольких источников и объединяться) в за счет. В то же время LSM-Tree снижает нагрузку на память, не оставляя зарезервированного пространства (в отличие от узлов B-Tree, средний коэффициент использования которых составляет 70 %, включая накладные расходы, необходимые для обновлений на месте), из-за более высокого уровня использования и возможных Неизменяемость файлов, LSM-Tree поддерживает блочное сжатие. Короче говоря, LSM-Tree жертвует производительностью чтения и увеличивает стоимость обслуживания для повышения производительности записи и уменьшения объема памяти.

Существуют структуры данных, которые можно оптимизировать для каждого желаемого свойства. Более высокая производительность чтения может быть достигнута с более высокими затратами на обслуживание с использованием адаптивных структур данных. Добавьте метаданные, облегчающие обход (например,Рассредоточенная укладка) повлияет на время записи и займет больше места, но может повысить производительность чтения. Используйте сжатие для оптимизации использования памяти (например,Горилла Сжатие ^[6],дельта-кодированиеи многие другие алгоритмы) добавляет некоторые накладные расходы на сжатие данных при записи и распаковку данных при чтении. Иногда вы можете пожертвовать функциональностью ради эффективности. Например,Файлы кучи и хэш-индексыБлагодаря простоте формата файла гарантируется хорошая производительность и небольшие накладные расходы за счет отсутствия поддержки других функций, кроме точечных запросов. Вы также можете использовать приблизительные структуры данных, такие как фильтры Блума,HyperLogLog,Count-Min sketchи т. д.), чтобы пожертвовать точностью ради пространства и эффективности.

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

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

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

использованная литература

1. Comer, D. 1979. The ubiquitous B-tree. Computing Surveys 11(2); 121-137; Эта функция работает. Я упоминал. Простой. Quota/view doc/Dow….

2. Data Systems Laboratory at Harvard. The RUM Conjecture; Big Time Speaker.seas.Harvard.Amount/Getting Started-con on ECT….

3. Graefe, G. 2011. Modern B-tree techniques. Foundations and Trends in Databases 3(4): 203-402; Эта функция работает. Я упоминал. Простой. Quota/view doc/Dow….

4. MySQL 5.7 Reference Manual. The physical structure of an InnoDB index; Dev.MySQL.com/doc/Furious/….

5. O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. 1996. The log-structured merge-tree. Acta Informatica 33(4): 351-385; Эта функция работает. Я упоминал. Простой. Quota/view doc/Dow….

6. Pelkonen, T., Franklin, S., Teller, J., Cavallaro, P., Huang, Q., Meza, J., Veeraraghavan, K. 2015. Gorilla: a fast, scalable, in-memory time series database. Proceedings of the VLDB Endowment 8(12): 1816-1827; Уууу, лицо Ви полностью в .org/PV dB/Vol8/….

7. Suzuki, H. 2015-2018. The internals of PostreSQL; B.keyboard/apple/apple от woohoo.inter потерял 01. ….

8. Apple HFS Plus Volume Format; developer.apple.com/legacy/patient…

9. Mathur, A., Cao, M., Bhattacharya, S., Dilger, A., Tomas, A., Vivier, L. (2007). The new ext4 filesystem: current status and future plans. Proceedings of the Linux Symposium. Ottawa, Canada: Red Hat.

10. Bloom, B. H. (1970), Space/time trade-offs in hash coding with allowable errors,Communications of the ACM, 13 (7): 422-426

Статьи по Теме

Правило пяти минут: как Flash изменит правила игры через 20 лет
Гетц Грефе, лаборатория Hewlett-Packard
Старые правила продолжали развиваться, а flash добавил два новых.
queue.ACM.org/detail Кухонные двери?…

Disambiguating Databases
Rick Richardson
Создайте базу данных в соответствии с вашей моделью доступа.
queue.ACM.org/detail Кухонные двери?…

Ты делаешь это неправильно!
Poul-Henning Kamp
Как вы думаете, вы овладели искусством серверной производительности? Подумайте еще раз.
queue.ACM.org/detail Кухонные двери?…

Alex Petrov (coffeenco.de/, @ifesdjeen (GitHub) @ifesdjeen (Twitter)), участник Apache Cassandra и энтузиаст систем хранения. Последние несколько лет он работал над базами данных, строил распределенные системы и конвейеры обработки данных для различных компаний.

Оригинальный английский PDF-файл этой статьи:ссылка для скачивания

Copyright © 2018 held by owner/author. Publication rights licensed to ACM.

---

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из ИнтернетаНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллекти другие поля, если вы хотите видеть больше качественных переводов, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.