Как стать автором
Обновить

Хранения данных алгоритмом «Хранилище, структурированное журналом»

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

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

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



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



Исходная запись с индексом (A) все еще находится в файле, но он больше не используется: она была заменена новой записью A', которая относится к оригинальной копии Foo, а также к новой записи Bar. Когда хоти прочитать из нашей файловой системы, мы находим индекс корневого узла, и использует его как было бы в любой другой системе.

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

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



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

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

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

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



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

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

Преимущества этого подхода для базы данных на этом не заканчиваются. В целях обеспечения согласованности транзакций, базы данных обычно используют «Write Ahead Log», или WAL. Когда база данных сохраняется на диск, он сначала записывает все изменения в WAL, после на диск, а затем обновляет существующие файлы базы данных. Это позволяет восстановить после аварии изменения, записанные в WAL. Если мы используем журнала структурированного хранилища, WAL базы данных, так что нам остается только записать данные один раз. При восстановлении просто открываем базу данных, начиная с последнего записанного индекса, и производим поиск любых отсутствующих индексов.

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

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

Когда дело доходит до записи данных, мы можем использовать Оптимистический параллелизм. В типичных циклах чтение-модификация-запись, мы сначала выполняем наши операции чтения, как описано выше. Тогда, чтобы записать наши изменения, мы блокируем записи для базы данных и убеждаемся, что ни один из данных, которые мы читаем в первой фазе. Мы можем сделать это быстро, глядя на индекс, если адрес данных такой же, как когда мы в последний раз читали. Если оно не записывается мы можем приступить к изменению. Если все иначе, мы просто возвращаемся и начинаем снова читать.
Теги:алгоритмбазы данныхфайловая система
Хабы: Алгоритмы
Всего голосов 21: ↑19 и ↓2+17
Просмотры3.6K

Похожие публикации

Лучшие публикации за сутки