Разбор задачек от Одноклассников на JPoint 2018

в 15:56, , рубрики: java, jpoint, puzzlers, Блог компании Одноклассники

Алоха!

Самым, наверное, интересным событием на этой неделе в мире Java стала конференция JPoint, которая прошла в Центре Международной Торговли в Москве. Одноклассники предложили посетителям тоже поучаствовать в разработке самой высоконагруженной системы на Java и помочь нашим разработчикам в решении практических задач, с которыми они сталкиваются в своей работе.
Одиннадцать человек, лучше всех решивших эти задачки уже получили от нас призы, ну а для остальных мы запилли этот пост с разбором решений.

Чтобы вам удобнее было сначала попробовать решить задачки самим, мы скрыли правильные ответы под спойлером. Чур, открывать только после того, как сами додумались до решения ;-)

Поехали!

Задача о Вадиме и партитуре

Вадим написал следующий код для партиционирования музыкальных треков по серверам. Что он сделал не так? Исправьте ошибку Вадима в коде:

    /**
     * @return partition between 0 inclusive
     *         and partitions exclusive
     */
    int partition(Track track, int partitions) {
        assert track != null;
        assert partitions > 0;    
        return track.hashCode() % partitions;    
    }
Решение

Очевидная проблема в коде Вадима в том, что track.hashCode() может возвращать как положительные, так и отрицательные значения.
Вадим же человек аккуратный ( вы посмотрите сколько assertов! ), значит, комментарий к методу он тоже написал аккуратно, а там указано, что метод вернет число в интервале от 0 до partitions исключительно.
Очевидным способом исправить проблему будет немного другая концовка метода, например, такая:

        return Math.abs( track.hashCode() ) % partitions;

Казалось бы — ура и в продакшен! Но есть одна менее очевидная проблема — по спецификации hashCode() вполне себе может вернуть и Integer.MIN_VALUE, а попытка взять от такого числа Math.abs ни к чему хорошему не приведет.

Ох, говорила мама, следи за скобками, сынок! Правильно будет как-то так:

        return Math.abs( track.hashCode() % partitions );

Другая, более серьезная проблема Вадима гораздо менее очевидна. Способ, который он выбрал для того, чтобы распределять данные по серверам не консистентен — при изменении количества партиций ( например, при добавлении серверов ) все треки перераспределяются по кластеру практически полностью. Если треков мало — проблем не много, а если кластер большой и треков там на сотни терабайт — их все надо переместить между серверами. А Вадим уже залил терабайты треков на сотню — другую серверов…

Эх, Вадим, Вадим! Использовал бы ты какой либо из вариантов консистентных хешей, не болела бы у тебя сейчас голова.

Леонид работает дворником

Леонид написал такой код для очистки временных файлов из директории. Что он сделал не так?

    void cleanup(Path dir) throws IOException {
        for (Path file :
                Files.newDirectoryStream(dir)) {
            if (file.endsWith(".tmp")) {
                Files.delete(file);
            }
        }
    }
Решение

Леонид очень торопился выкатить очистку мусора в продакшен и невнимательно изучил документацию к DirectoryStream. DirectoryStream implements AutoCloseable. То есть имеет метод close(). А если что-то имеет такой метод — он должен вызываться. Последствия не заставили себя ждать — выкатив новую версию в продакшен он обнаружил утечку нативной памяти в java процессе.

Поскольку релиз включал не только этот код, источник утечки однозначно определить было нельзя и Леониду пришлось изучить как можно определять нативные утечки. При профилировании нашлась утечка при вызове нативного метода __alloc_dir, который как раз вызывается в результате вызова Files.newDirectoryStream. Леонид хлопнул себя по лбу и исправил проблему:

    void cleanup(Path dir) throws IOException {
       try ( DirectoryStream<Path> stream = Files.newDirectoryStream(dir) ) {
          for (Path file : stream) {
              if (file.endsWith(".tmp")) {
                  Files.delete(file);
              }
          }
        }
    }

— «Ура!», сказал Леонил и выкатил релиз. И снова поторопился.
Ведь еще неплохо было бы проверить, что file из стрима является файлом, а не директорией, например добавив условие с Files.isRegularFile(file).
Также Леонид забыл, что Files.delete может выбросить IOException и процесс очистки прервётся — с этим тоже надо что-то делать.

«Зря я пошел в дворники» подумал про себя Леонид…

Бедная Даша

Даша мигрирует код с Java 10 на legacy систему, работающую под Java 8. На что ей нужно заменить `var`, чтобы программа скомпилировалась?

    var list = Arrays.asList("1", 2, 3.0);

Выберите подходящие ответы:

  1. `List<?>`
  2. `List<? super Comparable>`
  3. `List<? extends Comparable>`
  4. `List<? extends Comparable & Serializable>`
  5. `List<? super Comparable & Serializable>`
Решение

«Боже, на что я трачу свою жизнь» подумала Даша и быстро нашла правильные варианты: конечно же первый, второй и третий.

Антон, щи и лимиты

Антон ограничивает количество запросов к детектору лиц на пользовательских фото следующим кодом. Как ему реализовать изменение лимита на лету потокобезопасным способом?

    class ConcurrencyLimiter {
        static final int DEFAULT_LIMIT = 10;
        final Semaphore semaphore =
                new Semaphore(DEFAULT_LIMIT);
    
        void runTask(Runnable task) {
            semaphore.acquireUninterruptibly();
            try {
                task.run();
            } finally {
                semaphore.release();
            }
        }
        
        // Implement me
    
        void setLimit(int newLimit) {
            assert newLimit > 0;
            
            // TODO: Implementation pending

        }
    }
Решение

«Многопоточность — это сложно» — в очередной раз прочитал Антон мудрость древних с плаката и сочинил вот такой код:

    // Implemented
    final AtomicInteger limit = new AtomicInteger(DEFAULT_LIMIT);
    void setLimit(int newLimit) {
        assert newLimit > 0;
        final int previous = limit.getAndSet(newLimit);
        if (newLimit >= previous) {
            semaphore.release(newLimit - previous);
        } else {
            semaphore.acquireUninterruptibly(previous - newLimit);
        }
    }

Естественно, что он не единственный верный, тут возможны различные вариации, например без CAS, но с синхронизациией всего setLimit, это не принципиально.

Но, Антон не учел, что семафор то он объявил unfair в самом начале и попытка получить сразу много пермитов выражением semaphore.acquireUninterruptibly(previous — newLimit) может никогда не завершиться, особенно если поступает очень много задач на определение лиц и в семафоре никогда не образуется достаточное количество пермитов за 1 раз.

Данную проблему Антон может решить с помощью вот такого цикла, который берет пермиты по одному:

    // Implemented
    final AtomicInteger limit = new AtomicInteger(DEFAULT_LIMIT);
    void setLimit(int newLimit) {
        assert newLimit > 0;
        final int previous = limit.getAndSet(newLimit);
        if (newLimit >= previous) {
            semaphore.release(newLimit - previous);
        } else {
            // magic goes here:
            for ( int i = 0; i < previous - newLimit; i++)
                semaphore.acquireUninterruptibly(1);
        }
    }

«А может, это не лучшее решение?» — задумался Антон, ведь «Многопоточность — это сложно» — в очередной раз прочитал Антон мудрость древних с плаката висящего над его столом…

Вот и все! Всем спасибо что приняли участие в решении наших задачек. Отдельное спасибо тем, кто написал нам свое мнение по поводу наших задачек, приходил к нам на стенд и спорил с нами о решениях!

А может вы знаете лучшие решения? Добро пожаловать в комменты!

Автор: Олег Анастасьев

Источник

Поделиться

* - обязательные к заполнению поля