company_banner

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

    В эти выходные прошел Joker 2018, было интересно! Но не одними выступлениями была богата конференция. Все компании-спонсоры старались выделиться на фоне «конкурентов» и мы — не исключение.

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

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



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


    Петя и Коля коммитят в Apache Ignite по одной фиче в сутки.

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

    Cколько фич будет закоммичено за 86 рабочих дней, если Маше нравится Петя,
    и она замечает его ошибку лишь в тот день, когда ошибается только он?


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

    Ответ
    64 + 54 = 118;

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


    Процессинг ненадежного банка при операциях над группой счетов блокирует ключи
    счетов в порядке их объявления в операции, т.е. слева направо.
    Каждый дедлок решается специалистами банка вручную и занимает в 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" - Сережа едет на Бали
    }
    

    Подсказка №1
    — 131072?
    — Нет, вылезай из ловушки :)
    Подсказка №2
    Какая минимальная ставка может принести Сереже выигрыш?
    Подсказка №3
    th1{
    	bid.restricted = true;
    	bid.checked = true;
    }
    ...
    th2{
    	while (!bid.checked) {
    		sleep(1);
    	}
    	assert bid.restricted; // 99.999%
    }
    

    Тут нет интуитивно ожидаемых гарантий видимости.

    Добавить их можно следуюшим образом:

    volatile boolean checked;
    

    Подсказка №4
    Какая минимальная ставка может принести Сереже выигрыш?
    Решение

    Ответ
    java.lang.Integer#MIN_VALUE

    Впрочем, «0» и даже «1» расценивались как верное решение.

    Победители


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

    Ребята получили фирменные рюкзаки, футболки и, конечно же, книги.
    • +12
    • 4,4k
    • 1
    Сбербанк
    206,00
    Компания
    Поделиться публикацией

    Комментарии 1

      0
      В Воронеже на РИФе у Сбербанка на стенде тоже такая 360-камера крутилась.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое