На прошлой неделе завершился конкурс HighLoad Cup, идеей которого была реализация HTTP-сервера для туристического сайта.
О том, как за 5 дней написать решение на Go, которое принесет вам 52 место в абсолютном зачете из 295, читайте здесь.
Описание задачи
Пользователь Афиноген В его статья Условия конкурса я уже описывал, но для удобства повторю кратко.Сервер должен реализовать API для сайта путешественника и поддерживать три типа сущностей: путешественник (Пользователь), достопримечательность (Местоположение) и посещение (Посещение).
API должен обеспечивать возможность добавлять в базу любые новые сущности, получать и обновлять их, а также выполнять над ними 2 операции — получение среднего рейтинга достопримечательности (avg) и получение мест, посещенных путешественником (посещений).
Каждая из этих операций также имеет набор фильтров, которые необходимо учитывать при формировании ответа.
Например, API позволяет получить средний рейтинг привлекательности среди мужчин от 18 до 25 лет начиная с 1 апреля 2010 года.
Это накладывает дополнительные трудности при реализации.
На всякий случай, вот краткое формальное описание API:
- ПОЛУЧАТЬ / / получить данные о сущности
- ПОЧТА / / обновить
- ПОЧТА / /новое для создания
- ПОЛУЧИТЬ /пользователи/ /visits, чтобы получить список посещений пользователей
- ПОЛУЧИТЬ /местоположения/ /avg, чтобы получить средний рейтинг достопримечательности
Как хранить данные
Самый первый вопрос, который возникает у каждого, кто прочитал постановку задачи, — как хранить данные.Многие (как и я, например) сначала пытались использовать какую-то базу данных с расчетом на большой объем данных, который не поместится в памяти и не будет пустой тратой времени.
Однако такой подход не дал высокого места в рейтинге.
Дело в том, что организаторы конкурса очень демократично подошли к размеру данных, поэтому даже без какой-либо оптимизации структуры хранения все данные легко помещаются в памяти.
Всего в рейтинговом обстреле было около 1 миллиона путешественников, 100 тысяч достопримечательностей и 10 миллионов посещений, идентификаторы каждой сущности были в порядке от 1. На первый взгляд объём может показаться большим, но если посмотреть на размер структур, которые можно использовать для хранения данных, а также по размеру строк в структурах видно, что в среднем размеры не слишком велики.
Сами структуры и размеры их полей я привел ниже:
Размеры строки в структуре я указал в формате «средняя длина строки» + «размер строкового объекта».type Visit struct { // overall 40 bytes Id int // 8 bytes Location int // 8 bytes User int // 8 bytes VisitedAt int // 8 bytes Mark int // 8 bytes } type User struct { //overall 133 bytes Id int // 8 bytes Email string // 22 bytes + 16 bytes FirstName string // 12 bytes + 16 bytes LastName string // 18 bytes + 16 bytes Gender string // 1 byte + 16 bytes Birthdate int // 8 bytes } type Location struct { // overall 105 bytes Id int // 8 bytes Place string // 11 bytes + 16 bytes Country string // 14 bytes + 16 bytes City string // 16 bytes + 16 bytes Distance int // 8 bytes }
Умножив средний размер каждой структуры на количество объектов, получим, что чисто для хранения данных нам понадобится всего около 518 МБ.
Там не так уж и много, при условии, что мы сможем использовать до 4 ГБ.
Наибольшее потребление памяти, как это ни странно на первый взгляд, происходит не во время самого шеллинга, а на этапе загрузки данных.
Дело в том, что изначально все данные запакованы в .
zip-архив и в первые 10 минут серверу необходимо скачать эти данные из архива для дальнейшей работы с ними.
Распакованный архив весит 200 Мб, + файлы после распаковки весят 1,5 Гб.
Без тщательной работы с данными и без более агрессивной настройки сборщика мусора загрузить все данные не удалось.
Второй момент, который был очень важным, но не все сразу это заметили, заключался в том, что атаки на сервер происходили таким образом, что состояние гонки не могло произойти в принципе.
Тестирование сервера проходило в 3 этапа: на первом этапе были GET-запросы, которые получали объекты и вызывали методы avg (получение среднего рейтинга) и visits (получение посещений пользователей), на втором этапе обновлялись данные (при на этом этапе были исключительно POST-запросы на создание и обновление данных) а на последнем этапе снова были GET-запросы, только с новыми данными и с большей нагрузкой.
Поскольку запросы GET и POST были жестко разделены, не было необходимости использовать какие-либо примитивы синхронизации потоков.
Таким образом, если мы учтем эти два момента, а также запомним, что идентификаторы объектов каждой сущности были в порядке, начиная с 1, то в результате все данные можно будет хранить так: type Database struct {
usersArray []*User
locationsArray []*Location
visitsArray []*Visit
usersMap map[int]*User
locationsMap map[int]*Location
visitsMap map[int]*Visit
}
Все объекты, если размера массива достаточно, помещаются в массив, соответствующий типу.
Если идентификатор объекта больше размера массива, он будет помещен в соответствующий словарь.
Сейчас, зная, что в финале данные вообще не изменились, я понимаю, что словари излишни, но тогда не было никаких гарантий этого.
Индексы
Довольно скоро стало понятно, что для быстрой реализации методов avg и visits необходимо хранить не только сами структуры User и Location, но и id посещений и достопримечательностей пользователей вместе с самими структурами соответственно.В результате я добавил к этим двум структурам поле «Посещения», которое представляет собой обычный массив, и таким образом смог быстро найти все структуры «Посещения», связанные с этим пользователем/достопримечательностью.
Во время тестирования я также думал об использовании «контейнера/списка» из стандартной библиотеки, но знание структуры этого контейнера подсказывало мне, что он всегда будет проигрывать как по скорости доступа к элементам, так и по памяти.
Единственное его преимущество в том, что возможность быстрого удаления/добавления в любой момент не очень важна для данной задачи, так как соотношение количества посещений пользователей примерно 10 к 1, можно сделать предположение, что контейнеры Visit в Структуры местоположения и пользователя будут иметь размер примерно 10. А удаление элемента из начала массива размером 10 единиц вообще не так уж дорого и не является частой операцией.
Что касается памяти, то ее потребление можно проиллюстрировать следующим кодом: package main
import (
"fmt"
"runtime"
"runtime/debug"
"container/list"
)
func main() {
debug.SetGCPercent(-1)
runtime.GC()
m := &runtime.MemStats{}
runtime.ReadMemStats(m)
before := m.Alloc
for i:=0;i<1000;i++ {
s := make([]int, 0)
for j:=0;j<10;j++ {
s = append(s, 0)
}
}
runtime.ReadMemStats(m)
fmt.Printf("Alloced for slices %0.2f KB\n", float64(m.Alloc - before)/1024.0)
runtime.GC()
runtime.ReadMemStats(m)
before = m.Alloc
for i:=0;i<1000;i++ {
s := list.New()
for j:=0;j<10;j++ {
s.PushBack(1);
}
}
runtime.ReadMemStats(m)
fmt.Printf("Alloced for lists %0.2f KB\n", float64(m.Alloc - before)/1024.0)
}
Этот код выдает следующий результат:
Выделено на срезы 117,19 КБ Выделено под списки 343,75 КБЭтот код создает 1000 массивов и 1000 списков и заполняет их 10 элементами, так как это среднее количество посещений.
Число 10 плохо для массива, поскольку при добавлении элементов на 8-м элементе он расширится до 16 элементов и тем самым будет потреблять больше памяти, чем необходимо.
Результаты по-прежнему показывают, что решение со срезами потребовало в 3 раза меньше памяти, что согласуется с теорией, поскольку каждый элемент списка хранит указатель на следующий, предыдущий элемент и на сам список.
Другие пользователи, вышедшие в финал, сделали еще несколько индексов — например, индекс по странам для метода посещений.
Эти индексы, вероятно, ускорят решение, но не настолько, чтобы хранить посещения пользователей и посещения достопримечательностей вместе с информацией об этом объекте.
Библиотеки
Стандартная библиотека для реализации http-сервера довольно проста в использовании и хорошо распространена, но когда дело касается скорости, все рекомендуют fasthttp. Поэтому первым делом после реализации логики было выкинуть стандартный http-сервер и заменить его на fasthttp. Замена прошла абсолютно безболезненно, хотя у этих двух библиотек разные API. Далее была заменена стандартная библиотека кодирования/декодирования json. Я выбрал easyjson, потому что он показал отличные данные о скорости/памяти + имел API, аналогичный «encoding/json».Easyjson генерирует собственный парсер для каждой структуры данных, что и позволяет ему показывать столь впечатляющие результаты.
Единственный его недостаток – небольшое количество настроек.
Например, в задаче были запросы, в которых отсутствовало одно из полей, что должно было привести к ошибке, но easyjson молча пропускал такие поля, из-за чего нам пришлось лезть в исходный код парсеров.
Другие оптимизации
Поскольку все методы API, за исключением методов POST, были реализованы без использования дополнительной памяти, сборщик мусора было решено отключить — все равно, если памяти достаточно, то зачем его запускать? Маршрутизация запросов также была переписана.Каждый запрос определялся по одному символу за раз, что позволяло экономить на сравнении строк.
Оптимизация школы.
Результат
За последние 5 дней соревнований я, не имея никакого опыта участия в подобных соревнованиях, написал решение на Го, которое принесло мне 52 место из 295 участников.К сожалению, до финала мне не хватило совсем чуть-чуть, но с другой стороны, в финале собрались достойные соперники, так что в связи с тем, что данные и условия задания никак не изменились, маловероятно, что Я мог бы подняться выше.
GitHub с решением Теги: #Go #golang #highloadcup #Высокая производительность #Go
-
Понимание Возможностей Flash
19 Oct, 24 -
Основы Поисковой Оптимизации Веб-Сайта
19 Oct, 24 -
Об Интервью
19 Oct, 24 -
Resource Bowl — Советы По Построению Команды
19 Oct, 24
