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

В эти выходные прошел 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 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

Победители

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

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

© Habrahabr.ru