Олег Нурзаев
Ученик
(13),
на голосовании
1 год назад
Алиса хочет последовательно выполнить N транзакций вида
BEGIN ISOLATION LEVEL READ COMMITTED; SELECT value FROM T WHERE id = 2 FOR UPDATE; SELECT value FROM T WHERE id = 3 FOR UPDATE; SELECT value FROM T WHERE id = 4 FOR UPDATE; SELECT value FROM T WHERE id = 1 FOR UPDATE; UPDATE T SET value = value + 10 WHERE id BETWEEN 1 AND 4; COMMIT;
Если транзакция по каким-либо причинам обрывается, то Алиса немедленно повторяет её заново и делает так до тех пор, пока транзакция не закончится успешным подтверждением.
Одновременно с транзакцией Алисы с вероятностью p запускается транзакция Болванщика, которая выглядит так:
BEGIN ISOLATION LEVEL READ COMMITTED; SELECT value FROM T WHERE id = 1 FOR UPDATE; SELECT inc INTO _inc FROM R WHERE id = 1; UPDATE T SET value = value + _inc WHERE id=1; COMMIT;
Транзакции Алисы и Болванщика выполняются параллельно на разных процессорах, без каких-либо не указанных в задаче задержек и накладных расходов.
В нашей воображаемой базе данных каждый оператор SELECT FOR UPDATE выполняется за 2 миллисекунды, простой оператор SELECT выполняется за 1 миллисекунду, а оператор UPDATE выполняется за 10 миллисекунд. Если оператор ждет получения блокировки, то мы считаем, что он начинает выполняться с момента её получения. Если оператор по каким-то причинам оборвался, то время выполнения конкретно этого оператора мы считаем равным нулю. Все использующиеся таблицы и записи в нашей БД есть.
Алиса заметила, что Болванщик запускает свои транзакции не так уж и часто, и ей пришла в голову мысль о том, что замена уровня изоляции в её транзакции на REPEATABLE READ и всех операторов SELECT FOR UPDATE в её транзакции на простые SELECT несколько уменьшит время выполнения её транзакции, что для неё важно. Кроме того, у неё есть договорённость с Болванщиком о том, что если Алиса повторяет оборвавшуюся транзакцию, то в то время, пока она повторяется, Болванщик гарантированно ничего не будет делать.
Болванщик может сообщить Алисе значение вероятности p. Подскажите Алисе, при каких p имеет смысл воспользоваться уровнем REPEATABLE READ.
Запись ответа
В ответе должен быть записан интервал значений p, при которых матожидание времени, прошедшего от начала до успешного подтверждения транзакции Алисы с уровнем изоляции REPEATABLE READ будет строго меньше матожидания времени от начала до успешного выполнения транзакции с уровнем изоляции READ COMMITTED.
Интервал должен быть записан в виде (полу)открытого или закрытого отрезка. Границы отрезка должны быть целыми числами или несократимыми рациональными дробями. Границы должны быть отделены друг от друга запятой. Если значение границы входит в отрезок (то есть если он с этой стороны закрытый) то скобка должна быть квадратной, а если не входит, то круглой. Пробелов в ответе быть не должно. Примеры валидных ответов:
-- от нуля до единицы включительно [0,1] -- от нуля до единицы не включая 0 и 1 (0,1) [1/2,1) (1/3,2]
Примеры невалидных ответов:
-- пробел после запятой [0, 1] -- скобки не круглые и не квадратные {0,1} -- не рациональное число [0.5,1) -- дробь сократимая (2/6,2]
BEGIN ISOLATION LEVEL READ COMMITTED;
SELECT value FROM T WHERE id = 2 FOR UPDATE;
SELECT value FROM T WHERE id = 3 FOR UPDATE;
SELECT value FROM T WHERE id = 4 FOR UPDATE;
SELECT value FROM T WHERE id = 1 FOR UPDATE;
UPDATE T SET value = value + 10 WHERE id BETWEEN 1 AND 4;
COMMIT;
Если транзакция по каким-либо причинам обрывается, то Алиса немедленно повторяет её заново и делает так до тех пор, пока транзакция не закончится успешным подтверждением.
Одновременно с транзакцией Алисы с вероятностью p запускается транзакция Болванщика, которая выглядит так:
BEGIN ISOLATION LEVEL READ COMMITTED;
SELECT value FROM T WHERE id = 1 FOR UPDATE;
SELECT inc INTO _inc FROM R WHERE id = 1;
UPDATE T SET value = value + _inc WHERE id=1;
COMMIT;
Транзакции Алисы и Болванщика выполняются параллельно на разных процессорах, без каких-либо не указанных в задаче задержек и накладных расходов.
В нашей воображаемой базе данных каждый оператор SELECT FOR UPDATE выполняется за 2 миллисекунды, простой оператор SELECT выполняется за 1 миллисекунду, а оператор UPDATE выполняется за 10 миллисекунд. Если оператор ждет получения блокировки, то мы считаем, что он начинает выполняться с момента её получения. Если оператор по каким-то причинам оборвался, то время выполнения конкретно этого оператора мы считаем равным нулю. Все использующиеся таблицы и записи в нашей БД есть.
Алиса заметила, что Болванщик запускает свои транзакции не так уж и часто, и ей пришла в голову мысль о том, что замена уровня изоляции в её транзакции на REPEATABLE READ и всех операторов SELECT FOR UPDATE в её транзакции на простые SELECT несколько уменьшит время выполнения её транзакции, что для неё важно. Кроме того, у неё есть договорённость с Болванщиком о том, что если Алиса повторяет оборвавшуюся транзакцию, то в то время, пока она повторяется, Болванщик гарантированно ничего не будет делать.
Болванщик может сообщить Алисе значение вероятности p. Подскажите Алисе, при каких p имеет смысл воспользоваться уровнем REPEATABLE READ.
Запись ответа
В ответе должен быть записан интервал значений p, при которых матожидание времени, прошедшего от начала до успешного подтверждения транзакции Алисы с уровнем изоляции REPEATABLE READ будет строго меньше матожидания времени от начала до успешного выполнения транзакции с уровнем изоляции READ COMMITTED.
Интервал должен быть записан в виде (полу)открытого или закрытого отрезка. Границы отрезка должны быть целыми числами или несократимыми рациональными дробями. Границы должны быть отделены друг от друга запятой. Если значение границы входит в отрезок (то есть если он с этой стороны закрытый) то скобка должна быть квадратной, а если не входит, то круглой. Пробелов в ответе быть не должно. Примеры валидных ответов:
-- от нуля до единицы включительно
[0,1]
-- от нуля до единицы не включая 0 и 1
(0,1)
[1/2,1)
(1/3,2]
Примеры невалидных ответов:
-- пробел после запятой
[0, 1]
-- скобки не круглые и не квадратные
{0,1}
-- не рациональное число
[0.5,1)
-- дробь сократимая
(2/6,2]