На прошлой недели закончилось соревнование HighLoad Cup, идея которого заключалась в реализации HTTP сервера для сайта путешественников. О том как за 5 дней написать решение на Go, которое принесет 52 место в абсолютном зачете из 295, читайте под катом.

Описание задачи

Пользователь Afinogen в своей статье уже описывал условия конкурса, но для удобства я сжато повторюсь. Сервер должен реализовывать API для работы сайта путешественников и поддерживать сущности трех видов: путешественник (User), достопримечательность (Location) и посещение (Visit). API должно предоставлять возможность добавлять любые новые сущности в базу, получать их и обновлять, а также делать 2 операции над ними — получение средней оценки достопримечательности (avg) и получение мест, посещенных путешественником (visits). У каждой из этих операций так же есть набор фильтров, которые необходимо учитывать при формировании ответа. Так, например, API позволяет получить среднюю оценку оценку достопримечательности среди мужчин от 18 до 25 лет начиная с 1 апреля 2010 года. Это накладывает дополнительные сложности при реализации.

На всякий случай приведу краткое формальное описание API:

• GET // для получения данных о сущности
• POST // для обновления
• POST //new для создания
• GET /users//visits для получения списка посещений пользователем
• GET /locations//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
}

Размеры string в структуре я указал в формате "средняя длинна строки" + "размер объекта string". Умножив средний размер каждой структуры на количество объектов получаем, что чисто для хранения данных нам нужно всего лишь примерно 518 МБ. Не там уж не много, при условии того что мы можем разгуляться аж на 4 ГБ.

Самое большое потребление памяти, как это не было бы странно на первый взгляд, происходит не при самом обстреле, а на этапе загрузки данных. Дело в том, что изначально все данные запакованы в .zip архив и в первые 10 минут серверу необходимо загрузить эти данные из архива для дальнейшей работы с ними. Нераспакованный архив весит 200 МБ, + 1.5 ГБ весят файлы после распаковки. Без аккуратной работы с данными и без более агрессивной настройки сборщика мусора загрузить все данные не получалось.

Второй момент, который был очень важен, но не все сразу его заметили — обстрелы сервера проходили так, что состояние гонки не могло получиться в принципе. Тестирование сервера проходило в 3 этапа: на первом этапе шли GET запросы, которые получали объекты и вызывали методы avg (получения средней оценки) и visits (получения посещений пользователем), вторым этапом данные обновлялись (на этом этапе были исключительно POST запросы на создание и обновление данных) и на последнем этапе опять шли GET запросы, только уже на новых данных и с большей нагрузкой. Из-за того что GET и POST запросы были жестко разделены, не было нужды использовать какие-либо примитивы синхронизации потоков.

Таким образом, если принять во внимание два эти момента, а так же вспомнить что id объектов каждой сущности шли по порядку начиная с 1, то в результате все данные можно хранить так:

type Database struct {
    usersArray     []*User
    locationsArray []*Location
    visitsArray    []*Visit
    usersMap       map[int]*User
    locationsMap   map[int]*Location
    visitsMap      map[int]*Visit
}

Все объекты, если хватает размера массива, помещаются в соответствующий типу массив. В случае, если id объекта был бы больше чем размер массива, он помещался бы в соответствующий словарь. Сейчас, зная что в финале данные абсолютно не поменялись, я понимаю что словари лишние, но тогда никаких гарантий этого не было.

Индексы

Довольно скоро стало понятно, что для быстрой реализации методов avg и visits необходимо хранить не только сами структуры User и Location, но и id посещений пользователя и достопримечательностей вместе с самими структурами соответственно. В результате я добавил поле Visits, представляющее собой обычный массив в эти две структуры, и таким образом смог быстро находит все структуры Visit, ассоциированные с этим пользователем/достопримечательностью.

В процессе тестирования я так же думал об использовании "container/list" из стандартной библиотеки, но знание устройства этого контейнера подсказывало мне что он всегда будет проигрывать и по скорости доступа к элементам, и по памяти. Его единственный плюс — возможность быстрого удаления/добавления в любую точку не сильно важен для этой задачи, так как соотношение количества посещений к пользователям примерно 10 к 1, то мы можем сделать предположение что контейнеры Visit в структурах Location и User будут примерно размером 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)

}

Этот код дает следующий вывод:

Alloced for slices 117.19 KB
Alloced for lists 343.75 KB

Этот код создает 1000 массивов и 1000 списков и заполняет их 10 элементами, так как это среднее число посещений. Число 10 является плохим для массива, так как при добавлении элементов, на 8 элементе он расширится до 16 элементов и тем самым памяти будет затрачено больше чем необходимо. По результатам все равно видно что на решение со слайсами было затрачено в 3 раза меньше памяти, что сходится с теорией, так как каждый элемент списка хранит указатель на следующий, предыдущий элемент и на сам список.

Другие пользователи прошедшие в финал делали еще несколько индексов — например индекс по странам для метода visits. Эти индексы, скорее всего ускорили бы решение, однако не так сильно, как хранение посещений пользователя и хранение посещений достопримечательности вместе с информацией об этом объекте.

Библиотеки

Стандартная библиотека для реализации http сервера достаточно удобная в использовании и хорошо распространена, однако когда речь заходит о скорости, все рекомендуют fasthttp. Поэтому первым делом после реализации логики я выкинул стандартный http сервер и заменил его на fasthttp. Замена прошла абсолютно безболезненно, хоть данные две библиотеки имеют разный API.

Далее под замену ушла стандартная библиотека кодирования/декодирования json. Я выбрал easyjson, так как он показывал отличные данные по скорости/памяти + имел схожий с "encoding/json" API. Easyjson генерирует свой собственный парсер для каждой структуры данных, что и позволяет показывать такие впечатляющие результаты. Его единственный минус — небольшое число настроек. Например, в задаче были запросы, в которых одно из полей отсутствовало, что должно приводить в ошибке, однако easyjson тихо пропускал такие поля, из-за чего пришлось лезть в исходных код парсеров.

Прочие оптимизации

Так как все методы API за исключением POST методов были реализованы без использования дополнительной памяти, было решено отключить сборщик мусора — все равно если памяти хватает, то зачем гонять его?

Так же был переписан роутинг запросов. Каждый запрос определялся по одному символу, что позволило сэкономить на сравнении строк. Школьная оптимизация.

Результат

За 5 последних дней конкурса я, без какого либо опыта участия в подобных конкурсах, написал решение на Go, которое принесло мне 52 место из 295 участников. К сожалению мне не хватило совсем чуть чуть до прохождения в финал, но с другой стороны в финале собрались достойные соперники, поэтому из-за того что данные и условия задачи никак не менялись то маловероятно что я смог бы подняться выше.

GitHub с решением