Транзакционные параллельные СУБД новая волна


Автоматизация методов разделения и реплицирования баз данных - часть 2


База данных

Рабочая нагрузка

ACCOUNT
id name balance
1 Carlo 80K
2 Evan 100K
3 Sam 129K
4 Eugene 29K
5 Yang 12K

  I  

BEGIN

UPDATE account SET bal=bal-1k
  WHERE name="carlo";

UPDATE account SET bal=bal+1k
  WHERE name="evan";

COMMIT

  II  

BEGIN

UPDATE account SET bal=60k

  WHERE id=2;

SELECT * FROM account

  WHERE id=5;

COMMIT

  III  

BEGIN

SELECT * FROM account

  WHERE id IN {1,3};

ABORT

  IV  

BEGIN

UPDATE account SET bal=bal+1k

  WHERE bal < 100k;

COMMIT

Рис. 4. Примерные база данных и рабочая нагрузка.

Рис. 5. Общая идея графа, использумого для разделения базы данных.

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

Рис. 6. Граф с учетом возможности репликации.

На рис. 6 показано расширенное представление графа с учетом возможности репликации на уровне кортежей. Для этого каждая вершина, соответствующая кортежу, к которому обращается n > 1 транзакций, заменяется "звездообразным" подграфом из n+1 вершин. Веса дуг, соединяющих вершины-реплики с центральной вершиной, характеризуют стоимость репликации данного кортежа и определяются как число транзакций в данной рабочей нагрузке, обновляющих данный кортеж. Например, на рис. 6 показано, что кортеж с id=1 представлен четырьмя вершинами, поскольку к нему обращаются три транзакции (I, III и IV). Веса дуг у соответствующего подграфа равны 2, поскольку только транзакции I и IV обновляют этот кортеж.


Начало  Назад  Вперед



Книжный магазин