Вступление
Итак начнём с футболки. Своё решение нужно было написать до первого сентября, а я дописал только шестого.
Первого сентября были подведены итоги, места распределены, всем кто уложился в тысячу секунд пообещали футболки. После этого организаторы позволили ещё неделю улучшать свои решения, но уже без призов. Этим временем я и воспользовался, чтобы переписать своё решение (на самом деле мне не хватило всего пару вечеров). Собственно футболка мне не положена, а жаль :(
Во время своей предыдущей статьи я сравнивал библиотеки на php для создания вебсокет-сервера тогда мне порекомендовали библиотеку swoole — она написана на C++ и устанавливается из pecl. К слову сказать, все эти библиотеки могут использоваться не только для создания вебсокет сервера, но подходят и просто для http-сервера. Этим я и решил воспользоваться.
Я взял библиотеку swoole, создал базу данных sqlite в памяти и сразу поднялся в первую двадцатку с результатом 159 секунд, потом меня сместили, я добавил кеш и уменьшил время до 79 секунд, попал назад в двадцатку, меня сместили, переписал с sqlite на swoole_table и уменьшил время до 47 секунд. Конечно до первых мест мне было далеко, но мне удалось обойти в таблице моих нескольких знакомых с решением на Go.
Так выглядит старая рейтинговая таблица сейчас:
Немного похвалы для Mail.Ru и можно идти дальше.
Благодаря этому замечательному чемпионату я более близко познакомился с библиотеками swoole, workerman, научился лучше оптимизировать php под высокие нагрузки, научился использовать yandex tank и многое другое. Продолжайте устраивать такие чемпионаты, соревновательность подстёгивает к изучению новой информации и прокачке навыков.
php vs node.js vs go
Для начала я взял swool, потому что он написан C++ и однозначно должен работать быстрее workerman, который написан на php.
Я написал hello world код:
$server = new Swoole\Http\Server('0.0.0.0', 1080);
$server->set(['worker_num' => 1,]);
$server->on('Request', function($req, $res) {$res->end('hello world');});
$server->start();
Запустил линуксовую консольную утилиту Apache Benchmark, которая делает 10к запросов в 10 потоков:
ab -c 10 -n 10000 http://127.0.0.1:1080/
и получил время ответа 0.17 ms
После этого написал пример на workerman:
require_once DIR . '/vendor/autoload.php';
use Workerman\Worker;
$http_worker = new Worker("http://0.0.0.0:1080");
$http_worker->count = 1;
$http_worker->onMessage = function($conn, $data) {$conn->send("hello world");};
Worker::runAll();
и получил 0.43 ms, т.е. результат в 3 раза хуже.
Но я не сдавался, установил библиотеку event:
pecl install event
добавил в код:Worker::$eventLoopClass = '\Workerman\Events\Ev';
require_once DIR . '/vendor/autoload.php';
use Workerman\Worker;
Worker::$eventLoopClass = '\Workerman\Events\Ev';
$http_worker = new Worker("http://0.0.0.0:1080");
$http_worker->count = 1;
$http_worker->onMessage = function($conn, $data) {$conn->send("hello world");};
Worker::runAll();
Измерения показали 0.11 ms, т.е. workerman написанный на php и использующий libevent стал работать быстрее чем swoole написанный на C++. Я с помощью гуглтранслейта прочитал тонны документации на китайском. Но ничего не нашёл. К слову сказать обе библиотеки написаны китайцами и комментарии на китайском в коде библиотек для них — …
Теперь я понимаю, что чувствовали китайцы, когда читали мой код.
Я завёл тикет на гитхабе swoole с вопросом как такое может происходить.
Там мне порекомендовали использовать:
$serv = new Swoole\Http\Server('0.0.0.0', 1080, SWOOLE_BASE);
вместо:
$serv = new Swoole\Http\Server('0.0.0.0', 1080);
$serv = new Swoole\Http\Server('0.0.0.0', 1080, SWOOLE_BASE);
$serv->set(['worker_num' => 1,]);
$serv->on('Request', function($req, $res) {$res->end('hello world');});
$serv->start();
Я воспользовался их советом и получил 0.10 ms, т.е. чуть-чуть быстрее чем workerman.
На этот момент у меня уже было готовое приложение на php, которое я уже не знал как оптимизировать, оно отвечало за 0.12 ms и решил переписать приложение на что-нибудь другое.
Попробовал node.js:
const http = require('http');
const server = http.createServer(function(req, res) {
res.writeHead(200);
res.end('hello world');
});
server.listen(1080);
получил 0.15 ms, т.е. на 0.03 ms меньше чем моё готовое приложение на php
Взял fasthttp на go и получил 0.08 ms:
package main
import (
"flag"
"fmt"
"log"
"github.com/valyala/fasthttp"
)
var (
addr = flag.String("addr", ":1080", "TCP address to listen to")
compress = flag.Bool("compress", false, "Whether to enable transparent response compression")
)
func main() {
flag.Parse()
h := requestHandler
if *compress {
h = fasthttp.CompressHandler(h)
}
if err := fasthttp.ListenAndServe(*addr, h); err != nil {
log.Fatalf("Error in ListenAndServe: %s", err)
}
}
func requestHandler(ctx *fasthttp.RequestCtx) {
fmt.Fprintf(ctx, "Hello, world!")
}
Итоговая таблица:
splfixedarray vs array
За неделю до окончания конкурса условия немного усложнили:
- объём данных увеличили в 10 раз
- количество запросов в секунду увеличили в 10 раз
Структура данных, которые нужно хранить — это 3 таблицы: users (1kk), locations (1kk) и visits (11kk).
User (Профиль):
id — уникальный внешний идентификатор пользователя. Устанавливается тестирующей системой и используется для проверки ответов сервера. 32-разрядное целое беззнаковое число.
email — адрес электронной почты пользователя. Тип — unicode-строка длиной до 100 символов. Уникальное поле.
first_name и last_name — имя и фамилия соответственно. Тип — unicode-строки длиной до 50 символов.
gender — unicode-строка m означает мужской пол, а f — женский.
birth_date — дата рождения, записанная как число секунд от начала UNIX-эпохи по UTC (другими словами — это timestamp).
Location (Достопримечательность):
id — уникальный внешний id достопримечательности. Устанавливается тестирующей системой. 32-разрядное целое беззнаковоее число.
place — описание достопримечательности. Текстовое поле неограниченной длины.
country — название страны расположения. unicode-строка длиной до 50 символов.
city — название города расположения. unicode-строка длиной до 50 символов.
distance — расстояние от города по прямой в километрах. 32-разрядное целое беззнаковое число.
Visit (Посещение):
id — уникальный внешний id посещения. 32-разрядное целое беззнакое число.
location — id достопримечательности. 32-разрядное целое беззнаковое число.
user — id путешественника. 32-разрядное целое беззнаковое число.
visited_at — дата посещения, timestamp.
mark — оценка посещения от 0 до 5 включительно. Целое число.
Моё решение перестало укладываться в выделенные для него 4Гб. Пришлось искать варианты.
Для начала мне нужно было залить в память из json-файлов 11 миллионов записей.
Попробовал swoole_table, замерил потребление памяти — 2200 Мб
$visits = new swoole_table(11000000);
$visits->column('id', swoole_table::TYPE_INT);
$visits->column('user', swoole_table::TYPE_INT);
$visits->column('location', swoole_table::TYPE_INT);
$visits->column('mark', swoole_table::TYPE_INT);
$visits->column('visited_at', swoole_table::TYPE_INT);
$visits->create();
$i = 1;
while ($visitsData = @file_get_contents("data/visits_$i.json")) {
$visitsData = json_decode($visitsData, true);
foreach ($visitsData['visits'] as $k => $row) {
$visits->set($row['id'], $row);
}
$i++;
}
unset($visitsData);
gc_collect_cycles();
echo 'memory: ' . intval(memory_get_usage() / 1000000) . "\n";
Попробовал ассоциативный массив, потребление памяти сильно больше — 6057 Мб
$visits = [];
$i = 1;
while ($visitsData = @file_get_contents("data/visits_$i.json")) {
$visitsData = json_decode($visitsData, true);
foreach ($visitsData['visits'] as $k => $row) {
$visits[$row['id']] = $row;
}
$i++;echo "$i\n";
}
unset($visitsData);
gc_collect_cycles();
echo 'memory: ' . intval(memory_get_usage() / 1000000) . "\n";
Попробовал SplFixedArray, потребление памяти немого меньше, чем у обычного массива — 5696 Мб
$visits = new SplFixedArray(11000000);
$i = 1;
while ($visitsData = @file_get_contents("data/visits_$i.json")) {
$visitsData = json_decode($visitsData, true);
foreach ($visitsData['visits'] as $k => $row) {
$visits[$row['id']] = $row;
}
$i++;echo "$i\n";
}
unset($visitsData);
gc_collect_cycles();
echo 'memory: ' . intval(memory_get_usage() / 1000000) . "\n";
Решил отдельные свойства визита сохранять в отельные массивы, потому что текстовые ключи могут занимать в памяти много места, т.е. изменил такой код:
$visits[1] = ['user' => 153, 'location' => 17, 'mark' => 5, 'visited_at' => 1503695452];
на такой:
$visits_user[1] = 153;
$visits_location[1] = 17;
$visits_mark[1] = 5;
$visits_visited_at[1] => 1503695452;
потребление памяти при разбивке трёхмерного массива на двумерные составило — 2147 Мб, т.е. в 3 раза меньше. Т.о. имена ключей в трёхмерном массиве съедали 2/3 от всей занимаемой им памяти.
$user = $location = $mark = $visited_at = [];
$i = 1;
while ($visitsData = @file_get_contents("data/visits_$i.json")) {
$visitsData = json_decode($visitsData, true);
foreach ($visitsData['visits'] as $k => $row) {
$user[$row['id']] = $row['user'];
$location[$row['id']] = $row['location'];
$mark[$row['id']] = $row['mark'];
$visited_at[$row['id']] = $row['visited_at'];
}
$i++;echo "$i\n";
}
unset($visitsData);
gc_collect_cycles();
echo 'memory: ' . intval(memory_get_usage() / 1000000) . "\n";
Решил использовать разбиение трёхмерного массива совместно с SplFixedArray и потребление памяти упало ещё в 3 раза составив 704 МБ
$user = new SplFixedArray(11000000);
$location = new SplFixedArray(11000000);
$mark = new SplFixedArray(11000000);
$visited_at = new SplFixedArray(11000000);
$user_visits = [];
$location_visits = [];
$i = 1;
while ($visitsData = @file_get_contents("data/visits_$i.json")) {
$visitsData = json_decode($visitsData, true);
foreach ($visitsData['visits'] as $k => $row) {
$user[$row['id']] = $row['user'];
$location[$row['id']] = $row['location'];
$mark[$row['id']] = $row['mark'];
$visited_at[$row['id']] = $row['visited_at'];
if (isset($user_visits[$row['user']])) {
$user_visits[$row['user']][] = $row['id'];
} else {
$user_visits[$row['user']] = [$row['id']];
}
if (isset($location_visits[$row['location']])) {
$location_visits[$row['location']][] = $row['id'];
} else {
$location_visits[$row['location']] = [$row['id']];
}
}
$i++;echo "$i\n";
}
unset($visitsData);
gc_collect_cycles();
echo 'memory: ' . intval(memory_get_usage() / 1000000) . "\n";
Ради интереса попробовал тоже самое на node.js и получил 780 Мб
const fs = require('fs');
global.visits = []; global.users_visits = []; global.locations_visits = [];
let i = 1; let visitsData;
while (fs.existsSync(`data/visits_${i}.json`) && (visitsData = JSON.parse(fs.readFileSync(`data/visits_${i}.json`, 'utf8')))) {
for (y = 0; y < visitsData.visits.length; y++) {
//visits[visitsData.visits[y]['id']] = visitsData.visits[y];
visits[visitsData.visits[y]['id']] = {
user:visitsData.visits[y].user,
location:visitsData.visits[y].location,
mark:visitsData.visits[y].mark,
visited_at:visitsData.visits[y].visited_at,
//id:visitsData.visits[y].id,
};
}
i++;
}
global.gc();
console.log("memory usage: " + parseInt(process.memoryUsage().heapTotal/1000000));
Итоговая таблица:
Хотел попробовать apc_cache и redis, но у них ещё дополнительно память тратится на хранения имён ключей. В реальной жизни можно использовать, но для этого чемпионата вообще не вариант.
Послесловие
После всех оптимизаций общее время составило 557 секунд, что в 4 раза медленнее, чем первое место.
Ещё раз спасибо организаторам, которые не спали по ночам, перезагружали зависшие контейнеры, фиксили баги, допиливали сайт, отвечали в телеграмме на вопросы.
Другая моя сегодняшняя статья на Хабре: бесплатный сервер в облаке
Комментарии (30)
akzhan
07.09.2017 05:08+4Сразу по обьявлению конкурса понял, что этот этап соревнования не вполне четко описан и не совсем highload.
Понятно, что нужна in-memory db и относительно быстрый event loop.
Написал от балды сервер на Crystal (просто прямолинейно, с хэшами вместо массивов и без индексов). И результат мне лично понравился, хоть и далеко… Настроения адаптировать код под конкретную нагрузку не было, зато код читаем :)
https://github.com/akzhan/highload-cup-1/blob/master/src/cup1.cr
akzhan
07.09.2017 05:14+3попутно добавили в Crystal поддержку проверки на отсутствие ключа в объекте JSON/YAML, что позволит в будущем упростить код и избавиться от on_presence/on_absence.
jehy
07.09.2017 09:07Непонятно, как именно запускались проекты, так что уточню — нода у вас была в один поток, как все обычно делают на подобных бенчмарках?
morozovsk Автор
07.09.2017 09:49да у меня был один поток, но он не держит нагрузку от рейтингового обстрела и нужно переписывать на node claster.
jehy
07.09.2017 10:27+1Ну таки сразу нужно было это делать, без многопоточности сравнивать как-то странно. Насколько я помню, тот же Go по умолчанию использует количество потоков по числу CPU.
(промазал, комментарий к ответу выше).morozovsk Автор
07.09.2017 10:37Моё решение делалось по предыдущие условия конкурса, тогда один поток был эффективнее, тогда в топе были решения на одном потоке. у меня процесс ел не больше 1% процессора, разбивать на два — только дополнительные расходы.
А вот уже после того как поменяли условия и 1 процесс был загружен на 100% и не справлялся, вот тогда уже стала необходимость распараллеливать нагрузку. Но я сначала решил сделать это на php, до node.js ещё просто руки не дошли.jehy
07.09.2017 10:42+1Будет здорово, если попробуете — интересно, пока не видел внятных бенчмарков с кластером.
morozovsk Автор
07.09.2017 10:58сейчас в рейтинге уже есть решение на cluster, оно набрало 8843 секунд. Не уверен, что напишу лучше. Я не большой специалист в node.js — я писал всего три приложения (включая это).
coh
07.09.2017 17:10Решил использовать разбиение трёхмерного массива совместно с SplFixedArray и потребление памяти упало ещё в 3 раза составив 704 МБ
Не понял почему вы не стали хранить данные в формате типа:
$visits[$row['id']] = [ $row['user'], $row['location'], $row['visited_at'], $row['mark'], ];
заняло бы еще меньше на PHP 7 точноmorozovsk Автор
07.09.2017 17:45+1$visits = new SplFixedArray(11000000); $i = 1; while ($visitsData = @file_get_contents("data/visits_$i.json")) { $visitsData = json_decode($visitsData, true); foreach ($visitsData['visits'] as $k => $row) { $visits[$row['id']] = [$row['user'], $row['location'], $row['visited_at'], $row['mark'], ]; } $i++;echo "$i\n"; } unset($visitsData); gc_collect_cycles(); echo 'memory: ' . intval(memory_get_usage() / 1000000) . "\n";
ваш вариант — 3936 Мб, php7 если чтоcoh
07.09.2017 17:51Внутри тоже можно использовать fixed.
Теперь понял, вы убрали оверхэд на создание мелкого массива свойств вовсе.morozovsk Автор
07.09.2017 18:13ваш вариант 2790 Мб:
$visits = new SplFixedArray(11000000); $i = 1; while ($visitsData = @file_get_contents("data/visits_$i.json")) { $visitsData = json_decode($visitsData, true); foreach ($visitsData['visits'] as $k => $row) { $visits[$row['id']] = new SplFixedArray(4); $visits[$row['id']][0] = $row['user']; $visits[$row['id']][1] = $row['location']; $visits[$row['id']][2] = $row['visited_at']; $visits[$row['id']][3] = $row['mark']; } $i++;echo "$i\n"; } unset($visitsData); gc_collect_cycles(); echo 'memory: ' . intval(memory_get_usage() / 1000000) . "\n";
вариант с объектом 5510 Мб:
class MyArray { public $user; public $location; public $visited_at; public $mark; public function __construct($user, $location, $visited_at, $mark) { $this->user = $user; $this->location = $location; $this->visited_at = $visited_at; $this->$mark = $mark; } } $visits = new SplFixedArray(11000000); $i = 1; while ($visitsData = @file_get_contents("data/visits_$i.json")) { $visitsData = json_decode($visitsData, true); foreach ($visitsData['visits'] as $k => $row) { $visits[$row['id']] = new MyArray( $row['user'], $row['location'], $row['visited_at'], $row['mark'] ); } $i++;echo "$i\n"; } unset($visitsData); gc_collect_cycles(); echo 'memory: ' . intval(memory_get_usage() / 1000000) . "\n";
coh
07.09.2017 18:19Спасибо за статью, интересная тема оказалось.
Для себя понял, что видимо индексированные массивы всетаки не до конца оптимизировали в 7ке по сравнению с fixed.
bashkarev
07.09.2017 23:05+1У вас в конструкторе $this->$mark ошибка, довольно странно что объекты заняли настолько много.
Вот твит Никиты Попова по этому поводуmorozovsk Автор
07.09.2017 23:18спасибо, исправил опечатку, результат 1430 Мб
Я собственно почему и решил попробовать вариант с классом, потому что раньше на конференции слышал, что они эффективнее работают чем массивы. Так и есть, в текущей таблице меньше класса ест память только SplFixedArray, правда разница аж в два раза.
Сейчас попробовал разбить объект на отдельные массивы в node.js там тоже стало памяти меньше занимать.
maksimmysak
07.09.2017 23:07А почему не пробовали вариант с golang?
morozovsk Автор
07.09.2017 23:08в разделе «php vs node.js vs go» я пробовал fasthttp, который написан на golang
balloon
08.09.2017 11:45+1Еще можно хранить данные в бинарном виде. Это сэкономит кучу памяти, которая используются php на хранение переменных. В итоге 1 visit — это 13 байт, 11M visits — 143MB.
define('BLOCK_LENGTH', 13); // 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() / 1000000) . "\n"; $i = 1; while ($visitsData = @file_get_contents("data/visits_$i.json")) { $visitsData = json_decode($visitsData, true); foreach ($visitsData as $k => $row) { $id = $row['id']; $heapIndex = intval(floor($id / 1000000)); $startPosition = $id - $heapIndex * 1000000; $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() / 1000000) . "\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 * BLOCK_LENGTH, BLOCK_LENGTH); return unpack('Luser/Llocation/Lvisited_at/cmark', $data); }
morozovsk Автор
08.09.2017 12:27Очень ценный комментарий, большое вам спасибо.
Я думал делать как в вашем коде, но хотелось бы всё таки использовать готовые библиотеки. Приблизительно такую реализацию я ожидал от swool_table.
Я вчера задал на гитхабе им вопрос github.com/swoole/swoole-src/issues/1345 и жду ответа, иначе смыла в нём никакого нету, я смогу написать на php с использованием shmop свой swool_table и он будет занимать меньше памяти.morozovsk Автор
08.09.2017 16:48жаль только то что код с ошибками.
попробовал:
var_export(read_from_heap($heaps, 1));
получил:
array ( 'user' => 220939112, 'location' => 442239836, 'visited_at' => 556494424, 'mark' => 27, );
цифры ненастоящие, такой оценки, пользователя и локации не может быть. Оценка вообще может быть только от 1 до 5.
Что-то пошло не так.
kraso4niy
08.09.2017 12:06За статью спасибо!
Теперь я понимаю смысл этих конкурсов!
Было желание участвовать, но времени не было.
robert_ayrapetyan
>научился использовать yandex tank. У меня наоборот — одно из основных полученных знаний: «никогда не используй танк для хайлоад тестов». Там баги лезли изо всех щелей с самого начала: неправильная обработка connection close (что сыграло на руку наивным гошникам поначалу), «пики» (это отдельная песня, слово «пик» в официальном чате уступало по встречаемости разве что epoll(0). В чате участниками открывались новые учения (гадания по пикам, пики: путь к просвещению, роль пик в становлении христианства и пр.). До конца победить пики так и не смогли и они до сих пор проскакивают даже в песочнице. Для меня большая загадка почему орги мейлру решили использовать именно этот клиент.
morozovsk Автор
да, яндекс танк вёл себя как сумасшедший. при чём локально он был ещё более менее стабильный, а вот на серверах организаторов был абсолютно не предсказуем