Voldemort (Data Store)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 22:07, 11 ноября 2017.
Project Voldemort
Voldemort logo.png
Разработчики: LinkedIn
Выпущена: 2009; 11 years ago (2009)
Состояние разработки: Активное
Написана на: Java
Операционная система: Кросс-платформенная
Локализация: Английский
Тип ПО: key-value store
Лицензия: Apache License 2
Веб-сайт www.project-voldemort.com

Voldemort — это распределенное хранилище данных, которое создается как хранилище ключей, используемое LinkedIn для хранения с высокой масштабируемостью[1]. Он назван в честь вымышленного злодея Гарри Поттера - Лорда Волдеморта.

Исследование 2012 года, сравнивающее системы хранения данных мониторинга производительности приложений, показало, что Voldemort, Cassandra и HBase в большинстве случаев предлагают линейную масштабируемость, причем минимальная латентность у Voldemort и максимальная пропускная способность у Cassandra.

Основные свойства

  • Данные автоматически реплицируются на несколько серверов[2]
  • Данные автоматически разбиваются на разделы, поэтому каждый сервер содержит только подмножество общих данных
  • Обеспечивает настраиваемую согласованность (строгий кворум или возможную согласованность)
  • Сбой сервера обрабатывается прозрачно
  • Pluggable Storage Engines - BDB-JE, MySQL, только для чтения
  • Взаимозаменяемая сериализация - протокольные буферы, блокировка, Avro и Java Serialization
  • Элементы данных версируются для максимизации целостности данных в сценариях сбоя без ущерба для доступности системы
  • Каждый узел не зависит от другого
  • Хорошая производительность одного узла: вы можете ожидать 10-20 тыс. операций в секунду в зависимости от машин, сети, дисковой системы и коэффициента репликации данных
  • Поддержка подключаемого размещения данных.

Сравнение с реляционными базами данных

Voldemort не является реляционной базой данных. Он также не вводит новую абстракцию, такую ​​как ориентация документа. Это в основном просто большая, распределенная, стойкая, отказоустойчивая хеш-таблица. Для больших приложений под давлением масштабируемости система может потенциально состоять из нескольких функционально разделенных служб или API. Для приложений в этом пространстве произвольные объединения в базе данных уже невозможны. Типичным примером является введение слоя кэширования, который в любом случае потребует семантики хеш-таблицы. Для этих приложений Voldemort предлагает ряд преимуществ:

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

Хранилище «ключ-значение»

Чтобы обеспечить высокую производительность и доступность, допускается простой доступ к данным с ключом[3]. Ключ и значение могут быть сложными составными объектами, включая списки или карты, но, тем не менее, единственные поддерживаемые запросы эффективны:

value = store.get(key)

store.put(key, value)

store.delete(key)

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

Минусы:

  • нет сложных фильтров запросов
  • все соединения должны выполняться в коде
  • никаких ограничений внешнего ключа
  • нет триггеров

Плюсы:

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

Архитектура системы

Каждый уровень в коде реализует простой интерфейс хранения, который помещает, получает и удаляет. Каждый из этих уровней отвечает за выполнение одной функции, такой как сетевая связь tcp/ip, сериализация, согласование версий, маршрутизация между узлами и т.д.

Логическая архитектура

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

Физическая архитектура

На приведенной выше диаграмме «Load Bal.» указывает аппаратный балансировщик нагрузки или балансировщик программных продуктов с круговым движением. «Partition-aware routing» (маршрутизация с поддержкой разделов) - это внутренняя маршрутизация систем хранения. Очевидно, хорошо, что меньшее количество прыжков с точки зрения латентности и с точки зрения пропускной способности (так как меньше потенциальных узких мест), но требуется, чтобы интеллект маршрутизации перемещался вверх по стеку (например, клиент должен быть java и использовал нашу библиотеку).

Доступ к дискам - это самый большой успех в хранилище, второй - сетевой перелет. Доступ к дискам можно избежать, разделив набор данных и кеширование как можно больше. Сетевые переходы требуют архитектурной гибкости для устранения. Обратите внимание, что на приведенной выше диаграмме мы можем реализовать 3-точечные, 2-точечные и 1-точечные удаленные службы с использованием различных конфигураций. Это позволяет достичь очень высокой производительности, когда можно направлять вызовы службы непосредственно на соответствующий сервер.

Разделение и репликация данных

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

Аналогично серверы регулярно терпят неудачу, становятся перегруженными или сбиты для обслуживания. Если есть S серверов, и каждый сервер, как предполагается, терпит неудачу независимо с вероятностью p в данный день, тогда вероятность потери по меньшей мере одного сервера за день будет 1-(1-p)^s. Ясно, что, учитывая этот факт, мы не можем хранить данные только на одном сервере или вероятность потери данных будет обратно пропорциональна размеру кластера. Простейшим возможным способом добиться этого было бы сократить данные на S разделов (по одному на один сервер) и хранить копии заданного ключа K на R серверах. Один из способов связать R серверов с ключом K - взять a = K mod S и сохранить значение на серверах a, a+1, ... , a+r. Таким образом, для любой вероятности p вы можете выбрать подходящий фактор репликации R для достижения приемлемо низкой вероятности потери данных.

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

Последовательное хеширование - это метод, который позволяет избежать этих проблем, и мы используем его для вычисления местоположения каждой клавиши в кластере. При сбое сервера загрузка распределяется поровну по всем оставшимся серверам в кластере. Аналогично, когда новый сервер добавляется в кластер из S серверов, только 1/(S+1) значения должны быть перенесены на новый компьютер. Чтобы визуализировать последовательный метод хэширования, мы можем представить возможные значения хеш-целых чисел как кольцо, начинающееся с 0 и кружащееся вокруг 2^31-1. Это кольцо делится на Q одинаковых размеров (Q >> S), и каждому из S серверов назначается Q / S из них. Ключ отображается на кольцо с использованием произвольной хеш-функции, а затем мы вычисляем список серверов R, ответственных за этот ключ, принимая первые R уникальных узлов при перемещении по разделам по часовой стрелке. На приведенной ниже диаграмме изображено хеш-кольцо для серверов A, B, C, D. Стрелки указывают клавиши, отображенные на хеш-кольцо и результирующий список серверов, которые будут хранить значение для этого ключа, если R = 3.

Хеш-кольцо

Формат данных и запросы

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

Запросы

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

Voldemort хоть и не поддерживает отношения «один-ко-многим», он поддерживает списки как значения, которые выполняют одно и то же, поэтому можно хранить разумное количество значений, связанных с одним ключом. Это соответствует java.util.Map, где значение представляет собой java.util.List. В большинстве случаев эта денормализация является огромным улучшением производительности, поскольку существует только один набор обращений к диску; но для очень больших отношений «один-ко-многим» (скажем, где ключ сопоставляется с десятками миллионов значений), которые должны храниться на сервере и лениво передаваться с помощью курсора, этот подход нецелесообразен. Этот (редкий) случай должен быть разбит на подзапросы или иным образом обрабатываться на уровне приложения.

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

Модель данных и сериализация

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

Следующие типы поддерживаются из коробки, введя соответствующий тип в конфигурацию хранилища:

  • json - двоичная, типизированная модель данных JSON, которая поддерживает списки, карты, даты, булевы и числа различных прецизионных решений. Это единственный тип сериализации, который имеет полное отображение из байтов ↔ объектов AND из строк ↔ объектов. Это означает, что он может взаимодействовать с подобным SQL. В текущем производственном использовании используется типизированный, компактный, подобный схеме JSON-подобный формат.
  • string - просто хранит строковые строки; полезно для XML-блоков.
  • java-serialization
  • protobuf - протокольные буферы - это формат последовательной генерации кода от Google. Это может быть предпочтительным способом, если вам не нужен доступ к командной строке.
  • thrift
  • avro-generic / avro-specific / avro-reflective - Avro - еще одна богатая система сериализации данных.
  • identity - это фактически отключает сериализацию, просто вернув вам точный байт.

Консистенция и управление версиями

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

Альтернативным решением является терпимость к возможности несогласованности и устранение несоответствий во время чтения. Это подход, который здесь используется.

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

Значение для данного ключа согласовано, если в отсутствие обновлений все чтения этого ключа возвращают одинаковое значение. В мире только для чтения данные создаются согласованным образом и не изменяются. Когда мы добавляем как записи, так и репликации, мы сталкиваемся с проблемами: теперь нам нужно обновить несколько значений на нескольких машинах и оставить вещи в согласованном состоянии. При наличии сбоев сервера это очень сложно, при наличии сетевых разделов это невозможно сделать (раздел - когда, например, A и B могут достигать друг друга, а C и D могут достигать друг друга, но A и B могут не достигают C и D).

Существует несколько способов достижения согласованности с различными гарантиями и компромиссами с производительностью:

  • Двухфазная фиксация - это протокол блокировки, который включает в себя два раунда координации между машинами. Он идеально согласуется, но не терпит к отказам и очень медленный.
  • Paxos-style consensus - это протокол для согласования значения, которое является более отказоустойчивым.
  • Read-repair - подход включает в себя запись всех несогласованных версий, а затем при чтении обнаруживается конфликт и решается проблема. Для устранения конфликтов может потребоваться дополнительная логика приложения.

В Voldemort используется управление версиями и read-repair. Им присущи лучшие гарантии доступности и максимальная эффективность.

Еще один подход к достижению согласованности - использование Hinted Handoff. В этом методе во время записи, если мы обнаруживаем, что узлы назначения опущены, мы сохраняем «подсказку» обновленного значения на одном из живых узлов. Затем, когда эти нижние узлы возвращаются, «подсказки» подталкиваются к ним, тем самым делая данные согласованными.

Управление версиями в распределенной системе

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

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

  • Два сервера одновременно получают одно и то же значение:

[client 1] get(1234) => {"name":"jay", "email":"jay.kreps@linkedin.com"}

[client 2] get(1234) => {"name":"jay", "email":"jay.kreps@linkedin.com"}

  • Клиент 1 изменяет имя и помещает put

[client 1] put(1234, {"name":"jay kreps", "email":"jay.kreps@linkedin.com"})

  • Клиент 2 изменяет электронную почту и помещает put

[client 2] put(1234, {"name":"jay", "email":"jay.kreps@yahoo.com"})

  • Теперь у нас есть следующие конфликтующие версии:

{"name":"jay", "email":"jay.kreps@linkedin.com"}

{"name":"jay kreps", "email":"jay.kreps@linkedin.com"}

{"name":"jay", "email":"jay.kreps@yahoo.com"}

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

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

Векторные часы - это список серверов: пары версий:

 [1: 45,2: 3,5: 55]

Версия указывает, что сервер был «мастером» для этого количества записей.

Версия v1 преуспевает в версии v2, если для всех i , v1[i] > v2[i] . Если ни v1 > v2, ни v1 < v2 , то v1 и v2 совпадают и находятся в конфликте. Вот простой пример двух противоречивых версий:

 [1: 2,2: 1] 
 [1: 1,2: 2]

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

Параметры маршрутизации

Любая постоянная система должна ответить на вопрос «где мои вещи?». Это очень простой вопрос, если у нас есть централизованная база данных, так как ответ всегда «где-то на сервере базы данных». В многораздельной ключевой системе есть несколько машин, которые могут иметь данные. Когда мы читаем, нам нужно прочитать, по крайней мере, один сервер, чтобы получить ответ, когда мы пишем, нам нужно (в конце концов) написать все N реплик.

Таким образом, существуют три параметра:

  • N - количество реплик
  • R - количество машин для чтения из
  • W - число записывается в блок

Заметим, что если R + W > N, то нам гарантировано «прочитать наши записи». Если W = 0, то записи не блокируются, и никаких гарантий успеха нет. Помещения и удаления не являются ни последовательными, ни изолированными. Семантика такова: если операция put/delete успешно завершается без исключения, то гарантируется, что по крайней мере W узлов выполнили операцию; однако, если запись не выполняется (скажем, потому что слишком мало узлов удается выполнить операцию), то состояние не указано. Если хотя бы один put/delete успешно завершен, тогда в конечном итоге это будет новое значение, однако если ни один не удался, значение будет потеряно. Если клиент хочет обеспечить состояние после неудачной операции записи, он должен выпустить другую запись.

Стойкость

В Voldemort поддерживается простой api для сохранения и используем версию BDB Java по умолчанию. Другие поддерживаемые устройства хранения данных - это MySQL, хранилище в памяти (используется для модульного тестирования) и собственный механизм хранения только для чтения (который генерируется автономно как пакетный процесс в Hadoop). Чтобы добавить новую реализацию сохранения, вам необходимо реализовать put, get и delete, а также предоставить итератор над значениями в локальном хранилище.

Установка

Установка Voldemort на Ubuntu:

1) Клонирование:

$ sudo apt-get git
$ git clone https://github.com/voldemort/voldemort

2) Установите последнюю версию OpenJDK:

$ sudo apt-get install default-jdk

3) Установите последнюю версии JRE:

$ sudo apt-get install default-jre

4) Для установки JAVA_HOME для всех пользователей отредактируйте файл bash.bashrc

$ gedit .bashrc

В конце файла допишите:

 JAVA_HOME=/usr/lib/jvm/java-*
 export JAVA_HOME
 PATH=$PATH:$JAVA_HOME
 export PATH

Вместо * укажите название папки, в которой установлена java, например:

 JAVA_HOME=/usr/lib/jvm/java-openjdk-amd64

Сохраните и откройте новый терминал.

5) Компилирование:

$ sudo apt install gradle
$ cd voldemort
$ ./gradlew clean build -x test

6) Voldemort предполагает, что у вас 2GB-машина. Поэтому нужно настроить два файла. Сначала отредактируйте сценарий запуска:

$ sudo nano bin/voldemort-server.sh

Найдите эти строчки:

 	if [ -z $VOLD_OPTS ]; then
  	  VOLD_OPTS="-Xmx2G -server -Dcom.sun.management.jmxremote"
  	fi

И замените 2G на 256M, выглядеть должно так:

  	if [ -z $VOLD_OPTS ]; then
  	  VOLD_OPTS="-Xmx256M -server -Dcom.sun.management.jmxremote"
  	fi

Сохраните и выйдите. Затем отредактируйте файл свойств, чтобы скорректировать параметр кеширования:

$ sudo nano config/single_node_cluster/config/server.properties 

Найдите эту строчку:

 bdb.cache.size=1G

И замените 1G на 128M, выглядеть должно так:

 bdb.cache.size=128M

7) Запуск кластера с одним узлом:

$ bin/voldemort-server.sh config/single_node_cluster

8) Откройте новый терминал. Запустите тестовый клиент командной строки и выполните некоторые операции:

$ cd voldemort
$ bin/voldemort-shell.sh test tcp://localhost:6666

Источники

  1. Wikiwand [Электронный ресурс]: Voldemort (distributed data store) / Дата обращения: 24.09.2017. — Режим доступа: http://www.wikiwand.com/en/Voldemort_(distributed_data_store)
  2. Project Voldemort [Электронный ресурс]: Project Voldemort / Дата обращения: 24.09.2017. — Режим доступа: http://www.project-voldemort.com/voldemort/
  3. Project Voldemort [Электронный ресурс]: Design / Дата обращения: 24.09.2017. — Режим доступа: http://www.project-voldemort.com/voldemort/design.html

Ссылки

  1. Usenix [Электронный ресурс]: Serving Large-scale Batch Computed Data with Project Voldemort / Дата обращения: 24.09.2017. — Режим доступа: https://www.usenix.org/legacy/events/fast12/tech/full_papers/Sumbaly.pdf
  2. Cyberleninka [Электронный ресурс]: Распределенные горизонтально масштабируемые решения для управления данными / Дата обращения: 24.09.2017. — Режим доступа: https://cyberleninka.ru/article/n/raspredelennye-gorizontalno-masshtabiruemye-resheniya-dlya-upravleniya-dannymi