Schism: управляемый рабочей нагрузкой подход к репликации и разделению баз данных

Карло Курино, Эван Джонс, Янг Жанг и Сэм Мэдден
Перевод: Сергей Кузнецов

Назад Содержание

10. Литература

1. S. Agrawal, V. Narasayya, and B. Yang. Integrating vertical and horizontal partitioning into automated physical database design. In SIGMOD, 2004.
2. F. Chang, J. Dean, S. Ghemawat, W. Hsieh, D. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber. Bigtable: A distributed storage system for structured data. In OSDI, 2006.
3. B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!’s hosted data serving platform. PVLDB, 1(2), 2008.
4. B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with ycsb. SoCC, 2010.
5. C. Curino, E. Jones, Y. Zhang, E. Wu, and S. Madden. Relationalcloud: The case for a database service. New England Database Summit, 2010.
6. D. DeWitt and J. Gray. Parallel database systems: the future of high performance database systems. Comm. ACM, 1992.
   Перевод на русский язык: Дэвид Девитт, Джим Грей. Параллельные системы баз данных: будущее высоко эффективных систем баз данных, 2009.
7. R. Freeman. Oracle Database 11g New Features. McGraw-Hill, Inc., New York, NY, USA, 2008.
8. S. Ghandeharizadeh and D. J. DeWitt. Hybrid-range partitioning strategy: a new declustering strategy for multiprocessor databases machines. In VLDB, 1990.
9. M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten. The weka data mining software: An update. SIGKDD Explorations, 11, 2009.
10. G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1), 1998.
11. G. Karypis and V. Kumar. METIS - Family of Multilevel Partitioning Algorithms, 2010.
12. B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal 49, pages 291–307, 1970.
13. R. Khandekar, S. Rao, and U. Vazirani. Graph partitioning using single commodity flows. J. ACM, 56(4):1–15, 2009.
14. M. Koyutürk and C. Aykanat. Iterative-improvement-based declustering heuristics for multi-disk databases. Journal of Information Systems, 30(1):47–70, 2005.
15. P. Massa and P. Avesani. Controversial users demand local trust metrics: an experimental study on epinions.com community. In AAAI’05, 2005.
16. J. M. Pujol, G. Siganos, V. Erramilli, and P. Rodriguez. Scaling online social networks without pains. NetDB, 2009.
17. J. R. Quinlan. C4.5: Programs for machine learning. Morgan Kaufmann Series in Machine Learning, 1993.
18. J. Rao, C. Zhang, N. Megiddo, and G. Lohman. Automating physical database design in a parallel database. In SIGMOD, 2002.
19. D. ren Liu and S. Shekhar. Partitioning similarity graphs: A framework for declustering problems. ISJ, 21, 1996.
20. N. Selvakkumaran and G. Karypis. Multi-objective hypergraph partitioning algorithms for cut and maximum subdomain degree minimization. In ICCAD, 2003.
21. M. Stonebraker, S. Madden, D. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era: (it’s time for a complete rewrite). In VLDB, 2007.
    Перевод на русский язык: Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд. Конец архитектурной эпохи, или Наступило время полностью переписывать системы управления данными, 2007.
22. M. M. Tsangaris and J. F. Naughton. A stochastic approach for clustering in object bases. SIGMOD Rec., 20(2), 1991.
23. D. C. Zilio. Physical database design decision algorithms and concurrent reorganization for parallel database systems. In PhD thesis, 1998.

Приложения

A. Аппаратно-программная конфигурация

Эксперименты, описанные в разд. 3 и подразделе 6.3, выполнялись на восьми серверах с MySQL, соединенных через один коммутатор Gigabit Ethernet. Более мощная машина использовалась для генерации трафика и выполнения экспериментов с производительностью времени выполнения, описанных в подразделе 6.2. Подробности о составе аппаратных и программных средств собраны в табл. 2.

Табл. 2. Экспериментальные системы.

B. Гиперграфы

Вместо того, чтобы представлять транзакции в виде набора дуг, соединяющих вершины, мы использовали их представление в виде одной гипердуги, соединяющей все вершины, к которым обращается данная транзакция. Это представление является несколько более естественным, поскольку число разрезов гипердуг в точности совпадает с числом распределенных транзакций. Кроме того, мы расчитывали, что разделение гиперграфа позволит обеспечить более высокое качество, основываясь на результатах, которые описаны в литературе о разделении графов [20], и предыдущих статьях сообщества баз данных, которые посвящены использованию такого подхода [14]. Однако после выполнения активного тестирования с применением наиболее популярных библиотек разделения гиперграфов (hMETIS и Zoltan-PHG) мы установили, что разделение графов выполняется быстрее и обеспечивает лучшие результаты. Мы полагаем, что это объясняется более широким использованием и изучением методов разделения графов, в результате чего соответствующие инструментальные средства обладают большей зрелостью.

В результате нам пришлось аппроксимировать гиперграф набором дуг в графе. Известно, что это трудная задача. После пропуска многочисленных тестов мы решили использовать для представления транзакций полные подграфы (clique), а для репликации – звездообразное представление (меньше дуг для кортежей, доступ к которым происходит очень часто). Эта комбинация представлений обеспечила получение хороших результатов и приемлемые размеры графов.

C. Разделение и маршрутизация

В этом приложении мы обсудим две проблемы маршрутизации запросов: i) как можно работать с поисковыми таблицами, и ii) как следует использовать схемы разделения (поисковые таблицы, предикаты диапазонов, хэширование) для маршрутизации запросов и операций обновления на правильные машины.

C.1 Поисковые таблицы

Как описывалось в подразделе 4.2, поисковые таблицы оказываются полезными в тех случаях, когда в данных имеется некоторая локальность, не очевидная по схеме базы данных. Чтобы получить наилучшее разделение для данных этого типа, необходимо поддерживать информацию о разделении для каждого отдельного кортежа. На логическом уровне это представляет собой отображение между кортежами и идентификаторами разделов. Поддерживать это отображение для всех атрибутов кортежей невозможно. Однако во многих приложениях доступ к данным, в основном, производится по первичному ключу, значения которого обычно образуют плотное множество целых чисел, генерируемых системой. Для приложений такого типа хранение и поддержка поисковых таблиц могут быть очень эффективными. К этой информации можно относиться как к "мягкому состоянию" ("soft state"), потому что в случае отказа системы ее легко можно восстановить путем сканирования базы данных.

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

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

В настоящее время мы изучаем возможности (i) наилучшей реализации поисковых таблиц для распределенных баз данных, (ii) определения того, когда лучше использовать поисковые таблицы, а не традиционные хэш-разделение и разделение по диапозонам значений, а также (iii) выбора наилучшей реализации для каждого сценария.

C.2 Маршрутизация запросов и операций обновления

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

Наша система предоставляет приложениям для задания операторов интерфейс JDBC. Получив такой оператор, наш компонент маршрутизации выполняет следующие шаги: i) разбирает этот оператор, ii) извлекает из раздела WHERE предикаты над атрибутами таблицы, iii) сопоставляет атрибуты со схемой разделения для получения списка целевых разделов. Затем координатор распределенных транзакций управляет выполнением оператора на нескольких машинах.

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

Разделение работает наиболее эффективно, если в разделе WHERE большинства запросов используются атрибуты разделения. Именно поэтому на фазе толкования Schism пытается использовать атрибуты, наиболее часто используемые в разделах WHERE.

D. Наборы данных

В этом разделе приводятся дополнительные подробности относительно тестовых наборов, упоминавшихся в разд. 6.

D.1 Yahoo! Cloud Serving Benchmark

Yahoo! Cloud Serving Benchmark (YCSB) – это коллекция простых тестовых микронаборов, разработанных с целью представления приложений управления данными, являющихся простыми, но требующими высокого уровня масштабируемости [4]. Этот тестовый набор ориентирован на оценку распределенных систем хранения данных "ключ-значение", подобных тем, которые созданы компаниями Yahoo, Google и в различных проектах категории open source. В нашей работе этот стандартизованный и простой тестовый набор использовался для получения представления о некоторых возможностях нашего инструментального средства, например, о его возможности прибегать к использованию более дешевых стратегий разделения в случае совпадения ожидаемых результатов.

Из пяти основных рабочих нагрузок YCSB мы выбрали рабочие нагрузки A и E. Рабочая нагрузка является смесью 50/50 операций чтения и записи одного кортежа, выбираемого случайным образом по распределению Зипфа. Если игнорировать потенциальные трудности достижения хорошей производильности при работе с данными масштаба Internet, для разделения эта проблема является очень простой. На самом деле, за исключением случая полной репликации, любая стратегия разделения обладает нулевой стоимостью, поскольку транзакции обращаются только к одному кортежу. Поэтому целью пропуска этого теста являлась демонстрация способности нашей системы выбирать более дешевую стратегию разделения (например, хэш-разделения), если она существует.

Рабочая нагрузка E является смесью 95/5 операций чтения и записи, причем при чтении производится короткое сканирование (длина сканирования выбирается равномерным случайным образом в диапазоне от 1 до 100 кортежей), а запись затрагивает один кортеж. Начальная точка сканирования и кортеж для записи выбирались случайным образом по распределению Зипфа. Эта рабочая нагрузка показывает непригодность схемы хэш-разделения для запросов по диапазонам значений, а также то, что наше средство может автоматически выбирать точки расщепления по предикатам диапазонов, что приводит к близкой к оптимальной стратегии разделения.

D.2 TPC-C

Тестовый набор TPC-C разработан для имитации рабочей нагрузки OLTP системы обработки заказов. В своей реализации мы не следовали строго требованиям спецификации TPC-C. В частности, для генерации высокой пропускной способности при малых размерах наборов данных в симуляторах клиентов не используется указанное в спецификации TPC-C "время на размышление", и следующая транзакция запрашивается сразу после получения ответа от предыдущей транзакции. Поэтому наши результаты, представленные в подразделе 6.3, не предназначаются для сравнения с другими системами, а лишь показывают относительную производительность конфигураций, в которых производилось тестирование.

Схема базы данных TPC-C включает 9 таблиц с 92 столбцами (в общей сложности), 8 первичными ключами и 9 внешними ключами. В рабочую нагрузку TPC-C входят транзакции пяти типов.

D.3 TPC-D

Тестовый набор TPC-D – это тестовый набор OLTP, более сложный, чем TPC-C. Он моделирует брокерскую компанию, которая выполняет сделки от имени клиентов. И в этом случае наша реализация не полностью соответствует спецификации, но мы старались генерировать корректные данные и транзакции. Схема базы данных TPC-D включает 33 таблицы со 188 столбцами (в общей сложности), 33 первичными ключами, 50 внешними ключами и 22 ограничениями целостности. В рабочую нагрузку TPC-C входят транзакции десяти типов.

D.4 Epinions.com

Целью эксперимента с Epinions.com являлось испытание нашей системы на сценарии, который трудно поддается разделению. Выявлялась эффективность системы при обнаружении важных корреляций между данными, которые не видны на уровне схемы или запросов. Наша схема базы данных Epinions.com включает четыре отношения: users, items, reviews и trust. Отношение reviews представляет связи n-к-n между пользователями (users) и товарами (items) (связываются отзывы пользователей и рейтинги товаров). Отношение trust представляет связи n-к-n между парами пользователей, указывая, что они другу другу доверяют. Данные были предоставлены Паоло Масса (Paolo Massa) из группы разработчиков Epinions.com. Поскольку рабочую нагрузку нам не предоставили, мы создали запросы, примерно соответствующие функциональности этого Web-сайта:

Q1:	для заданных пользователя и товара выбрать рейтинги, заданные пользователями, которым он доверяет;
Q2:	выбрать список пользователей, которым доверяет данный пользователь;
Q3:	для заданного товара выбрать взвешенное среднее всех рейтингов;
Q4:	для заданного товара выбрать 10 наиболее популярных отзывов;
Q5:	выдать 10 наиболее популярных отзывов данного пользователя;
Q6:	вставить/изменить профиль пользователя;
Q7:	вставить/изменить метаданные товара;
Q8:	вставить/изменить отзыв;
Q9:	обновить информацию о доверии пары пользователей друг к другу.

Для получения разделения вручную были привлечены студенты, действовавшие в качестве администраторов базы данных. Найти хорошее разделение оказалось непросто, поскольку запросы опирались на связи n-к-n с конфликтующими требованиями к группировке таблиц и кортежей. Например, при выполнении запроса Q1 будут производиться обращения к одному разделу, если данные разделены по товарам, а рейтинги и доверительные отношения сохраняются вместе с товарами. В то же время при выполнении запроса Q2 будут производиться обращения к одному разделу, если данные разделены по пользователями, и доверительные отношения сохраняются вместе с пользователями. Предложенное студентами решение заключалось в оптимизации запросов, наиболее часто встречавшихся в рабочей нагрузке (Q1 и Q4), путем разделения таблиц items и reviews на основе одной и той же хэш-функции, и репликации таблиц users и trust в каждом узле.

D.5 Random

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

Назад Содержание