R*-tree в Go, немного геймдева и поиска элементов в пространстве

Приветствую, уважаемые читатели Habr!

Сегодня я хотел бы рассказать об интересном подвиде одного алгоритма, о котором Вы могли возможно забыть!

Начну с предыстории...

У меня довольно интересный, но малозначительный опыт в разработке игровых модификаций под некоторые игровые проекты, как на языках NodeJS, так и Lua, которые использовались на сервере и клиенте.

Эти модификации, с которыми я работал, являются мультиплеерами (далее - МП) для трехмерных игр (в подробности вдаваться не будем). В один прекрасный день, я все же решил углубиться в настоящий Highload и изучать для себя язык Go. Пока я ходил по собеседованиям, я понял, что у меня действительно малозначительный опыт именно в разработке высоконагруженных систем.

И, пока всё это происходило, я понял, что знания все же необходимо подтягивать, а сами собеседования помогут направить меня в нужное русло. И, после одного из собеседований с вопросами об индексах, я решил углубиться в них (помимо бездумного расставления btree и hash через EXPLAIN ANALYZE).Так я наткнулся на интересный для себя индекс в PostgreSQL - GiST.

Что из себя представляет индекс GiST? Вспомним, что GiST - это подвид структуры R-tree, которая позволяет быстро обращаться к данным в пространстве.

Когда я это прочитал, мне стало невероятно интересно, как в игровых модификациях, с которыми я работал, обстоят дела с пространственным поиском?

Как с этим обстоят дела в той сфере, где я работаю:

Там, где я работаю, существует один из старейших МП, разработанный ещё в 2004 году. Исходников у меня не было, поэтому мне стало интересно, как решали эту проблему тогда и, возможно, сейчас.

Объяснение для тех, кто совсем не связан с играми.
В каждом МП, где большое количество игроков (а я работал с МП, где средний онлайн на одном сервере более 300-500, а порой и 1000 человек). Представляем себе большую карту и понимаем, что игрокам не обязательно видеть друг друга на большом расстоянии.

Поэтому у каждого игрока есть своя зона видимости - то есть, зона стрима.
Эта зона стрима обновляется не в реальном времени каждую возможную единицу времени, а раз в секунду, для того чтобы не создавать большой нагрузки на сервер МП. В итоге, я решил узнать, как конкретно игрок 1 должен узнавать, что игрок 2 должен находиться в зоне стрима.

Обратившись к своему хорошего другу, с кем я продолжаю работать в этой сфере, и скинув ему интересную статью, он подсказал мне, как действительно устроен стриминг в этом МП. Он смог покопаться в закрытом исходном коде и найти конкретно то место, которое меня интересовало. Ответ меня поразил и смутил. Разработчик МП буквально перебирал каждого игрока для каждого игрока.

Я был в шоке, но в то же время понимал, почему разработчик этого старого МП ограничился всего 1000 игроков в пределах одного сервера. Если бы он поставил хотя бы ограничение в 1500 игроков, то сложность поиска игроков в зоне стрима увеличилась бы уже буквально в 2.25 раз. И, судя по метрикам, даже текущее решение съедало не мало так ресурсов.

Решение уже близко

Вооружившись современным инструментов в виде языка Go я решил провести искусственное нагрузочное тестирование с алгоритмами R-tree и квадратным (каждый игрок для каждого игрока) линейным поиском.

Что я сделал в логике приложения на Go?

На сервере есть сущности с данными:

• Координаты X и Y

• Массив указателей на игроков, которые находятся в зоне видимости этой сущности

Данные области видимости и "поля" для поиска:

• Размер поля в X и Y (2000x2000 у. е.)

• Размер стороны области видимости

Область видимости, в данном случае - это квадрат с равными сторонами, которые указаны в данных выше. Сущность, к которой применяется поиск, находится в центре этого квадрата.

Синхронизация в логике Go обновляется раз в секунду.

У следующих сущностей будут случайно сгенерированная позиция в пределах поля.

Теперь к самим показателям, начнем с квадратичного линейного поиска:

С учетом того, что синхронизация обновляется раз в секунду, мы можем понять, что при показателях в 4000 сущностей сервер просто перестанет нам отвечать, если все данные обрабатываются в одном потоке или если есть обращение к этой структуре...

Как это выглядит в коде:

for i := 0; i < len(players); i++ {
  for k := 0; k < len(players); k++ {
    p1 := players[i]
    p2 := players[k]
    if(dist(p1, p2) > visibleDistance) {
      continue;
    }
    p1.playersInStream = append(p1.playersInStream, p2)
  }
}

Сложность квадратичного линейного поиска здесь буквально O(n^2), и мы можем её сократить. Например, если один игрок уже видит второго, то и второй игрок видит первого. Следовательно, нам не нужно перебирать весь список игроков внутри второго цикла. В итоге, можем представить новый код уже вот так:

for i := 0; i < len(players); i++ {
  for k := i; k < len(players); k++ {
    p1 := players[i]
    p2 := players[k]
    if(dist(p1, p2) > visibleDistance) {
      continue;
    }
    p1.playersInStream = append(p1.playersInStream, p2)
    p2.playersInStream = append(p2.playersInStream, p1)
  }
}

Довольно банальное решение, и я был крайне удивлен, что разработчик мультиплеера к этому не пришел. Показатели O(n^2)/2:

Уже лучше, но даже с учетом затрат в виде 580 из 1000 мсек чисто на синхронизацию - это невероятно много, потому что в том же потоке работает ещё и основная логика сервера. В общем, это решение так же не подходит...

И, наконец, гвоздь программы - R-tree!

К моему счастью (огромное спасибо dhconnelly) я буквально сразу нашел библиотеку rtreego, которая реализовывала структуру R-tree в языке Go.

Я был невероятно удивлен, ведь показатели времени обновления зоны стрима оказались от 4 до 10 раз меньше, чем то, что используется сейчас!

Что удивительно, в моей сфере есть более современный мультиплеер, у которого есть примерно аналогичная проблема, но утверждать я, к сожалению, ничего не могу, так как нет доступа к исходному коду от слова СОВСЕМ.

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

Причем здесь вообще R*-tree?

Я уже радовался победе, что сделал что-то полезное, как друг, которому я скидывал я скидывал эту же статью обратил внимание, что там написано R*-tree, а не R-tree в некоторых местах.

Как мы поняли, R*-tree и R-tree - это две разных структуры данных, первая является подвидом второй. Параллельно я решил покопаться у себя в показателях, заведя свой код с отладкой, и понял, что 70-80% времени занимает вставка и удаление.

Я решил сравнить R-tree и R*-tree хоть в каких-нибудь бенчмарках, чтобы убедиться, что, возможно, есть алгоритм ещё эффективнее.

Поискав бенчмарки R*-tree в сравнении R-tree и наткнувшись на:

Имплементация на Java с показателями оказалась ровно тем, что мне нужно, но...
Оказалось, что показатели вставки в R*-tree гораздо медленнее, но поиск гораздо эффективнее. Мне стало резко интересно, а есть ли R*-tree такое в Go? И такого не оказалось.

И тут мне невероятно сильно захотелось это воссоздать и сравнить на практике...

Так что же такое R-tree? И в чём разница R-tree и R*-tree?

После таких историй пора приступить к делу и понять, в чём разница между R*-tree и R-tree простыми словами

R-tree - это древовидная структура, которая разбивает пространство на области.

R*-tree - это подвид структуры дерева R-tree, которое балансирует эти данные, чтобы поиск по этому дереву был эффективнее.

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

Возьмем пример обычного R-tree:

Синими квадратами обозначаются поддеревья или ветки.

Красными квадратами обозначаются "листья" этих поддеревьев, в которых хранятся элементы.

Черные точки - те самые элементы в этом дереве.

Теперь же возьмем пример R*-tree:

Все данные остаются теми же самыми, но мы буквально можем заметить визуальные отличия:

1. Поддеревья и ветки располагаются так, чтобы не накладываться друг на друга. Уменьшается перекрытие веток.

2. Все ветки или поддеревья стараются быть минимальных размеров. Уменьшается площадь листьев и веток.

Как раз, в этом и есть главная задумка R*-tree!

При абсолютно каждой вставке элемента происходит цикл, который перебирая все возможные элементы, старается уменьшить площадь веток и перекрытие веток, таким образом, упрощая в будущем поиск по этой структуре данных!

Как мы понимаем, за счет таких манипуляций, растёт и цена (то есть, время) вставки элемента. Причем, если дерево становится больше, то и элементов нужно перебирать больше.

Ну и зачем оно вообще нужно: что одно, что второе?

Буквально, на примере разработки игровых модификаций, я пришел к таким выводам:

Где можно использовать R-tree?

• Игровые мультиплееры с большим количеством элементов;

• Любая реал-тайм карта с множеством элементов, которые перемещаются (например, карта автомобилей с такси)

Где можно использовать R*-tree?

• Статические карты хоть с миллионом миллионов элементов (например, это можно использовать в игровом стриминге статических объектов);

• Любые гео-данные, которые читаются в несколько раз чаще, чем заполняются (например, карта целого города или области)

Псевдо-бенчмарки

Я решил не использовать стандартное решение в виде бенчмарков Go и буквально на своих примерах показать время обработки запросов. Я решил взять приблизительные размеры карты той игры, в которой я работал, и актуальный размер зоны стрима.

• Область в условных единицах: 8000x8000

• Область видимости: 500x500, элемент находится в центре зоны видимости

• Позиции элементов: генерируются случайно

• Показатели: средние из 3-5 прогонов

Интересная идея: невероятно эффективным (и простым в реализации, особенно в случае языка Go) решением является создание нескольких деревьев для поиска, чтобы искать элементы в разных горутинах в нескольких деревьях. Простыми словами - чтобы достичь максимальной эффективности - нужно найти для себя максимальное количество элементов в среднем на дерево и делить деревья на равные части. Буквально, как партицирование в БД :)

Самое важное (ссылка на мою реализацию R*-tree в Go):

Конец

Невероятно огромное спасибо за внимание!

Если Вы знаете более эффективные решения для игр или гео-данных на вставку или чтение, я буду очень рад почитать в комментариях!

Дополнительно

Ссылка на реализацию rtreego (обычного R-tree), которую я взял за основу и переделал её под R*-tree.