СберТех ♥ Open Source, concurrency и надежные банковские операции — разбор решений задач с Joker 2018

Много интересного было на стенде Сбербанк-Технологий, но я хочу рассказать о том чем выделились именно мы. Наша команда, занимающаяся развитием Apache Ignite в СберТехе, подготовила задачи и провела розыгрыш среди тех, кто отважился их решить.

Под катом вас ожидают задачи, разбор решений и возможность обосновать собственный вариант решения в комментариях.

Горе-коммитеры

Петя и Коля коммитят в Apache Ignite по одной фиче в сутки.
Маша оперативно тестирует каждую фичу и откатывает коммиты, содержащие ошибки.
Каждый третий первоначальный коммит от Пети и пятый от Коли содержат ошибку.
Петя тратит на исправление ошибки дополнительные 2 дня, Коля 3, и они снова делают
коммит.
Cколько фич будет закоммичено за 86 рабочих дней, если Маше нравится Петя,
и она замечает его ошибку лишь в тот день, когда ошибается только он?

Решение

Начиная с 13-го дня, образуется цикличность позволяющая Пете фиксить только каждую вторую свою ошибку.

Вилларибо и Виллабаджо

Процессинг ненадежного банка при операциях над группой счетов блокирует ключи
счетов в порядке их объявления в операции, т.е. слева направо.
Каждый дедлок решается специалистами банка вручную и занимает в 10 раз больше
времени, чем обычная операция.
Процессинг надежного банка всегда блокирует ключи по возрастанию, но тратит в 2
раза больше времени, чем на обычную операцию в ненадежном банке.
В обоих банках 10 счетов, ключи счетов — числа от 1 до 10.
Процессингу каждого банка необходимо провести 12 операций.
Операции проводятся параллельно, по две за раз. Каждая операция затрагивает до 3-х
счетов:
— операция №1 (счета: A,B,C), где A=i, B=A+1, C=(A+B)%10,
— операция №2 (счета: D,E,F), где D=11-i, E=D-1, F=(D+E)%10,
i меняется от 1 до 6.
Выполнение последующей пары операций начинается только после полного завершения
предыдущей.
Ключи блокируются согласно политике банка, по одному в каждой из операций, начиная
с операции №1.
Если ключ уже заблокирован в одной из операций, но требуется для выполнения другой,
то сначала полностью завершается первая операция, затем продолжается вторая.
Вынужденное выполнение пары операций в последовательном режиме, ожидаемо, происходит в 2 раза медленнее чем в параллельном.
Какой банк и во сколько раз быстрее завершит проводить операции?

Подсказка

Итого:
— 6 итераций,
— 12 операций,
— во всех операциях, кроме одной, по 3 ключа.

Решение

Если все ключи разные — параллельное выполнение возможно.
Если нет — то нет, и возможен дедлок.

Рассчеты

Ненадежный банк тратит на операцию 1 «такт», 2 в случае «сложностей» и целых 10 в случае дедлока.
Надежный банк тратит на операцию 2 «такта» и 4 в случае «сложностей». Дедлоков у надежного не бывает.

Риски публичных репозиториев

Сережа очень опытный программист, крайне азартный и бесконечно жадный.
Однажды он нашел исходный код своего любимого тотализатора на гитхабе.
Какая минимальная ставка может принести Сереже выигрыш?
Упрощенный листинг тотализатора прилагается:

class Bid { // Ставка 	int amount; 	boolean checked; 	boolean restricted; 	Bid(int amount) {this.amount = amount;} } ~~~ AtomicReference<Bid> ref = new AtomicReference<>(); volatile boolean winner = false; ~~~ Thread validator = new Thread(() -> { // Запущен заранее! 	while (true) { 		Bid bid = ref.get(); 		if (bid == null) continue; 		if ((((bid.amount << 5) ^ 1_000_000) >>> 6) < (2 << 15)) 			bid.restricted = true; 		bid.checked = true; 	} }); Thread payer = new Thread(() -> { // Запущен заранее! 	while (true) { 		Bid bid = ref.get(); 		if (bid == null) continue; 		if (bid.checked) { 			if (!bid.restricted) 				winner = true; // Выигрыш! 			ref.set(null); 		} 	} }); ~~~ synchronized boolean makeMeRich(int amount){ // Какую ставку сделает Сережа? 	if (winner) return false; // Сережа должен торопиться - приз всего один 	ref.set(new Bid(amount));  	while(ref.get() != null) sleep(1); 	return winner; // Если вернется "true" - Сережа едет на Бали } 

th1{ 	bid.restricted = true; 	bid.checked = true; } ... th2{ 	while (!bid.checked) { 		sleep(1); 	} 	assert bid.restricted; // 99.999% } 

volatile boolean checked; 

Решение

java.lang.Integer#MIN_VALUE

Победители

Лучше всех задачи решили
— Евгений Зубенко
— Александр Новиков
— Андрей Голиков

Ребята получили фирменные рюкзаки, футболки и, конечно же, книги.