СУБД. Параллелизм

Параллелизм

• Какая проблема решается?
• Правила игры.
• Пессимистичные блокировки.
• Оптимистичные блокировки.
• Lock-free.

Какая проблема решается?

Нет разделяемого состояния - нет проблем

1: SELECT * FROM account WHERE id = 42;
1: ...
1: UPDATE account SET money = 1234 WHERE id = 42;

1: SELECT * FROM account WHERE id = 42;
2: SELECT * FROM account WHERE id = 42;
1: ...
2: ...
1: UPDATE account SET money = 1234 WHERE id = 42;
2: UPDATE account SET money = 2345 WHERE id = 42;

Проблема не специфична для СУБД

Java

class Foo {
    private Helper helper = null;

    public Helper getHelper() {
        if (helper == null)
            helper = new Helper();
        return helper;
    }
}

Правила игры

Java Memory Model (JSR 133)

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

ACID

Требования к транзакционной системе, обеспечивающие наиболее надёжную и предсказуемую её работу.

Пессимистичные блокировки

SQL

SELECT * FROM account WHERE id = 42 FOR UPDATE;
...
UPDATE account SET money = 1234 WHERE id = 42;

class Foo {
    private Helper helper = null;

    public synchronized Helper getHelper() {
        if (helper == null)
            helper = new Helper();
        return helper;
    }
}

Пессимистичные блокировки

Пессимистическая блокировка

Это стратегия, при которой вы блокируете запись для вашего исключительного использования, пока не закончите с ней. Он имеет гораздо лучшую целостность, чем оптимистическая блокировка, но требует от вас быть осторожным с дизайном приложения, чтобы избежать тупиков. Для использования пессимистической блокировки необходимо либо прямое подключение к базе данных, либо внешне доступная транзакция ID, которая может использоваться независимо от подключения. В последнем случае вы открываете транзакцию с помощью TxID, а затем повторно подключаетесь с помощью этого ID. DBMS поддерживает блокировки и позволяет вам забрать сеанс обратно через TxID. Именно так работают распределенные транзакции, использующие двухфазные протоколы фиксации (такие как XA или COM + транзакции).

Пессимистичные блокировки

Когда вы оперируете lock’ами могут случиться четыре типа проблем:

• вы возьмете слишком мало локов (поломанные данные);
• вы возьмете слишком много локов (deadlock, starvation);
• вы возьмете не те локи (поломанные данные);
• вы возьмете те локи, но не в том порядке (deadlock).

Пессимистичные блокировки

DEADLOCK

Оптимистичные блокировки

Оптимистичная блокировка

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

Оптимистичные блокировки

SQL

SELECT * FROM account WHERE id = 42;
...
UPDATE account SET
  version = 8,
  money = 1234
WHERE id = 42
  AND version = 7;

SELECT xmin, * FROM account WHERE id = 42;
...
UPDATE account SET
  money = 1234
WHERE id = 42
  AND xmin = 1528942;

Оптимистичные VS Пессимистичные

• Пессимистичные блокировки проще;
• Пессимистичные блокировки подвержены DEADLOCK-ам;
• Если операции редко затрагивают одни и те же данные, то оптимистичные блокировки быстрее.

Lock-free очередь (сильно упрощенно)

void stack_push(stack* s, node* n) {
  node* head;
  do {
    head = s->head;
    n->next = head;
  } while (!atomic_compare_exchange(s->head, head, n));
}

node *stack_pop(stack* s) {
  node* head, next;
  do {
    head = s->head;
    next = head->next;
  } while (!atomic_compare_exchange(s->head, head, next));
  return head;
}