SberTech ♥ Open Source, concurrency and reliable banking operations - problem analysis with Joker 2018

    This weekend was Joker 2018 , it was interesting! But not only by speeches was the conference rich. All sponsoring companies tried to stand out against the “competitors” and we are no exception.

    There was a lot of interesting things on the Sberbank-Technologies stand, but I want to tell you about how we stood out. Our Apache Ignite development team at SberTech prepared tasks and conducted a rally for those who dared to solve them.

    Under the cut you are waiting for the task, the analysis of solutions and the ability to justify your own solution in the comments.



    Woe-committers


    Petya and Kolya commit in Apache Ignite one feature per day.

    Masha promptly tests each feature and rolls back commits containing errors.
    Every third initial commit from Petit and the fifth from Kolya contain an error.
    Petya spends an additional 2 days on correcting the error, Kolya 3, and they again
    commit.

    How many features will be committed for 86 working days, if Masha likes Petya,
    and she notices his mistake only on the day when only he is mistaken?


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

    Answer
    64 + 54 = 118;

    Villaribo and Villabaggio


    Processing an unreliable bank during operations on a group of accounts blocks the keys of the
    accounts in the order they are declared in the operation, i.e. from left to right.
    Each deadlock is solved manually by the bank’s specialists and takes 10 times longer
    than the usual operation.
    Processing a reliable bank always blocks the keys in ascending order, but spends 2
    times more time than a normal operation in an unreliable bank.
    In both banks there are 10 accounts, the keys of the accounts are numbers from 1 to 10.
    The processing of each bank requires 12 operations.
    Operations are carried out in parallel, two at a time. Each operation affects up to 3
    accounts:
    - operation №1 (accounts: A, B, C), where A = i, B = A + 1, C = (A + B)% 10,
    - operation №2 (accounts: D, E, F), where D = 11-i, E = D-1, F = (D + E)% 10,
    i changes from 1 to 6.
    The following pair of operations starts only after the full completion of the
    previous one.
    The keys are locked according to the policy of the bank, one in each of the operations, starting
    with operation No. 1.
    If the key is already locked in one of the operations, but is required to perform the other,
    then the first operation is fully completed first, then the second one continues.
    Forced execution of a pair of operations in sequential mode, as expected, occurs 2 times slower than in parallel.
    What bank and how many times faster will complete operations?

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

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

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

    Answer
    Завершат одновременно.

    Risks of public repositories


    Serezha is a very experienced programmer, extremely reckless and endlessly greedy.
    Once he found the source code of his favorite tote on a githaba.
    What is the minimum bet that Serezha can win?

    A simplified tote listing is attached:

    classBid{ // Ставкаint amount;
    	boolean checked;
    	boolean restricted;
    	Bid(int amount) {this.amount = amount;}
    }
    ~~~
    AtomicReference<Bid> ref = new AtomicReference<>();
    volatileboolean 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);
    		}
    	}
    });
    ~~~
    synchronizedbooleanmakeMeRich(int amount){ // Какую ставку сделает Сережа?if (winner) returnfalse; // Сережа должен торопиться - приз всего один
    	ref.set(new Bid(amount)); 
    	while(ref.get() != null) sleep(1);
    	return winner; // Если вернется "true" - Сережа едет на Бали
    }
    

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

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

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

    volatileboolean checked;
    

    Tip # 4
    Какая минимальная ставка может принести Сереже выигрыш?
    Decision

    Answer
    java.lang.Integer#MIN_VALUE

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

    Winners


    Best of all, the tasks were solved
    - Evgeny Zubenko
    - Alexander Novikov
    - Andrei Golikov The

    guys received branded backpacks, T-shirts and, of course, books.

    Also popular now: