31.01.2018 02:01
LionZXY 27 3300 Источник

Приветствую, Хаброжители!


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


Minecraft — игра-песочница и на мультиплеер-серверах остро стоит проблема гриферства (от англ. griefing — вредительство), когда игроки рушат чужие постройки. На серверах с этой проблемой справляются по-разному. На публичных используют плагин на 'приват', на остальных же все строится на доверии.


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


Выбор базы данных


Итак, вот у нас массив данных и хорошо бы его куда-то сохранять. Умные люди давно придумали БД. Лично у меня требования к БД были такие:


  • Быстрая вставка
  • Максимальное сжатие данных
  • Возможность из Java без root-прав развертываться без лишних телодвижений

Последний пункт появился из-за того, что не на всех хостингах есть возможность получить root-доступ или установить какой-либо пакет. К тому же, не хотелось усложнять процедуру установки, а остановиться на "Кинул и забыл".


Базы данных, которые удовлетворяли бы всем критериям я не нашел, поэтому решил сделать свою мини-БД на Java.



Оптимизация места на жёстком диске


Основная проблема игры, как считают многие, — все её вычисления происходят в одном потоке. Это настоящая боль держателей серверов. Распараллелить изначально однопоточную архитектуру — надо постараться.



Поэтому само логгирование пришлось вынести в отдельный поток. А чтобы система не захлебнулась от Event'ов в очереди, добавить поддержку воркеров. Количество воркеров настраеваемое.


В итоге получилось так, что само событие перехватывается в главном тике, потом отправляется в поток, который занят тем, что распределяет задачи между воркерами. Там мы получаем файл, в который надо занести наше событие и передаем уже воркеру, который прикреплен к этому файлу. И сама операция IO происходит в воркере.



Оптимизация места на жёстком диске


Большое количество событий может привести к тому, что логи будут весить больше, чем сам мир. Этого нам допустить нельзя, поэтому будем думать.


Изначально строчка в логфайле выглядела так:


[2001-07-04T12:08:56.235-0700]Player PLACE <blockid> to 128,128,128


При беглом взгляде можно заметить, что 2001-07-04T12:08:56.235-0700 можно сократить до Timestamp, а PLACE или REMOVE на символ '+' и '-' соответственно. Ну и уберем нафиг 'to':


[123454678]Player + <blockid> 128,128,128


Не сложно заметить, что в логе будет часто повторятся nickname и blockid. Соответсвенно, их можно вынести в отдельный файл, а в лог писать только id


[123454678]1 + 1 128,128,128


В итоге я пришел к тому, что в строчке лога остались только числа и один символ. Мы сэкономим много места, если уберем разделители (пробелы) и числа будем записывать как байты, а не как символы. Сообственно, это привело меня к решению использовать байтовые логи.


Сама байтовая строка теперь выглядит так:


Name posX posY posZ typeaction playerid blockid timestamp
Field Length (bytes) 4 byte 4 byte 4 byte 1 byte ('0' for Remove, '1' for Insert) 4 byte 8 byte 8 byte

Итого мы имеем 35 байтов на строку фиксированно (1 байт для разделения строк).
Вначале был соблазн оставить 34 байта, но так как запись ведется в один файл, то в случае с фиксированной длинной, если побьется одна строка, весь файл станет нечитаемым.


Путь для логов: /{save}/{world/dimension}/*.bytelog


Структура строки для blockname to id:


Name id blockname
Field Length (bytes) 8 byte 1 byte per symbols

Итого: ~ 21 байтов на блок
Имя файла: blockmap.bytelog


Структура строки для nickname to id:


Name id nickname
Field Length (bytes) 4 byte 1 byte per symbols

Итого: ~ 10 байтов на игрока
Имя файла: nickmap.bytelog


Оптимизация памяти


Чтобы быстро маппить blockname и nickname в id пришлось держать содержимое обоих файлов в памяти. Java не может в HashMap хранить примитивные типы, поэтому каждый Integer будет стоить нам ~50 байт в памяти, что очень много.


Решить эту проблему нам поможет библиотека trove.


private final TObjectIntHashMap uuidToId = new TObjectIntHashMap();

Но каждый символ у нас занимает примерно 2 байта. Мы можем снизить потребления памяти с помощью самописного файла ASCIString, в котором символы хранятся в byte[], а не в char[].


Тестирование


В тестировании байтовой сериализации и десериализации ничего необычного нет, а вот для тестирования компонентов, к которым требовался многопоточный доступ пришлось использовать фреймворк от гугла Thread Weaver. Обычный тест с использованием этого фреймворка выглядит так:


public class NickMapperAsyncTest extends TestCase {
    private volatile NickMapper nickMapper;

    public void testNickMapper() {
        final AnnotatedTestRunner runner = new AnnotatedTestRunner();
        runner.runTests(this.getClass(), NickMapper.class);
    }

    @ThreadedBefore
    public void before() throws IOException {
        nickMapper = new NickMapper();
    }

    @ThreadedMain
    public void main() {
        nickMapper.getOrPutUser(new ASCIString("2"));
        nickMapper.getOrPutUser(new ASCIString("LionZXY"));
        nickMapper.getOrPutUser(new ASCIString("3"));
    }

    @ThreadedSecondary
    public void secondary() {
        nickMapper.getOrPutUser(new ASCIString("2"));
        nickMapper.getOrPutUser(new ASCIString("LionZXY"));
        nickMapper.getOrPutUser(new ASCIString("3"));

    }

    @ThreadedAfter
    public void after() {
        final int first = nickMapper.getOrPutUser(new ASCIString("LionZXY"));
        final int second = nickMapper.getOrPutUser(new ASCIString("2"));
        final int third = nickMapper.getOrPutUser(new ASCIString("3"));
        assertEquals(3, nickMapper.size());
        assertEquals(Integer.MIN_VALUE + 3, Collections.max(Arrays.asList(first, second, third)).intValue());
    }
}

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


Заключение


Пока по количеству скачиваний будет понятно стоит ли развивать дальше этот мод и идею. Из примерных планов на будущее:


  • Добавить возможность удалять старые и неактуальные логи автоматически
  • Добавить сжатие для файлов

Ссылки



P.S. Вы только посмотрите какая офигенная конфиг-система в новых версиях Minecraft Forge
@Config(modid = FastLogBlock.MODID)
@Config.LangKey("fastlogblock.config.title")
public class LogConfig {
    @Config.Comment("Enable handling event")
    public static boolean loggingEnable = true;
    @Config.Comment("Filepath from minecraft root folder to block log path")
    public static String logFolderPath = "blocklog";
    @Config.Comment("Path to nickname mapper file from logFolderPath")
    public static String nickToIntFilePath = "nicktoid.bytelog";
    @Config.Comment("Path to block mapper file from logFolderPath")
    public static String blockToLongFilePath = "blocktoid.bytelog";
    public static HashConfig HASH_CONFIG = new HashConfig();
    @Config.Comment("File splitter type. SINGLE for single-file strategy, BLOCKHASH for file=HASH(BlockPos) strategy")
    public static FileSplitterEnum fileSplitterType = FileSplitterEnum.BLOCKHASH;
    @Config.Comment("Utils information for migration")
    public static int logSchemeVersion = 1;
    @Config.Comment("Utils information for migration")
    public static int writeWorkersCount = 4;
    @Config.Comment("Regular expression for block change event ignore")
    public static String[] ignoreBlockNamesRegExp = new String[]{"<minecraft:tallgrass:*>"};
    @Config.Comment("Permission level for show block log.")
    public static boolean onlyForOP = true;

    public static class HashConfig {
        @Config.Comment("Max logfile count")
        public final int fileCount = 16;

        @Config.Comment("Pattern for log filename. %d - file number. Default: part%d.bytelog")
        public final String fileNamePattern = "part%d.bytelog";
    }

    @Mod.EventBusSubscriber(modid = FastLogBlock.MODID)
    private static class EventHandler {

        /**
         * Inject the new values and save to the config file when the config has been changed from the GUI.
         *
         * @param event The event
         */
        @SubscribeEvent
        public static void onConfigChanged(final ConfigChangedEvent.OnConfigChangedEvent event) {
            if (event.getModID().equals(FastLogBlock.MODID)) {
                ConfigManager.sync(FastLogBlock.MODID, Config.Type.INSTANCE);
            }
        }
    }
}

Комментарии (27)


  1. SystemXFiles
    31.01.2018 06:24
    #10644444

    Появились такие вопросы:

    1. Есть софт для удобного просмотра и поиска операций в определенном радиусе от заданных координат?
    2. Лог пишется в один огромный файл или разбивается на части?
    3. Есть возможность сохранять логи по чанкам?


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

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


    1. LionZXY Автор
      31.01.2018 09:23
      #10644572

      1) Нет, как-то не пришла в голову идея так сделать :)
      2) Разбивается на части. Более того разбивка идет через Filename=Hash(BlockPos), но это все настраивается. Можно и по чанкам.
      3) Да


      С визуализацией не совсем понял, но большое спасибо за фидбек :) Очень полезно.


      1. SystemXFiles
        31.01.2018 10:19
        #10644654

        Относительно визуализации, например, смотреть в виде анимации, что «делал» игрок. Ведь время и действие нам известны, значит при желании, можно просто визуально посмотреть.
        Но это фича из разряда «хотелка», потому что требует времени на реализацию куда больше, а полезность чисто эстетическая и чуть проще понимать суть происходящего.

        Как вариант можно сделать мод для клиента, что позволит читать эти логи и прямо в игре визуализировать действия. По типу демок для CS той же.


      1. SystemXFiles
        31.01.2018 10:28
        #10644674

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

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


        1. LionZXY Автор
          31.01.2018 10:30
          #10644676

          Не понятно чем тогда будет отличаться этот мод от простого привата :)


          1. SystemXFiles
            31.01.2018 10:35
            #10644690

            Приват иногда можно обойти, плюс данный лог будет просто как дополнение. Хотя я играл как-то на сервере, где как раз таки собирается статистика по всем действиям игроков. Спокойно можно было отследить, кто разнес постройку.


    1. LionZXY Автор
      31.01.2018 09:25
      #10644576

      А и ещё. Вставка в кластерный индекс по-любому будет занимать O(logN), а я хотел очень быструю вставку O(1) и медленный поиск O(1). Мой косяк что не рассказал об этом


    1. eliduvid
      31.01.2018 09:29
      #10644586

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


      1. LionZXY Автор
        31.01.2018 09:34
        #10644600

        Ну, вообще, высота настраиваемая и часто бывает что строят выше 256. Да и я старался сделать мод максимально отказоустойчивым, поэтому следовал API Minecraft (если Майн говорит что координаты Инты — я ему верю)
        А вот с чанкам и оптимизацией по 7 байт это идея, хехе. Единственное, возможность делить файлы настраиваемая, поэтому придется либо отказываться от этой фичи, либо хардкодить. Я подумаю, вообщем. Звучит заманчиво


        1. eliduvid
          02.02.2018 01:05
          #10648828

          Выключить по-умолчанию + флаг в настройках?)
          Для желающих там же можно включить всё же хранение высоты в одном или двух байтах, у кого высота не сильно большая.


  1. voe
    31.01.2018 07:54
    #10644498

    А почему не писать в elasticsearch? Отказоустойчивость, быстрая запись и чтение, можно делать постые запросы по координатам.


    1. SystemXFiles
      31.01.2018 08:23
      #10644522

      Не настолько быстрые, чем невероятно простой способ записывать бинарные данные одного размера друг за другом. Особенно если там задействована буферизация.


  1. fediq
    31.01.2018 08:25
    #10644528

    Чего только не делают люди, лишь бы не читать best practice...


    Однопоточное приложение не в состоянии нагрузить больше одного потока нормально написанного логгера.


    Поэтому: асинхронный аппендер logback, все параметры блока в MDC, там бинарный сериализатор — и в logstash. Всё, минимум кода, один конфиг.


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


    1. LionZXY Автор
      31.01.2018 09:27
      #10644584

      Ну, по правде говоря, приложение всё-таки +- многопоточное (каждый мир работает в своем потоке). Да и количество воркеров не просто так настраиваемое.


  1. Softer
    31.01.2018 11:42
    #10644814

    А «разбор полетов» как выполняется? Грепаньем по логу в поисках координат? :)

    Почему только 2 события? Если я разолью лаву/воду за N блоков до «привата» и после — уберу за собой (чтобы не было следов «откуда прилетело»)? А если с лука выбью итем из рамки? Полутаю сундуки?

    За идеями можно глянуть тот-же bukkit-плагин Hawkeye. Он хоть и «мертвый», но вполне рабочий.
    PS: Хотя я скоро буду его менять (как ни крути — старый он, да и функционал для меня избыточен) и буду строить свое через RabbitMQ с записью или в Elastic или в ClickHouse.


    1. LionZXY Автор
      31.01.2018 11:46
      #10644824

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


      1. Softer
        31.01.2018 11:55
        #10644850

        А строить запросы «Кто ломал(!) блоки в этой точке и в радиусе 4 блоков?»?
        Или «Что последнее делал игрок 'Griefer' в этом пространстве (пространство — заданный 2-ми координатами кубоид)?».
        Вопросы не выдуманные, боевые :)


        1. LionZXY Автор
          31.01.2018 11:59
          #10644864

          Вполне можно такое сделать, но сейчас такого нет, да :)


          1. Softer
            31.01.2018 12:01
            #10644878

            Как такое решение будет работать с 50-100 гб данных?
            Я к тому что «Зачем изобретать еще один велосипед»?
            PS: Я уже молчу о выводе инфы для админа в «веб-админку» какую ;)


            1. LionZXY Автор
              31.01.2018 12:04
              #10644880

              Долго, но не затрагивая главный поток.
              Но, в целом, ваши замечания понятны. Такое количество функционала требует много времени и на постоянную поддержку мода, в том числе. У меня его нет


              1. Softer
                31.01.2018 12:10
                #10644888

                Последние правки для Hawkeye я делал года 4 назад. Работает до сих пор на версиях 1.7.10-1.12.2. Так что не знаю, что там насчет времени :)
                Но в качестве практики по разработке выполненная работа — да, однозначно интересна.


              1. fediq
                31.01.2018 16:02
                #10645438

                В стеке ElasticSearch это всё из коробки будет. Свои велосипеды, напротив, это почти всегда неполноценное решение. Не надо так, учитесь переиспользовать опыт предков.


  1. Rastishka
    31.01.2018 16:11
    #10645464

    На каком то публичном серваке полном грифферов стоял плагин, который делал запрещенными к разрушению другими пользователям печки, верстаки, двери и сундуки. Остальное можно было разрушать как угодно (или платная подписка на кусок земли).

    В результате я построил себе дом целиком из печек.

    Было забавно через неделю посмотреть что кто то пытался сделать подкопы, залить водой и как то еще испортить дом. Но дом выстоял. =))

    Так, вспомнилось о майнкрафте.


  1. Gravit
    31.01.2018 20:00
    #10645978

    Есть сравнения произвроддительности например с CoreProtect(на SQLite)? Очень интересно узнать альтернативные варианты.


    1. Donquih0te
      31.01.2018 23:39
      #10646348

      Не думаю, что SQLite в этом случае будет быстрее.


  1. momai
    01.02.2018 14:58
    #10647662

    Есть же проект Prism
    dev.bukkit.org/projects/prism
    Там и работа происходит в другом потоке, на сколько мне известно, так же предлагают большие возможности по кастомизации дополнения, ну и вообще функционально.
    Странно, что тут предлагается пофайловая система логирования, а не в базу данных, к примеру в MySQL.

    Интересно, какие автор пытался решить задачи, с которыми не справились существующие системы LogBlock (устаревший) Prism-2, CoreProtect, и какова, по сравнению с ними, разница?


    1. LionZXY Автор
      01.02.2018 15:17
      #10647734

      Вроде написал. Быстрее вставка, намного меньше памяти занимает на диске.