Задача на собеседовании, её решение и его разбор

Привет, обычно пару раз в год я хожу на собеседования без намерения менять работу, а для получения нового опыта и в поисках актуального ответа на вопрос "А что сейчас спрашивают?"

Часто там задают обычные, даже скучные вопросы вроде "расскажите о контракте между equals()и hashCode()", но иногда попадаются очень умные и приятные интервьюеры, проводящие собеседование вдумчиво, расспрашивающие о технологиях, используемых на целевом проекте (а не об абстрактном volatile), ставящие нестандартные вопросы и задачи. Сегодняшняя статья будет об одном из таких замечательных собеседований (вернее о задаче) и о вопросах, поднятых в ходе её обсуждения.

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

Вот условие задачи:

Создать микросервис, который отдает шутки по API. Технологии: Java, Spring Boot.

Описание API:

Метод GET /jokes, его параметры: count: количество шуток (от 1 до 100), по умолчанию 5. В случае запроса более 100 шуток нужно возвращать ошибку "За один раз можно получить не более 100 шуток.".

Шутки можно получить по API: https://official-joke-api.appspot.com/random_joke (использовать только это API!) В случае запроса более одной шутки, они должны запрашиваться пачками по 10 штук параллельно (т.е. 10 штук параллельно, потом еще 10 штук параллельно и т. д.). Код должен быть покрыт тестами.

Моё решение as is доступно по ссылке https://github.com/stsypanov/demo.

Теперь воспроизведём близко к тексту его обсуждение.

Интересное началось прямо с pom.xml:

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>3.1.3</version>
        <relativePath/>
    </parent>
    <groupId>com.example</groupId>
    <artifactId>demo</artifactId>
    <version>0.0.1-SNAPSHOT</version>
    <name>demo</name>
    <description>demo</description>
<!--  ...  -->
</project>

Для создания заготовки проекта использовался spring initializr. Поэтому первый вопрос звучит так: что ещё даёт из коробки spring initializr, кроме правильной структуры папок и перечисления выбранных пользователем зависимостей?

Ответ

Spring initializr не просто добавляет в pom.xml/build.gradle зависимости (и плагины), но ещё и гармонизирует их. Таким образом, вы получаете проект без конфликтов, и приложение не свалится с NoClassDefFoundError или NoSuchBeanDefinitionException. Это вдвойне важно, если вы используете Spring Cloud.

Но вернёмся к основной теме.

Спорным моментом в этом pom.xml является наследование от spring-boot-starter-parent. В данном случае это не столь существенно, т. к. проект состоит из одного модуля, но в дальнейшем может создать проблемы. Допустим, мы решили сделать данный модуль дочерним, для этого нам нужно подвязать его к родителю, а место уже занято. Придётся переписывать <parent/> и добавлять spring-boot-dependencies в раздел <dependencyManagement/>:

<dependencyManagement>
    <dependencies>
        <dependency>
            <groupId>org.springframework.cloud</groupId>
            <artifactId>spring-cloud-dependencies</artifactId>
            <version>${spring-cloud.version}</version>
            <type>pom</type>
            <scope>import</scope>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-dependencies</artifactId>
            <version>${spring-boot.version}</version>
            <type>pom</type>
            <scope>import</scope>
        </dependency>
    </dependencies>
</dependencyManagement>

С другой стороны, при использовании spring-boot-dependencies мы лишаемся части настроек, наследуемых от spring-boot-parent, например, теперь нужно указать компилятору версию Java и прописать spring-boot.version в разделе <properties/> (при наличии их в родительском pom.xml этот шаг лишний). В рассматриваемом случае после отказа от <parent/> pom.xml стал лишь на 12 строк длиннее.

На мой взгляд использование <dependencyManagement/>выглядит более гибким, чем указание spring-boot-dependencies в качестве родителя ввиду неограниченного количества прописываемых BoM-ов (<parent/> всегда только один). В целом, вопрос дискуссионный и его обсуждение на собеседовании помогает понять, насколько глубоко соискатель разбирается в вопросах управления зависимостями, а также компоновки и сборки проекта.

Исправленную версию можно посмотреть в ветке reworked того же репозитория.

Переходим к коду.

Разбирать JokeController смысла нет, там всего 16 строк, из которых 14 – это объявление класса, метода, аннотации и т. п. Сосредоточимся на сервисном слое, представленном классом JokeProvider:

@Component
@RequiredArgsConstructor
public class JokeProvider {
  private final JokeForeignClient jokeForeignClient;
  private final ExecutorService executor = Executors.newFixedThreadPool(10);

  public List<JokeDto> getJokes(int count) {
    if (count == 0) {
      return List.of();
    }
    if (count == 1) {
      return List.of(jokeForeignClient.takeAJoke());
    }
    if (count <= 10) {
      int batchSize = Math.min(count, 10);
      return getJokesInBatch(batchSize);
    }
    List<JokeDto> jokes = new ArrayList<>();
    for (int i = count; i > 0; i -= 10) {
      int batchSize = Math.min(i, 10);
      jokes.addAll(getJokesInBatch(batchSize));
    }
    return jokes;
  }

  private List<JokeDto> getJokesInBatch(int count) {
    return IntStream.range(0, count)
            .boxed()
            .map(operand -> fetchAJoke())
            .toList()
            .stream()
            .map(this::fromFuture)
            .toList();
  }

  @SneakyThrows
  private JokeDto fromFuture(Future<JokeDto> future) {
    return future.get();
  }

  @SneakyThrows
  private Future<JokeDto> fetchAJoke() {
    return executor.submit(jokeForeignClient::takeAJoke);
  }
}

Здесь я допустил одну грубую ошибку и несколько мелких. Попробуйте найти их самостоятельно, ответ ниже.

Начнём с мелочей

Пустяк номер раз – это лишний Stream.boxed():

private List<JokeDto> getJokesInBatch(int count) {
  return IntStream.range(0, count)
          .boxed()
          .map(operand -> fetchAJoke())
          .toList()
          .stream()
          .map(this::fromFuture)
          .toList();
}

Его можно выбросить, заменив следующий за ним map() на mapToObj(). Пока "Идея" не умеет выявлять этот антипаттерн, а я его проморгал. Этот лишний IntStream.boxed() ни на что не влияет, т.к.
1) все числа ограничены 10, что укладывается в диапазон кэшируемых значений
2) компилятор наверняка обнаружит, что области видимости создаваемого Integer-а очень узкая, его значение нигде не используется, и сотрёт аллокацию.

Второе – это по очевидным причинам лишний Math.min():

if (count <= 10) {
  int batchSize = Math.min(count, 10);
  return getJokesInBatch(batchSize);
}

Этот код подсвечивается, но из-за спешки оставил как есть.

Теперь можно перейти к крупной ошибке:

Скрытый текст

private final ExecutorService executor = Executors.newFixedThreadPool(10);

Она не столь очевидна, и споткнулся я на условии задачи:

В случае запроса более одной шутки, они должны запрашиваться пачками по 10 штук параллельно (т.е. 10 штук параллельно, потом еще 10 штук параллельно и т. д.)

На первый взгляд, решение выглядит очень логичным: раз наш параллелизм ограничен 10 потоками, то возникает соблазн явно прописать их предельное количество. Однако, это заблуждение. Читаем документацию к Executors.newFixedThreadPool(int):

Creates a thread pool that reuses a fixed number of threads operating off a shared unbounded queue. At any point, at most nThreads threads will be active processing tasks. If additional tasks are submitted when all threads are active, they will wait in the queue until a thread is available. If any thread terminates due to a failure during execution prior to shutdown, a new one will take its place if needed to execute subsequent tasks. The threads in the pool will exist until it is explicitly shutdown.

Иными словами, если исполнитель о 10 потоках получает на вход ещё одну задачу и свободных потоков нет, то придётся ждать. Кажется, ничего страшного здесь нет, ведь одновременно у нас обрабатывается не более 10 запросов. Проблемы начинаются, когда к нашему АПИ обращается 2 и более клиентов. Предположим, наш контроллер получил два запроса с count = 15 (т. е. всего мы должны отдать 30 шуток), но одновременно запрашиваются только 10, остальные ждут в очереди. Конечно, запрос 1 шутки занимает немного времени и ограничение количества потоков не столь заметно. Теперь немного замедлим код

private Future<JokeDto> fetchAJoke() {
  return executor.submit(() -> {
    TimeUnit.SECONDS.sleep(2);
    return new JokeDto();
  });
}

и увеличим нагрузку (см. JokeControllerConcurrentTest в ветке reworked):

@ParameterizedTest
@ValueSource(ints = {2, 4, 6, 8})
void getJokesWithSimultaneousRequests(int simultaneousRequestCount) throws Exception {
  var latch = new CountDownLatch(1);
  var futures = new CompletableFuture<?>[simultaneousRequestCount];
  for (int i = 0; i < simultaneousRequestCount; i++) {
    futures[i] = CompletableFuture.runAsync(() -> sendRequest(latch));
  }
  latch.countDown();
  CompletableFuture.allOf(futures).get();
}

private void sendRequest(CountDownLatch latch) {
  waitOnLatch(latch);
  log.info("Sending request to server");
  var uriComponents = UriComponentsBuilder.fromHttpUrl(getHttpUrl())
          .queryParam("count", 15)
          .build();
  var stopWatch = new StopWatch();
  stopWatch.start();
  var response = restTemplate.exchange(
          uriComponents.encode().toUri(),
          HttpMethod.GET,
          HttpEntity.EMPTY,
          responseType);
  stopWatch.stop();
  log.info("Request took {} millis", stopWatch.getTotalTimeMillis());
  assertTrue(response.getStatusCode().is2xxSuccessful());
}

@SneakyThrows
private static void waitOnLatch(CountDownLatch latch) {
  latch.await();
}

Обратите внимание, что без искусственного замедления указанный тест может падать с 429 Too Many Requests, – это нормально для сервиса с защитой от DoS.

Запустив тест с исходной версией кода получаем следующую картину:

requestCount = 2
Request took 6300 millis
Request took 6300 millis

requestCount = 4
Request took 10040 millis
Request took 10041 millis
Request took 12050 millis
Request took 12050 millis

requestCount = 6
Request took 14069 millis
Request took 14070 millis
Request took 16081 millis
Request took 16081 millis
Request took 18085 millis
Request took 18085 millis

requestCount = 8
Request took 18085 millis
Request took 18085 millis
Request took 20093 millis
Request took 20093 millis
Request took 22102 millis
Request took 22103 millis
Request took 24108 millis
Request took 24107 millis

С ростом нагрузки выполнение каждого запроса замедляется пропорционально их количеству.

Решить эту проблему можно с помощью Executors.newCachedThreadPool().

Замедление при росте нагрузки сходит на нет:

requestCount = 2
Request took 4287 millis
Request took 4287 millis

requestCount = 4
Request took 4022 millis
Request took 4021 millis
Request took 4033 millis
Request took 4033 millis

requestCount = 6
Request took 4016 millis
Request took 4017 millis
Request took 4016 millis
Request took 4029 millis
Request took 4030 millis
Request took 4031 millis

requestCount = 8
Request took 4014 millis
Request took 4014 millis
Request took 4014 millis
Request took 4014 millis
Request took 4014 millis
Request took 4015 millis
Request took 4027 millis
Request took 4028 millis

Общее же время выполнения JokeControllerConcurrentTest снижается с 1 минуты до 16-17 секунд.

Смотрим документацию Executors.newCachedThreadPool():

Creates a thread pool that creates new threads as needed, but will reuse previously constructed threads when they are available. These pools will typically improve the performance of programs that execute many short-lived asynchronous tasks. Calls to execute will reuse previously constructed threads if available. If no existing thread is available, a new thread will be created and added to the pool. Threads that have not been used for sixty seconds are terminated and removed from the cache. Thus, a pool that remains idle for long enough will not consume any resources.

Для нашего сценария этот исполнитель подходит как нельзя лучше ввиду его способности расширяться/сжиматься при росте/падении нагрузки, что мы и наблюдаем в тестах.

Разумеется, и здесь есть свои подводные камни, связанные с ростом потребления памяти для создания множества потоков и эффективностью распараллеливания (ядер может не хватить на всех).

Ещё одна моя недоработка – отсутствие правильного закрытия исполнителя, что в теории может привести к потере возвращаемого дочерним потоком результата при остановке приложения. По-хорошему исполнителю нужно дать время для завершения начатого и только потом тушить контекст:

@PreDestroy
@SneakyThrows
void shutdownExecutor() {
  executor.shutdown();
  if (!executor.awaitTermination(5, TimeUnit.SECONDS)) {
    executor.shutdownNow();
  }
}

Также мне задали вопрос, какой из слоёв приложения стоит описать с помощью интерфейса.

Здесь совсем просто

Поскольку для нас важен формат получения данных, а источник вторичен (в рассмотренном случае это OpenFeign), его и нужно выделить в интерфейс. Если завтра потребуется доставать шутки из кэша или базы, то мы просто подставим другую реализацию.

И по мелочи в .gitignore стоит явно прописать /.mvn/wrapper/maven-wrapper.jar, дабы не тащить этот файл в репозиторий (всё равно он выкачивается при первой сборке проекта) и не отслеживать его изменение при обновлении версии Мавена.

На этом всё, надеюсь, из этой статьи вы почерпнули для себя что-то новое и полезное. До новых встреч!