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

Параллелизм

• Какая проблема решается?
• Правила игры.
• Пессимистичные блокировки.
• Оптимистичные блокировки.
• 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;
    }
}

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

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

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

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

DEADLOCK

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

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;
}