Вы когда-нибудь задумывались, как устроены такие платформы как Codeforces и LeetCode? Как именно они компилируют и выполняют код, поступающий от множества пользователей и проверяют его в тестовых кейсах? Как определяют эффективность алгоритмов?
В этой статье мы подробно разберём, как выстроить высокоэффективную платформу для решения задач.
Исходный код к этой статье выложен на Github в этом репозитории
Спецификация
Функциональные аспекты
На нашей платформе должны гарантироваться следующие возможности:
- Поддержка множества языков программирования.
- Выполнение пользовательского кода применительно ко множеству тестовых кейсов
- Возможность возвращать верный вердикт после выполнения кода. Список вердиктов (Принято, Неверный ответ, Израсходован лимит времени, Израсходован лимит памяти, Ошибка выполнения, Ошибка компиляции).
- Возможность возвращать пользователю подробное описание ошибки в случае одного из следующих вердиктов: return a detailed error to the user if the verdict is one of these (Израсходован лимит времени, Ошибка компиляции, Ошибка выполнения, Израсходован лимит памяти).
- Возможность сообщить, сколько времени длилась компиляция.
- Возможность сообщить, сколько времени длился каждый тестовый кейс.
Нефункциональные аспекты
На нашей платформе должны гарантироваться следующие возможности:
- Возможность конкурентно выполнять сразу множество запросов
- Предоставление отдельных окружений для выполнения (вредоносный пользовательский код не должен получать доступа к хост-машине)
- Выполнение кода не допускается, если будет израсходован лимит времени.
- Для каждого запроса пользовательский код должен выполняться ровно один раз и выполняться множество раз, для каждого тестового кейса.
- Пользователь не должен иметь доступа к файловой системе хоста.
Интерфейс
Пример ввода:
{ "testCases": { "test1": { "input": "<YOUR_INPUT>", "expectedOutput": "<YOUR_EXPECTED_OUTPUT>" }, "test2": { "input": "<YOUR_INPUT>", "expectedOutput": "<YOUR_EXPECTED_OUTPUT>" }, ... }, "sourceCode": "<YOUR_SOURCE_CODE>", "language": "JAVA", "timeLimit": 15, "memoryLimit": 500 }Примеры вывода:
{ "verdict": "Accepted", "statusCode": 100, "error": "", "testCasesResult": { "test1": { "verdict": "Accepted", "verdictStatusCode": 100, "output": "0 1 2 3 4 5 6 7 8 9", "error": "", "expectedOutput": "0 1 2 3 4 5 6 7 8 9", "executionDuration": 175 }, "test2": { "verdict": "Accepted", "verdictStatusCode": 100, "output": "9 8 7 1", "error": "" , "expectedOutput": "9 8 7 1", "executionDuration": 273 }, ... }, "compilationDuration": 328, "averageExecutionDuration": 183, "timeLimit": 1500, "memoryLimit": 500, "language": "JAVA", "dateTime": "2022-01-28T23:32:02.843465" }
{ "verdict": "Runtime Error", "statusCode": 600, "error": "panic: runtime error: integer divide by zero\n\ngoroutine 1 [running]:\nmain.main()\n\t/app/main.go:11 +0x9b\n", "testCasesResult": { "test1": { "verdict": "Accepted", "verdictStatusCode": 100, "output": "0 1 2 3 4 5 6 7 8 9", "error": "", "expectedOutput": "0 1 2 3 4 5 6 7 8 9", "executionDuration": 175 }, "test2": { "verdict": "Runtime Error", "verdictStatusCode": 600, "output": "", "error": "panic: runtime error: integer divide by zero\n\ngoroutine 1 [running]:\nmain.main()\n\t/app/main.go:11 +0x9b\n" , "expectedOutput": "9 8 7 1", "executionDuration": 0 } }, "compilationDuration": 328, "averageExecutionDuration": 175, "timeLimit": 1500, "memoryLimit": 500, "language": "GO", "dateTime": "2022-01-28T23:32:02.843465" }
Реализация
Отдельные окружения для выполнения кода
Если нужно предусмотреть отдельные окружения для выполнения кода, то для этой цели можно использовать контейнеры. Концепция выглядит так: берём предоставленный пользователем исходный код и на его основе создаём образ Docker, в котором содержится информация о выполнении (лимит времени, лимит памяти, исходный код, тестовые кейсы), после чего применяем его с множеством тестовых кейсов. По коду выхода, получаемому из контейнера, можно определить результат выполнения (Принято, Неверный ответ, Израсходован лимит времени, Израсходован лимит памяти, Ошибка выполнения, Ошибка компиляции).
Некоторые достоинства работы с контейнерами.
- Изоляция: удобно изолировать приложения друг от друга, помещая их в контейнеры; при этом они также отграничиваются от хост-системы. Так можно предотвращать конфликты и повышать безопасность.
- Портируемость: в контейнер упаковываются все зависимости, необходимые для выполнения приложения. Поэтому приложение становится легко переносить между различными окружениями.
- Согласованность: поскольку в контейнер упаковываются все зависимости, необходимые для выполнения приложения, легко обеспечить согласованную работу приложения в разных окружениях.
- Масштабируемость: контейнеры легко масштабируются, как в сторону наращивания, так и в сторону свёртывания, в зависимости от изменения потребности. Поэтому при работе с контейнерами легко управлять ресурсами и гарантировать, что приложение всегда будет работать на оптимальном уровне производительности.
- Эффективное использование ресурсов: при использовании контейнеров можно снизить затраты на эксплуатацию и поддержку приложений, поскольку они легковесны и требуют не так много ресурсов, как традиционные виртуальные машины.
- Гибкость: контейнеры легко развёртываются и на предприятии, и в облаке, и в гибридных окружениях.
Как показано на иллюстрации выше, нам потребуются контейнеры двух типов: контейнеры для компиляции и контейнеры для выполнения. При каждом запросе будет создаваться контейнер одного из этих типов. Затем будет создаваться один экземпляр контейнера для компиляции и по одному экземпляру контейнеров для выполнения на каждый интересующий нас тестовый кейс.
Контейнеры для компиляции
Контейнеры такого типа используются для компиляции исходного кода в двоичный. Эти контейнеры очень специфические, поскольку они используют том совместно с главным сервисом.
Пример:
FROM openjdk:11.0.6-jdk-slim WORKDIR /app ENTRYPOINT ["/bin/sh", "-c", "javac -d $EXECUTION_PATH $EXECUTION_PATH/$SOURCE_CODE_FILE_NAME && rm $EXECUTION_PATH/$SOURCE_CODE_FILE_NAME"]
Контейнеры для выполнения
В контейнерах такого типа содержится вся информация о выполнении, причём, такой контейнер выполняется отдельно для каждого тестового кейса. Кроме того, этот контейнер изолирован (не разделяет том ни с одним другим контейнером или приложением).
Пример:
FROM openjdk:11.0.6-jre-slim WORKDIR /app USER root RUN groupadd -r user -g 111 && \ useradd -u 111 -r -g user -s /sbin/nologin -c "Docker image user" user ADD . . RUN chmod a+x ./entrypoint-*.sh USER user ENTRYPOINT ["/bin/sh", "-c", "./entrypoint-$TEST_CASE_ID.sh"]Как упоминалось в файле Dockerfile, файл входной точки (entrypoint) в каждый контейнер снабжён префиксом TEST_CASE_ID, он генерируется приложением по шаблону для каждого тестового кейса.
#!/usr/bin/env bash ulimit -s [(${compiler.memoryLimit})] timeout -s SIGTERM [(${compiler.timeLimit})] [(${compiler.executionCommand})] exit $? В шаблоне указывается лимит времени и лимит памяти, допустимый для каждого тестового кейса.
Политика безопасности
По соображениям безопасности и для того, чтобы закрыть пользователю доступ к файловой системе, можно применять политики безопасности.
В Java действуют политики безопасности, применяемые для контроля над системными ресурсами, в частности, над файлами и сетевыми ресурсами, используемыми в приложениях. Диспетчер безопасности Java обеспечивает соблюдение этих политик. Этот диспетчер можно сконфигурировать так, чтобы он предоставлял или отменял права доступа к конкретному коду в зависимости от его происхождения. Ориентироваться можно, например, на расположение кода в файловой системе или на его цифровую подпись.
grant { permission java.io.FilePermission "/tmp/test.txt", "read,write"; permission java.net.SocketPermission "www.example.com:80", "connect"; };Вышеприведённую политику можно задать как аргумент командной строки, приступая к работе с JVM, вот так:
java -Djava.security.policy=mypolicy.policy MyApp
Пользовательский запрос
Пользовательский ввод будет выглядеть так:
@Getter @NoArgsConstructor @EqualsAndHashCode @AllArgsConstructor public class Request { /** * The Source code. */ @ApiModelProperty(notes = "The sourcecode") @NonNull @JsonProperty("sourcecode") protected String sourcecode; /** * The Language. */ @ApiModelProperty(notes = "The programming language") @NonNull @JsonProperty("language") protected Language language; /** * The Time limit. */ @ApiModelProperty(notes = "The time limit in sec") @NonNull @JsonProperty("timeLimit") protected int timeLimit; /** * The Memory limit. */ @ApiModelProperty(notes = "The memory limit") @NonNull @JsonProperty("memoryLimit") protected int memoryLimit; /** * The Test cases. */ @ApiModelProperty(notes = "The test cases") @NonNull @JsonProperty("testCases") protected LinkedHashMap<String, TestCase> testCases; // Note: test cases should be given in order }По каждому тестовому кейсу нам известен ввод и ожидаемый вывод:
@Getter @AllArgsConstructor @EqualsAndHashCode public class TestCase { @ApiModelProperty(notes = "The input, can be null") @JsonProperty("input") private String input; @ApiModelProperty(notes = "The expected output, can not be null") @NonNull @JsonProperty("expectedOutput") private String expectedOutput; }
Стратегия компиляции
Ниже приведён пример кода, демонстрирующий, как обычно выполняется компиляция. Можно воспользоваться паттерном «стратегия», чтобы выбрать, какой алгоритм будет использоваться с компилируемыми языками, а какой — с интерпретируемыми.
@Override public CompilationResponse compile(Execution execution) { // repository name must be lowercase String compilationImageName = IMAGE_PREFIX_NAME + execution.getLanguage().toString().toLowerCase(); // If the app is running inside a container, we should share the same volume with the compilation container. final String volume = compilationContainerVolume.isEmpty() ? System.getProperty("user.dir") : compilationContainerVolume; String sourceCodeFileName = execution.getSourceCodeFile().getOriginalFilename(); String containerName = COMPILATION_CONTAINER_NAME_PREFIX + execution.getImageName(); var processOutput = new AtomicReference<ProcessOutput>(); compilationTimer.record(() -> { processOutput.set( compile(volume, compilationImageName, containerName, execution.getPath(), sourceCodeFileName) ); }); ProcessOutput compilationOutput = processOutput.get(); int compilationDuration = compilationOutput.getExecutionDuration(); ContainerInfo containerInfo = containerService.inspect(containerName); ContainerHelper.logContainerInfo(containerName, containerInfo); Verdict verdict = getVerdict(compilationOutput); compilationDuration = ContainerHelper.getExecutionDuration( containerInfo == null ? null : containerInfo.getStartTime(), containerInfo == null ? null : containerInfo.getEndTime(), compilationDuration); ContainerHelper.deleteContainer(containerName, containerService, threadPool); return CompilationResponse .builder() .verdict(verdict) .error(compilationOutput.getStdErr()) .compilationDuration(compilationDuration) .build(); }
Стратегия выполнения
Вот фрагмент кода, демонстрирующий, как построено выполнение кода в контейнере.
public ExecutionResponse run(Execution execution, boolean deleteImageAfterExecution) { buildContainerImage(execution); var testCasesResult = new LinkedHashMap<String, TestCaseResult>(); Verdict verdict = null; String err = ""; for (ConvertedTestCase testCase : execution.getTestCases()) { TestCaseResult testCaseResult = executeTestCase(execution, testCase); testCasesResult.put(testCase.getTestCaseId(), testCaseResult); verdict = testCaseResult.getVerdict(); log.info("Status response for the test case {} is {}", testCase.getTestCaseId(), verdict.getStatusResponse()); // Update metrics verdictsCounters.get(verdict.getStatusResponse()).increment(); if (verdict != Verdict.ACCEPTED) { // Don't continue if the current test case failed log.info("Test case id: {} failed, abort executions", testCase.getTestCaseId()); err = testCaseResult.getError(); break; } } // Delete container image asynchronously if (deleteImageAfterExecution) { ContainerHelper.deleteImage(execution.getImageName(), containerService, threadPool); } return ExecutionResponse .builder() .verdict(verdict) .testCasesResult(testCasesResult) .error(err) .build(); }
private TestCaseResult executeTestCase(Execution execution, ConvertedTestCase testCase) { log.info("Start running test case id = {}", testCase.getTestCaseId()); String expectedOutput = testCase.getExpectedOutput(); // Free memory space testCase.freeMemorySpace(); var result = new AtomicReference<TestCaseResult>(); executionTimer.record(() -> { // Run the execution container result.set(runContainer(execution, testCase.getTestCaseId(), expectedOutput)); }); TestCaseResult testCaseResult = result.get(); return testCaseResult; }В каждом языке программирования предусмотрены собственные параметры выполнения и конкретная конфигурация. Чтобы это абстрагировать, можно воспользоваться принципом инверсии зависимостей и создавать классы Execution при помощи паттерна абстрактная фабрика.
Абстрактная фабрика
Абстрактная фабрика — это паттерн проектирования, позволяющий создавать семейства родственных или зависимых объектов, не указывая конкретные классы. С его помощью создаются объекты, относящиеся к одному семейству, но не предназначенные для совместного использования.
@FunctionalInterface public interface AbstractExecutionFactory { /** * Create execution. * * @param sourceCode the source code * @param testCases the test cases * @param timeLimit the time limit * @param memoryLimit the memory limit * @return the execution */ Execution createExecution(MultipartFile sourceCode, List<ConvertedTestCase> testCases, int timeLimit, int memoryLimit); }
public abstract class ExecutionFactory { private static Map<Language, ExecutionType> registeredExecutionTypes = new EnumMap<>(Language.class); private static Map<Language, AbstractExecutionFactory> registeredFactories = new EnumMap<>(Language.class); private ExecutionFactory() {} /** * Register. * * @param language the language * @param factory the factory */ public static void registerExecution(Language language, AbstractExecutionFactory factory) { registeredFactories.putIfAbsent(language, factory); } /** * Register execution type. * * @param language the language * @param executionType the execution type */ public static void registerExecutionType(Language language, ExecutionType executionType) { registeredExecutionTypes.putIfAbsent(language, executionType); } /** * Gets execution type. * * @param language the language * @return the execution type */ public static ExecutionType getExecutionType(Language language) { return registeredExecutionTypes.get(language); } /** * Gets registered factories. * * @return the registered factories */ public static Set<Language> getRegisteredFactories() { return registeredFactories .keySet() .stream() .collect(Collectors.toSet()); } /** * Gets execution. * * @param sourceCode the source code * @param testCases the test cases * @param timeLimit the time limit * @param memoryLimit the memory limit * @param language the language * @return the execution */ public static Execution createExecution(MultipartFile sourceCode, List<ConvertedTestCase> testCases, int timeLimit, int memoryLimit, Language language) { AbstractExecutionFactory factory = registeredFactories.get(language); if (factory == null) { throw new FactoryNotFoundException("No ExecutionFactory registered for the language " + language); } return factory.createExecution( sourceCode, testCases, timeLimit, memoryLimit); } }All languages can be registered in a config class.
private void configureLanguages() { // Register factories register(Language.JAVA, (sourceCode, testCases, timeLimit, memoryLimit) -> new JavaExecution( sourceCode, testCases, timeLimit, memoryLimit, ExecutionFactory.getExecutionType(Language.JAVA))); register(Language.PYTHON, (sourceCode, testCases, timeLimit, memoryLimit) -> new PythonExecution( sourceCode, testCases, timeLimit, memoryLimit, ExecutionFactory.getExecutionType(Language.PYTHON))); ...Подробнее о классе Execution и о том, как он создаёт среду выполнения, рассказано в разделе Execution class
Как рассчитать длительность компиляции и выполнения
В данном случае можно воспользоваться командой inspect из docker, чтобы получить подробную информацию о контейнере (дата создния, жата начала выполнения, дата окончания выполнения, статус выхода…).
Docker Inspect
Можно воспользоваться командой docker inspect, указав в качестве аргумента ID образа или контейнера, либо имя образа.
Например, чтобы проверить контейнер под именем «my_container», нужно выполнить следующую команду:
docker inspect my_containerТакже можно воспользоваться опцией —format, чтобы отображать только конкретные иоля или чтобы отформатировать вывод конкретным образом.
docker inspect --format='{{json .Config}}' my_containerПодробнее см. в полном исходном коде приложения.
Какие ещё вещи есть в базе кода
- Helm-диаграммы для развёртывания сервиса в Kubernetes здесь
- Предоставление инфраструктуры в Azure при помощи ARM-шаблона
- Локальное выполнение при помощи docker-compose, в частности, коммуникация между RabbitMq и ApacheKafka здесь
Заключение
Создать платформу для решения задач бывает очень непросто. Но, если пользоваться контейнерами, то этот процесс становится гораздо более управляемым. Учитывая, сколько достоинств у контейнеров (изоляция, переносимость, согласованность, масштабируемость, экономичность), не составляет труда увидеть, почему они отлично подходят для выстраивания мощной платформы, на которой пользователи решают задачи. Итак, кто бы вы ни были — программист-энтузиаст, желающий отточить свои навыки, либо представитель бизнеса, изыскивающий возможность улучшить процессы, не сомневайтесь, попробуйте контейнеры. Вам понравится! Помните, что «работа с контейнерами — всё равно, что сборка кода из лего». Поэтому удачи вам в программировании платформы для решения задач. Здесь открываются просто безграничные возможности.
P.S Обращаем ваше внимание на то, что у нас на сайте проходит распродажа.
ссылка на оригинал статьи https://habr.com/ru/articles/831704/
Добавить комментарий