предисловие

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

Важность индексов

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

Индекс БД в инженерной сфере еще более незаменим, без индекса сложно представить, как получить такой огромный объем данных.

После выяснения важности индексов давайте посмотрим, как индексы реализованы в Kafka.

Практика индексации в Kafka

Первый индекс Кафкиразреженный индекс, что может помочь индексному файлу не занимать слишком много памяти, так чтоДержите больше индексов в памяти. Соответствует параметрам на стороне брокераlog.index.interval.bytesValue, значение по умолчанию равно 4 КБ, то есть индекс строится для сообщений размером 4 КБ.

В Kafka существует три основных типа индексов: индексы смещения, индексы временных меток и индексы прерванных транзакций. Соответствует файлам .index, .timeindex и .txnindex соответственно.

Соответствующий исходный код выглядит следующим образом:

1. AbstractIndex.scala: абстрактный класс,Инкапсулирует общие операции для всех индексов

2. OffsetIndex.scala: индекс смещения,Соотношение между значением смещения и физическим положением соответствующего диска сохраняется.

3, Timeindex.scala: индекс времени отметки,Соотношение между отметкой времени и соответствующим значением смещения сохраняется.

4. TransactionIndex.scala: индекс транзакций, который появится после включения транзакций Kafka (на данный момент эта статья не охватывает контент, связанный с транзакциями).

Давайте посмотрим на определение AbstractIndex.

Определение AbstractIndex было прокомментировано в коде, а также есть переменная-членentrySize. Эта переменная на самом деле является размером каждого элемента индекса, а размер каждого элемента индекса фиксирован.

entrySize

существуетOffsetIndexсредний даoverride def entrySize = 8, 8 байт. существуетTimeIndexсредний даoverride def entrySize = 12, 12 байт.

Почему 8 и 12?

существуетOffsetIndexКаждый элемент индекса хранит значение смещения и соответствующее физическое положение диска, так что 4 + 4 = 8, но это не правильно, физическое положение диска - это целое число, без проблем, ноAbstractIndexС точки зрения определения baseOffset, смещение представляет собой длинное целое значение, а не потому, что 8 байт?

следовательноСохраненное значение смещения на самом деле является относительным значением смещения.,СейчасЗначение истинного смещения - значение baseOffset.

Является ли относительное смещение целочисленным хранилищем? Достаточно, потому что параметр размера файла сегмента журналаlog.segment.bytesЭто целое число, и поэтому разница между значением смещения и значением -baseOffset сегмента журнала, соответствующего тому же индексному файлу, в диапазоне целых чисел положительна.

Почему так сложно сохранить разницу?

1. Для экономии места запись индекса экономит 4 байта, подумайте о тех компаниях, которые обрабатывают триллионы сообщений в день.

2. Поскольку ресурсы памяти очень ценны, чем короче элемент индекса, тем больше элементов индекса может храниться в памяти, а вероятность прямого попадания тем выше, чем больше элементов индекса. На самом деле это то же самое, почему MySQL InnoDB рекомендует, чтобы первичный ключ не был слишком длинным. Каждый вторичный индекс хранит значение первичного ключа.Чем длиннее первичный ключ, тем больше памяти занимает каждая запись индекса, тем меньше число индексов, получаемых с диска для страницы кэша за раз, и тем больше раз запрос должен получить доступ к диску. А доступ к диску, как мы все знаем, медленный.

Исходный код взаимного преобразования выглядит следующим образом, это такая простая операция:

Вышеприведенное объясняет, что значение смещения составляет 4 байта, поэтомуTimeIndexСредняя временная метка 8 байт + значение смещения 4 байта = 12 байт.

_warmEntries

Для чего это?

Прежде всего, подумайте о том, как мы можем быстро найти сообщения в сегменте журнала с помощью записи индекса, но как мы быстро найдем нужную запись индекса? Индексный файл по умолчанию имеет размер 10 МБ, а размер элемента индекса — 8 байт, поэтому файл может содержать более 100 W элементов индекса.

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

Тогда давай два очка!

с участием_warmEntriesкаковы отношения? Прежде всего, в чем проблема с двумя точками?

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

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

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

when looking up index, the standard binary search algorithm is not cache friendly, and can cause unnecessary page faults (the thread is blocked to wait for reading some index entries from hard disk, as those entries are not cached in the page cache)

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

Комментарии также дружелюбны, чтобы привести примеры

Проще говоря, предположим, что индекс занимает 13 страниц кэша страниц, а данные в это время записаны на 12 страниц. Согласно характеристикам доступа kafka данные, к которым обращаются в это время, находятся на 12-й странице, поэтому характеристики бинарного поиска, порядок доступа к страницам кеша в это время 0, 6, 9, 11, 12. Поскольку к ним часто обращаются, эти страницы должны существовать в кэше страниц.

Когда Page 12 продолжают заполнить, подать заявку на новую страницу на стр. 13, чтобы сохранить запись индекса после полной, а в соответствии с характеристиками двоичного поиска, в котором кэшированные кэшированные страницы кэшированных страниц доступа: 0,7,10 12 Этот 7 и 10 не был доступен, и, скорее всего, больше не в кэше, а затем нужно прочитать данные с диска. Комментарий сказал:В их тестах это привело как минимум к скачку задержки с нескольких миллисекунд до 1 секунды.

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

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

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

Что ж, давайте сначала посмотрим, как сделан исходный код

Это не сложно реализовать, но зачем использовать 8192 сзади как горячую зону?

Здесь стоит еще раз упомянуть исходный код, очень хорошо сказано.

1. This number is small enough to guarantee all the pages of the "warm" section is touched in every warm-section lookup. So that, the entire warm section is really "warm". When doing warm-section lookup, following 3 entries are always touched: indexEntry(end), indexEntry(end-N), and indexEntry((end*2 -N)/2). If page size >= 4096, all the warm-section pages (3 or fewer) are touched, when we touch those 3 entries. As of 2018, 4096 is the smallest page size for all the processors (x86-32, x86-64, MIPS, SPARC, Power, ARM etc.).

 大致内容就是现在处理器一般缓存页大小是4096，那么8192可以保证页数小于等3，用于二分查找的页面都能命中

2. This number is large enough to guarantee most of the in-sync lookups are in the warm-section. With default Kafka settings, 8KB index corresponds to about 4MB (offset index) or 2.7MB (time index) log messages.

 8KB的索引可以覆盖 4MB (offset index) or 2.7MB (time index)的消息数据，足够让大部分在in-sync内的节点在热区查询

Вышеизложенное объясняет, что такое_warmEntries, а зачем это нужно_warmEntries.

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

От горячего и холодного разделения индекса Kafka до управления буферным пулом MySQL InnoDB.

Из приведенной выше волны горячих и холодных разделов я подумал об управлении буферным пулом MySQL. MySQL делит пул буферов на новое поколение и старое поколение. По умолчанию 37 баллов, то есть на старое поколение приходится 3, а на молодое поколение 7. То есть 30 % хвоста связанного списка — это старое поколение, а первые 70 % — новое поколение.Заменяет стандартный механизм устранения LRU.

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

1. Ошибка предварительного чтения: Поскольку страница предварительного чтения будет предварительно прочитана, предполагая, что страница предварительного чтения не будет использоваться, предварительное чтение будет напрасным.Поэтому страница предварительного чтения вставляется в глава старости, и ликвидация также устраняется с окончанием старости. Данные нового поколения не будут затронуты.

2. Загрязнение кэша. При подобном полном сканировании таблицы будет прочитано много холодных данных. И некоторые частоты запросов на самом деле очень низкие, поэтому это правильный выбор, чтобы эти данные существовали только в старости, а затем быстро удаляли их.Для решения этой проблемы у MySQL недостаточно только генерации, а также устанавливает временное окно, по умолчанию 1 с, то есть, когда к старому поколению снова обращаются и существует более 1 с, оно будет повышено до нового поколения, так что горячие данные нового поколения не будут загрязнены.

резюме

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

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

Что не говори, простудился.