Как написать хорошее решение для Highload Cup, но недостаточно хорошее чтобы выйти в топ

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


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


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


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


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

  • +23
  • 5,3k
  • 8
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 8
  • 0
    Расскажите, как вычисляли среднюю оценку посещения достопримечательности?
    Просто шли по массиву, считали сумму и делили на количество?
    • 0
      Практически. Для каждой достопримечательности в какой то момент оптимизации сервера я стал хранить список ее посещений. Соответственно когда нужно было посчитать среднюю оценку я просматривал не весь массив с посещениями, а только те, которые относятся к этой достопримечательности. А так да, считал сумму и делил на количество
      • –1
        Есть способ делать это за O(lg(n))
        Нужно хранить с каждым посещением ещё и сумму оценок до этой даты для данной достопримечательности. Делать это надо до первой волны и после окончания второй, нет смысла при каждой вставке их пересчитывать.
        Как происходит выборка: выбираем последнее посещение до даты «from» и последнее посещение до даты «to», бинарным поиском, за O(log(n))
        берем разницу сумм оценок — получаем сумму в этом отрезке
        по разнице индексов найденных границ получаем число оценок
        и всё
        ЗЫ: я сам не участвовал, но эти оптимизации в голове пытался продумывать
        В принципе, вроде больше нечего оптимизировать, если все данные в памяти, есть общий доступ всех процессов к ним, нет data race-ов
        • +2
          Там наибольшее количество посещений достопримечательности было 124 (если не путаю), в основном же оно около десяти.
          Незначимо в общем, относительно затрат на сетевую часть.
    • 0
      deleted(ошибся веткой)
      • –2
        Читаю описания чужих решений и думаю: как же нас всё таки развратили все эти фреймворки, стандартные либы и подходы. Среди знакомых программистов никто не может даже на шаг отступить от привычных решений, типа «юзаем редис» или «создай индекс в базе» и т.п.

        Побольше бы таких конкурсов. И по ширше освещать их на популярных ресурсах.
        Руки чешутся поучавствовать ) Хоть я и нуб.
        • +2
          Просто сначала получаешь некий baseline, используя проверенные и подходящие решения. Возможно, он окажется достаточно хорош, возможно нет. В последнем случае начинаешь аккуратно искать «узкие» места.
          Иначе, скорее всего, просидишь весь конкурс в попытках написать свой http и закончишь конкурс с неполноценным творением, до сути задачи так и не добравшись.
        • +1
          Мне кажется, тут самый интересный момент это «5 дней», ибо показывает тот удачный компромисс в Go между скоростью разработки / производительностью (+читабельностью кода, хотя в конкурсе это не важно было :) ).

          У меня тоже было решение на fasthttp+ffjson, всё в памяти. Оно было написано за чуть более половину дня (субботы) — вот с нуля, с прочтения задания, и до попадания в в десятку на тот момент в рейтинговом обстреле. В воскресенье я провозился с залипшими обстрелами (это ещё было до того, как организаторы выложили ammos для yandex tank), а в будние дни уже было не до этого и интерес пропал.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.