Интересные решения с HighLoad Cup

В августе 2017 года Mail.Ru Group провёл чемпионат для backend-разработчиков HighLoad Cup. Суть конкурса проста: используя любой стек технологий написать как можно более производительное приложение под ограниченные серверные ресурсы обрабатывающее заранее определённый набор запросов и упаковать его в docker контейнер. Естественно, в лидерах оказались решения на C/C++, Java, GoLang. Что удивительно, PHP стек оказался производительнее NodeJS и Python решений.

Условия конкурса можно разделить на 2 задачи: быстрый веб-сервер и высокопроизводительное хранилище данных, желательно в оперативке. Будет очень хорошо, если вы предварительно ознакомитесь с условиями конкурса и вариантами решения, в данном обзоре я их не упоминаю.

Бинарно-упакованные данные в RAM

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

<?php

ini_set("memory_limit","256M");


define('BLOCK_LENGTH', 13);

echo 'memory: ' . intval(memory_get_usage() / (1024*1204)) . "\n";

// fill 11 heaps with zeros
// 1 heap stores 1M visits (1 visit is 13 bytes, 1M visits - 13MB)
$heaps = [
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000),
    str_repeat(pack('LLLc', 0, 0, 0, 0), 1000000)
];

echo 'memory: ' . intval(memory_get_usage() / (1024*1204)) . "\n";

$i = 1;
while($visitsData = @file_get_contents("visits_$i.json")) {
    $visitsData = json_decode($visitsData, true);

    foreach ($visitsData['visits'] as $k => $row) {
        $id = $row['id'];
        $heapIndex = intval(floor($id / 1000000));
        $startPosition = ($id - 1) * BLOCK_LENGTH;

        $data = pack('LLLc',
            $row['user'],
            $row['location'],
            $row['visited_at'],
            $row['mark']
        );

        for ($t = 0; $t < strlen($data); $t++) {
            $heaps[$heapIndex][$startPosition + $t] = $data[$t];
        }

    }

    echo "$i\n";
    $i++;
}

unset($visitsData);
gc_collect_cycles();

echo 'memory: ' . intval(memory_get_usage() / (1024*1204)) . "\n";

/**
 * Get visitor by id
 *
 * @param string[] $heaps
 * @param int $id
 * @return array
 */
function read_from_heap($heaps, $id) {
    $heapIndex = intval(floor($id / 1000000));
    $startPosition = $id - $heapIndex * 1000000;
    $data = substr($heaps[$heapIndex], ($startPosition-1) * BLOCK_LENGTH, BLOCK_LENGTH);
    var_dump(bin2hex($data) );
    return unpack('Luser/Llocation/Lvisited_at/cmark', $data);
}



var_dump( read_from_heap($heaps, 1) );
var_dump( read_from_heap($heaps, 2) );
var_dump( read_from_heap($heaps, 99999) );
var_dump( read_from_heap($heaps, 100000) );
var_dump( read_from_heap($heaps, 100001) );

Скорость чтения и декодирования одной записи из такого справочника без нагрузки варьируется от 0.000002 до 0.000012 секунды. Для сравнения, скорость чтения и декодирования из APCu (apcu_add + apcu_fetch) находится в пределах 0.000002 — 0.000004, однако, не гарантирует хранения данных т.к. является кэшем. А Memcached по TCP выдаёт вообще 0.000012 — 0.000037. Скорость работы подобного решения под нагрузкой — тема для отдельной статьи.

Данный способ хранения отлично подходит для массива данных с записями фиксированной длины и подряд идущими идентификаторами, иначе эффективность такой структуры будет падать. Главный профит подобного хранения — отсутствие оверхедов структур данных на хранения мета-информации, например ключей, а так же огромный оверхед на zval.

Хранение оригинального справочника визитов в PHP-массивах занимало бы в памяти от 2 790 Мб до 5 510 Мб, в зависимости от формата, а оптимизации с помощью SplFixedArray снижают потребление до 704 Мб. Бинарный же вариант хранения потребляет всего 116 Мб.

Оптимизация веб-сервера и сети

Не менее удивительной оказалась идея написания web-сервера, который обрабатывает только необходимый минимум заголовков для выполнения условий конкурса, игнорируя всё, что ни на что не влияет.

Другим интересным решением оказался тюнинг сети, а именно TCP_NODELAY, TCP_DEFER_ACCEPT, TCP_QUICKACK, SO_SNDBUF и SO_RCVBUF. Однако, это уже не про PHP, а, например, про nginx.

Материалов по конкурсу огромное количество и изучение их того стоит!

Ссылки по теме:

  1. Новый чемпионат для backend-разработчиков: HighLoad Cup
  2. Документация к первому, пилотному чемпионату highloadcup
  3. Телеграм-чат в котором до сих пор идут обсуждения
  4. По следам highloadcup: swoole vs workerman, splfixedarray vs array
  5. Как написать хорошее решение для Highload Cup
  6. Мои 5 копеек про Highload Cup 2017 или история 9го места
  7. Список репозиториев с решениями на github

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *