Управление параллелизмом на основе временных меток

Question

В управлении параллелизмом на основе временной метки, почему вы должны отклонить запись в транзакции T_i на элементе x_k, если какая-то транзакция с T_j, где j > i, уже прочитала ее?

Как указано в документе.

Если T_j вообще не планирует делать какие-либо обновления, почему нужно быть настолько ограничительным в действиях T_i?

Answer 1

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

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

Любые два чтения одного и того же значения в одно и то же время опасны, так как вызывают неточное представление базы данных, выявляя несериализуемый порядок. Если выполняются три транзакции, и все они используют x, то сериализуемый порядок не определен. Вам нужно обеспечить одно чтение x за раз, и это заставляет транзакции быть одним файлом и видеть последнюю транзакцию x. Итак, t_i, затем t_j, затем t_k по порядку, заканчивая до начала следующего.

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

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

Как свидетельствует технический документ Serializable Snapshot Isolation, опасная структура — это две зависимости чтения-записи. Но чтение-запись x, за которой следует чтение x, опасно также из-за того, что значение устарело, если обе транзакции выполняются одновременно, оно должно быть сериализуемым, поэтому вы прерываете второе чтение x, так как есть более молодая транзакция, использующая x.

Я написал реализацию многоверсионного параллелизма в симуляции. Смотрите бегун симуляции.Моя симуляция имитирует 100 потоков, каждый из которых пытается прочитать и записать два числа, A и B. Они хотят увеличить число на 1. Мы устанавливаем A на 1 и B на 2 в начале симуляции.

Желаемый результат состоит в том, что A и B должны быть установлены на 101 и 102 в конце симуляции. Это может произойти только в том случае, если есть блокировка или сериализация из-за управления параллельным выполнением нескольких версий. Если у вас не было управления параллелизмом или блокировки, это число будет меньше 101 и 102 из-за гонки данных.

Когда поток читает A или B, мы перебираем версии ключа A или B, чтобы увидеть, есть ли версия, которая является <= transaction.getTimestamp() и commit.get(key) == этой версией. В случае успеха он устанавливает отметку времени чтения этого значения как транзакцию, которая в последний раз читала это значение. rts.put("A", транзакция)

Во время фиксации мы проверяем, что rts.get("A").getTimestamp() != committingTransaction.getTimestamp() . Если эта проверка верна, мы прерываем транзакцию и пытаемся снова.

Мы также проверяем, совершил ли кто-либо коммит с момента начала транзакции — мы не хотим перезаписывать его коммит.

Мы также проверяем для каждой записи, что другая записывающая транзакция моложе нас, после чего прерываем. Оператор if находится в методе с именем shouldRestart, и он вызывается при чтении и во время фиксации, а также для всех транзакций, которые коснулись значения.

      public boolean shouldRestart(Transaction transaction, Transaction peek) {
    boolean defeated =  (((peek.getTimestamp() < transaction.getTimestamp() ||
            (transaction.getNumberOfAttempts() < peek.getNumberOfAttempts())) && peek.getPrecommit()) ||
            peek.getPrecommit() && (peek.getTimestamp() > transaction.getTimestamp() ||
                    (peek.getNumberOfAttempts() > transaction.getNumberOfAttempts() && peek.getPrecommit())
                    && !peek.getRestart()));

    return defeated;
}

см. код здесь . Или && peek.getPrecommit() означает, что более ранняя транзакция может прерваться, если более поздняя транзакция опережает и более поздняя транзакция не была перезапущена (прервана). Предварительная фиксация происходит в начале фиксации.

Во время чтения ключа мы проверяем RTS, чтобы убедиться, что он ниже, чем чтение, чем наша транзакция. Если да, то прерываем транзакцию и перезапускаем — кто-то стоит впереди нас в очереди и ему нужно совершить коммит.

В среднем система достигает значений 101 и 102 примерно после < 300 прерываний транзакций. Со многими прогонами, заканчивающимися намного ниже 200 попыток.

РЕДАКТИРОВАТЬ: я изменил формулу для расчета выигрышных транзакций. Поэтому, если другая транзакция моложе или у других транзакций больше попыток, текущая транзакция прерывается. Это уменьшает количество попыток.

РЕДАКТИРОВАТЬ: причина большого количества прерываний заключалась в том, что поток фиксации будет голодать, читая потоки, которые прервут перезапуск из-за потока фиксации. Я добавил Thread.yield при сбое чтения из-за опережающей транзакции, это уменьшает количество перезапусков до <200.