Наконец-то подошёл к концу 20-дневный матч-реванш.Международная практика - сначала говорить о результатах.Результаты матча-реванша не были идеальными.Однажды они опустились с 10-го места на итоговое 36-е место.Главная причина в том, что карта оптимизации написана уже 5 дней, а прогресса нет., итоговый рейтинг так же фиксируется на второй странице лидерборда. После всей боли в этой статье перечислены знания, которые я получил в матче-реванше, успешная оптимизация и неудачная оптимизация.
Введение в конкурс
Описание темы очень простое: используйте Java или C++ для реализации внутрипроцессного механизма очередей, и одна машина может поддерживать более 1 миллиона очередей.
public abstract class QueueStore {
abstract void put(String queueName, byte[] message);
abstract Collection<byte[]> get(String queueName, long offset, long num);
}
Напишите реализацию вышеуказанного интерфейса.
Метод put записывает сообщение в очередь. Этот интерфейс должен быть потокобезопасным. Программа оценки будет вызывать этот интерфейс одновременно, чтобы поместить его. Содержимое каждой очереди хранит сообщения в том порядке, в котором они отправляются (который может быть понимается как список в Java).Каждое сообщение будет иметь индекс, индекс начинается с 0, содержимое разных очередей не зависит друг от друга и не влияет друг на друга, имя_очереди представляет имя очереди, сообщение представляет содержимое сообщения, содержимое будет генерироваться случайным образом во время оценки, и большая часть длины составляет 58 байт или около того, будет небольшое количество сообщений размером около 1 КБ.
Метод get считывает пакет сообщений из очереди. Прочитанные сообщения должны отправляться в том порядке, в котором они отправляются. Этот интерфейс должен быть потокобезопасным, то есть программа оценки будет вызывать этот интерфейс одновременно для получения, и возвращенная коллекция будет читаться одновременно. Но это не требует записи, поэтому она должна быть только потокобезопасной. queueName представляет имя очереди, offset представляет начальный индекс сообщения в этой очереди, а num представляет количество прочитанных сообщений.Если сообщений достаточно, то Возвращает количество элементов, в противном случае возвращаются только существующие сообщения.Если сообщений недостаточно, возвращается пустой набор.
Введение в процедуры оценки
- Этап отправки: Размер сообщения около 58 байт, а количество сообщений около 2 миллиардов, то есть общий объем отправленных данных около 100G, а общее количество очередей 100w
- Стадия проверки индексов: будет выполняться случайная проверка индексов всех очередей, в среднем каждая очередь будет проверена 1~2 раза (случайное потребление)
- Стадия последовательного потребления: выделить 20% очереди длявсечитать и проверять; (последовательное потребление)
- Максимальное время, затраченное на фазе отправки, не может превышать 1800 с; фаза проверки индекса и фаза последовательного потребления вместе, максимальное потребление времени не может превышать 1800 с; тайм-аут будет расценен как сбой оценки.
- Количество потоков на каждом этапе составляет около 20–30.
Тестовая среда — 4c8g ECS, а максимальный используемый размер JVM ограничен 4 ГБ (-Xmx 4g). Принесите SSD-диск размером около 300G. Для Java-плееров доступная память может пониматься как: 4g вне кучи и 4g в куче.
Анализ конкурсных вопросов
Сначала проанализируйте тему, описание интерфейса очень простое, есть только один метод put и метод get. Необходимо обратить особое внимание на программу оценки.На этапе отправки необходимо отправить очередь 100 Вт.Объем каждой передачи составляет всего 58 байт, а окончательный общий объем данных составляет 100 г.Проверка индекса и последовательное потребление все этапы называются интерфейсами получения, разница в том, что первая проверка индекса — это случайное потребление, а вторая — полное последовательное потребление 20% очередей, начиная с индекса 0. Крайне важно оценить влияние характеристик программы на конечный результат. конструкция хранилища.
Одной из трудностей вопроса о матче-реванше является проектирование очереди на один миллион.Согласно рассмотренной информации показано, что
- Одна машина Kafka имеет более 64 очередей/разделов, и количество разделов Kafka не должно быть слишком большим.
- Одна машина RocketMQ поддерживает до 50 000 очередей.
Что касается сценария использования миллионов очередей, я могу представить такое требование только в сценарии IOT. По сравнению с предварительным раундом дизайн матча-реванша более неопределенный, и лучшие игроки могут выбрать совсем другой дизайн.
Точки проверки рематча в основном включают следующие аспекты: чтение и запись блоков диска, буферизация чтения и записи, последовательное чтение и запись и случайное чтение и запись, pageCache, разреженный индекс, дизайн хранилища очереди и т. д.
Поскольку результаты полуфинала были не очень удовлетворительными, основной причиной стала неоптимизация интерфейса путов, итоговый результат составил 126w TPS, в то время как TPS первого эшелона достиг 200w+ TPS. Ввиду этого я не хочу перечислять его по процессу оптимизации, как итог предварительного раунда, а хочу поделиться со всеми предварительным исследованием собственной схемы и дизайнерскими идеями. О файловом вводе-выводе также можно использовать эту статью как научно-популярную статью для чтения.
Подробная идея
Определить, как файл читается и записывается
Как преданный поклонник Java, я, естественно, выбираю Java в качестве языка соревнований.Хотя окончательный рейтинг монополизирован шишками Cpp, у меня нет другого выбора, кроме как отбросить Cpp в сторону после выпуска. Интерфейсы чтения и записи файлов в Java можно условно разделить на три категории:
- Стандартный ввод-вывод для чтения и записи, расположенный по адресуjava.ioПод пакетом родственные классы: FileInputStream, FileOuputStream
- NIO для чтения и записи, расположенный в пакете java.nio, связанные классы: FileChannel, ByteBuffer
- Карта памяти Mmap, расположенная в пакете java.nio, связанные классы: FileChannel, MappedByteBuffer
Стандартное чтение и запись IO не имеет исследовательской ценности и передается напрямую, поэтому выбор между NIO и Mmap стал первым объектом исследования.
На первом этапе исследовали Mmap. После поиска я обнаружил, что почти все статьи согласны с тем, что технология отображения памяти, такая как Mmap, является самой быстрой. Многие люди, которые не сталкивались с технологией отображения памяти, возможно, не знают, что это за технология.Короче говоря, Mmap может напрямую отображать файлы в адреса памяти пользовательского режима, так что операция с файлами больше не является операцией записи./ чтение, которое преобразуется в прямую операцию над адресом памяти.
public void test1() throws Exception {
String dir = "/Users/kirito/data/";
ensureDirOK(dir);
RandomAccessFile memoryMappedFile;
int size = 1 * 1024 * 1024;
try {
memoryMappedFile = new RandomAccessFile(dir + "testMmap.txt", "rw");
MappedByteBuffer mappedByteBuffer = memoryMappedFile.getChannel().map(FileChannel.MapMode.READ_WRITE, 0, size);
for (int i = 0; i < 100000; i++) {
mappedByteBuffer.position(i * 4);
mappedByteBuffer.putInt(i);
}
memoryMappedFile.close();
} catch (Exception e) {
e.printStackTrace();
}
}
Приведенный выше код показывает самый простой способ использования Mmap, а о скорости речи не идет, одним словом: быстро! Я искал больше доказательств со скептическим отношением. Отличный исходный код всегда является первым эталонным объектом. Глядя на дизайн RocketMQ, мы можем обнаружить, что NIO и Mmap появляются в исходном коде, но больше операций чтения и записи, кажется, предпочитают Mmap более. Исходный код RocketMQorg.apache.rocketmq.store.MappedFileДва метода написания существуют одновременно.Посоветовавшись с @CraftsmanshipZero, я, вероятно, пришел к выводу, что основное написание RocketMQ выполняется через Mmap.
Тем не менее, существует две основные проблемы, возникающие, когда фактически используют MMAP в качестве письма. С точки зрения использования, ограничения MMAP подвергаются:
- Mmap может отображать только 1,5 ~ 2 ГБ файловой памяти один раз в Java, но на самом деле наш файл данных больше 100 ГБ, что вызывает первый вопрос: либо вам нужно физическое разделение, разрезать на несколько файлов; либо сделать логическое разделение при отображении файла, отображение сегментации больших файлов. Размер одного файла ограничен, чтобы избежать этой проблемы.
- Причина, по которой Mmap работает быстро, заключается в том, что он использует память для ускорения. Поведение mappedByteBuffer при размещении на самом деле является операцией с памятью. Фактическое поведение очистки зависит от регулярной очистки операционной системы или ручного вызова интерфейса mappedByteBuffer.force() для очистки памяти. диск., иначе это приведет к зависанию машины (заключение после фактического измерения). Из-за ограниченной памяти в среде рематча возникает сложная проблема управления с помощью Mmap.
После такого метания вкупе со сбором данных окончательно определился,Mmap имеет преимущества в сценариях, где памяти много, а объем данных небольшой.(В большинстве статей сделан вывод, что Mmap подходит для чтения и записи больших файлов, и я подумал, что это неточный вывод).
На втором этапе я исследовал FileChannel Nio, который также является решением для чтения и записи, которое я окончательно определил.
Поскольку каждое сообщение имеет размер всего около 58 байт, запись напрямую через FileChannel определенно столкнется с узкими местами.На самом деле, если вы сделаете это, предполагается, что матч-реванш даже не сможет запуститься. Другое высказывание состоит в том, что минимальная единица записи ssd составляет 4 КБ.Если одна запись меньше 4 КБ, на самом деле она занимает столько же времени, сколько 4 КБ. Это включает в себя важный контрольный пункт вопроса конкурса: чтение и письмо блока.
Согласно внедрению облачного SSD-диска Alibaba Cloud, идеальный IOPS может быть получен только при записи 16–64 КБ за раз. Характеристики блочного хранилища файловой системы вдохновляют нас на настройку буфера записи в память, запись одного сообщения в буфер памяти и использование FileChannel для очистки диска при заполнении буфера. После практики производительность записи при использовании FileChannel с буфером ничем не отличается от Mmap, когда памяти достаточно, а FileChannel не имеет ограничения на размер файла, а управление относительно простое, поэтому я, наконец, решил использовать FileChannel для чтения и записи.
Определить структуру хранения и структуру индекса
Поскольку фоном соревнования является очередь сообщений, случайное обнаружение в фазе 2 и последовательное потребление в фазе 3 будут считывать несколько последовательных сообщений за раз, а последовательное потребление в фазе 3 происходит от индекса 0 очереди к индексу 3. последнее сообщение. , эти факторы вдохновляют нас: сообщения в одной очереди должны храниться вместе как можно больше. Буфер записи, упомянутый в предыдущем разделе, очень совместим с дизайном здесь.Например, мы можем настроить буфер записи в очереди (у конкурентов Java имеет 4 г памяти вне кучи, очередь 100 Вт, и очередь использует DirectByteBuffer для выделения 4 КБ памяти вне кучи, что может гарантировать, что буфер не взорвется в память), чтобы сообщения в одном и том же буфере размещались на диске вместе, что обеспечивает порядок сообщений в блоке, что то есть «сообщения в одной очереди хранятся вместе, насколько это возможно». Доступ к сообщениям по блоку в настоящее время имеет два преимущества:
- Чтение сообщений по частям => чтение сообщений по блокам, использование блочного чтения и уменьшение количества операций ввода-вывода.
- Полный индекс => разреженный индекс. Данные в блоке непрерывны, поэтому необходимо записать только смещение блока в физическом файле + количество сообщений в блоке, чтобы вычислить физическое местоположение сообщения. Это значительно уменьшает количество индексов. После небольшого расчета можно обнаружить, что можно использовать структуру данных карты. Ключ — это имя очереди, а значение — индекс списка для хранения блока очереди в памяти. В соответствии с традиционной схемой проектирования: одна очередь и один индексный файл, миллионы файлов неизбежно превысят установленный по умолчанию лимит дескрипторов системных файлов. Индекс хранится в памяти, чтобы избежать проблемы с количеством файловых дескрипторов, и скорость не должна быть большой.Файловый ввод-вывод и ввод-вывод памяти не одного порядка.
Поскольку в конкурсном вопросе указано, что тело сообщения имеет нефиксированную длину, большинство сообщений имеет длину 58 байт, а небольшое количество сообщений имеют характеристики данных 1 кбайт, поэтому при хранении можно использовать структуру short+byte[]. тело сообщения Short записывает фактическую длину сообщения, byte[] записывает полное тело сообщения. Short на 2 байта меньше, чем int, 2*2 миллиарда сообщений, что позволяет уменьшить объем данных на 4g.
Плотный индекс предназначен для индексации всего количества сообщений, что подходит для сообщений не по порядку.Объем индекса большой, и данные могут быть доступны по барам.
Разреженный индекс подходит для сообщений, хранящихся в блоках, блоки упорядочены, и он подходит для упорядоченных сообщений.Объем индекса небольшой, и доступ к данным осуществляется в соответствии с блоком.
Из-за характеристик последовательного хранения и последовательного использования очередей сообщений, а также ограничения, заключающегося в том, что минимальная единица доступа к облачному диску SSD составляет 4 КБ (намного больше, чем одно сообщение), разреженное индексирование очень подходит для этого сценария. Что касается файла данных, его можно преобразовать в параметры в соответствии с фактическим тестом, чтобы определить, хорош ли эффект нескольких файлов или одного файла, это решение поддерживает один файл размером 100 г.
Буфер чтения и записи памяти
При разработке разреженного индекса мы упомянули концепцию буферов записи.Согласно расчетам, можно обнаружить, что если очередь в 100 Вт выделяет буфер записи, она может выделить максимум 4 КБ, что как раз наименьшее размер блока записи на ssd.(Но по данным предоставленным облачным диском ssd ранее, за один раз можно записать только 64k, чтобы заполнить io).
4k записывается за раз, что приводит к размеру блока 4k в физическом файле, и 4k также считывается за раз при чтении.
// 写缓冲区
private ByteBuffer writeBuffer = ByteBuffer.allocateDirect(4 * 1024);
// 用 short 记录消息长度
private final static int SINGLE_MESSAGE_SIZE = 2;
public void put(String queueName,byte[] message){
// 缓冲区满，先落盘
if (SINGLE_MESSAGE_SIZE + message.length > writeBuffer.remaining()) {
// 落盘
flush();
}
writeBuffer.putInt(SINGLE_MESSAGE_SIZE);
writeBuffer.put(message);
this.blockLength++;
}
Часть, которая меньше 4k, может быть заполнена 0 или пропущена. Профилировщик обеспечивает синхронность операций записи на уровне очереди, поэтому мы не можем беспокоиться о проблемах синхронизации для одной и той же очереди. После завершения записи ту же логику можно использовать для чтения.Поскольку операция получения является параллельной, будет от 10 до 30 потоков, одновременно использующих одну и ту же очередь на этапах 2 и 3, поэтому буфер чтения операции получения может быть разработан какThreadLocal<ByteBuffer>, очищать каждый раз, когда он используется, что гарантирует, что буфер будет совершенно новым каждый раз, когда он читается, и уменьшает создание буферов чтения, иначе это приведет к частому полному сбору мусора. Псевдокод чтения пока не выложен, т.к. такая схема get не является окончательной схемой.
Вот и вышла общая архитектура дизайна.Основная логика процесса написания и чтения выглядит следующим образом:
Процесс записи:
Процесс чтения:
Оптимизация кеша чтения памяти
Дизайн схемы несколько раз переворачивался, прежде чем была определена вышеупомянутая архитектура.Преимущество такой архитектуры в том, что она очень проста и понятна.Но фактический эффект не идеален. Текущая оценка вышеупомянутой архитектуры, вероятно, может достигать 70 ~ 80 Вт TPS, что можно рассматривать только как оценку третьего эшелона. Прежде чем представить оптимизацию кэша чтения, позвольте мне представить концепцию PageCache.
Ядро Linux кэширует в памяти недавно использованные файловые страницы в течение определенного периода времени, этот файловый кэш называется PageCache. Как показано на фиг. Обычная операция read() происходит между буфером, предоставленным приложением, и PageCache. Алгоритм упреждающего чтения отвечает за заполнение этого PageCache. Кэш чтения приложения, как правило, относительно невелик.Например, гранулярность чтения и записи команды копирования файла cp составляет 4 КБ; алгоритм упреждающего чтения ядра будет выполнять ввод-вывод перед чтением с размером, который, по его мнению, больше подходит, например 16-128КБ.
В общем, мы считаем, что последовательное чтение выполняется быстрее, чем случайное, и PageCache вносит наибольший вклад.
Возвращаясь к теме, это довольно приятно, потому что данные в одной и той же очереди на диске частично непрерывны (один и тот же блок является непрерывным), на самом деле в блоке 4 КБ может храниться более 70 данных, а в последовательном этап потребления, один раз. Смещение обычно равно 10. Благодаря механизму предварительного чтения PageCache 7-кратный ввод-вывод файла можно сократить до 1-кратного! Это невероятная оптимизация, но приведенная выше архитектура имеет только TPS 70~80 Вт, что заставило меня усомниться После долгих поисков информации я наконец нашел проблему с напоминанием @江学雷.
Есть две возможные причины, по которым pageCache нельзя использовать для кеширования в игре.
- Поскольку я использую FIleChannel для чтения и записи, чтение и запись NIO может проходить через Direct IO, поэтому он вообще не будет проходить через уровень PageCache.
- Память ограничена в тестовой среде, и PageCache малоэффективен в ситуациях с интенсивным вводом-выводом.
Хотя я не уверен, по какой причине невозможно использовать PageCache, моя схема хранения по-прежнему удовлетворяет характеристикам последовательного чтения, и будет очень большое улучшение.
Одна очередь и один буфер чтения используются для последовательного чтения, и на этапе получения нет проблем с параллелизмом, поэтому я решил повторно использовать буфер чтения и добавить блокировку на уровне очереди в операцию получения, что является небольшой жертвой. на 2-м этапе конфликта нет, вероятность конфликта на 3-м этапе невелика. Схема модифицированного кэша чтения выглядит следующим образом:
После преобразования кэша Direct IO также может добиться оптимизации, аналогичной PageCache, и он будет более управляемым, чтобы не вызывать частые прерывания неисправности страницы. После этой оптимизации плюс некоторые оптимизации GC могут быть достигнуты 126 Вт TPS. Общий план введен.
Другие оптимизации
Также есть некоторые оптимизации, которые мало влияют на общий процесс, поэтому они будут представлены отдельно.
Для 2-этапного случайного обнаружения индекса и 3-этапного последовательного потребления могут быть приняты разные стратегии.2-этапный этап может напрямую считывать необходимые данные без кэширования (поскольку это случайное обнаружение, кэш чтения определенно не попадет).
Сделайте количество файлов параметром и настройте параметр, чтобы определить, является ли это многофайловым высоким TPS или одиночным файлом.На самом деле, после тестирования обнаружено, что разрыв не очень большой, а эффект одного файла немного лучше Потому что это облачный диск SSD и нет магнитной головки, поэтому я действительно не понимаю принципа.
Оптимизация GC, не используйте список, где можно использовать массивы. Сведите к минимуму появление мелких объектов Массивы можно использовать для управления базовыми типами данных Маленькие объекты очень недружественны для gc Будь то предварительный раунд или повторный матч, Java всегда является одним из механизмов сборки мусора после Cpp. Необходимо следить за тем, чтобы во всем процессе не появлялся полный gc.
Неудачная оптимизация и отражение
Этот конкурс - это большое сожаление, потому что оптимизация письма не была выполнена хорошо. После того, как прочитанный кеш проводится, общее время, проведенное во втором и третьем этапах, составляет 400 + с, что является хорошим результатом. Но написание занимает 1300 + с. Вышеуказанная схема, которую я использую, это многопоточная синхронная щетка, но я также пробовал следующие схемы записи:
- Асинхронный буфер записи отправки, однопоточная кисть
- Асинхронно отправить буфер записи, установить вторичный буфер на 64 КБ ~ 64 МБ и использовать вторичный буфер для очистки диска с помощью одного потока.
- Синхронно копируйте данные из буфера записи в LockFreeQueue и плавно используйте их в одном потоке для заполнения IOPS.
- Каждые 16 очередей совместно используют буфер записи, так что управляющий буфер записи может достигать 64 КБ, сортировать при сбросе и объединять данные одной и той же очереди.
Но все они закончились провалом, нет доступа к основам написания оптимизации, что является самым большим сожалением этого конкурса.
Другая ошибка заключается в том, что облачный диск SSD, используемый в оценочной среде, слишком отличается от структуры хранилища SSD под моим локальным Mac, а также некоторые пробелы между mac os и Linux, что приводит к успешной локальной оптимизации, которая вообще не может быть отражена в сети, или это надежнее арендовать облачную среду Alibaba.
С другой стороны, отражение не знакомо с дизайном архитектуры хранилища и MQ. Некоторые оптимизации, сделанные Kafka и RocketMQ, также используются сейчас, и я не уверен, что использование правильное, что приводит к некоторым обходным путям. Wang Yapu, a Мальчик 1996 года, которого я встретил на конкурсе, действительно восхищается глубиной и широтой своего понимания промежуточного программного обеспечения, и ему еще предстоит многому научиться.
Конкурентные идеи
Первое чувство утомляет, второе чувство освежает. Я считаю, что многие игроки являются рабочей группой, как и я. Они работают днем и могут найти время для соревнований только ночью. Я так недружелюбен к 966. Один раз продлить предварительный раунд - это облегчение, а матч-реванш - это мгновение ока, все кончено, у меня нет шансов вернуться, очень жаль. Круто то, что этот конкурс действительно потел и практиковал много технологий, связанных с промежуточным программным обеспечением.Нетти в предварительном конкурсе и дизайн хранилища в полуфинале - все это незабываемые воспоминания.Я также встретил много друзей во время конкурса, в том числе студенческих вечеринок. , есть рабочая группа, спасибо за ваше неутомимое обучение и наводящие на размышления дискуссии, вы действительно можете получить много знаний, которых вам не хватает, от разных людей.
Судя по новостям, конкурс промежуточного программного обеспечения Али, вероятно, будет последним. Независимо от причины, как участник, я чувствую глубокое сожаление. Я надеюсь, что у меня будет возможность участвовать в следующем конкурсе промежуточного программного обеспечения. Я также смотрю Это прекрасное чувство — видеть больше подобных мероприятий, проводимых крупными интернет-компаниями, соревноваться с большими парнями на одной сцене и встречать новых друзей.
Хотя в итоге я пропустил финал, я все еще с нетерпением жду 11 участников, которые вышли в финал, чтобы показать прекрасную защиту, а также ответить на план написания, который я всегда оптимизировал и терпел неудачу. В последующем мы рассмотрим возможность использования идей оптимизации лучших JAVA и организуем их в окончательное и совершенное решение. Git-адрес текущего решения, репозиторий стал общедоступным:code.aliyun.com/250577914/Пожалуйста…
Добро пожаловать в мою общедоступную учетную запись WeChat: «Обмен технологиями Кирито». На любые вопросы по статье будут даны ответы, что позволит расширить обмен технологиями, связанными с Java.