сказка
Теперь предположим, что вы читаете эту статью и возвращаетесь во второй класс начальной школы, в это время вы постоянно гоняетесь за Сяохуном, старостой следующего класса, и вам не терпится отдать ТА все дома. Итак, вопрос в том, если вы хотите отнести все вещи в доме в Сяохун, сколько у вас есть способов? Вот что я придумал
- Передвигайте по одному, если не можете передвинуть, то разделите (не исключается вероятность того, что вас побьют родители)
- Попытка превратить себя в сильного мужчину, принимая лекарства
Приведенный выше пример может показаться забавным, но на самом деле это решение, которое люди решали для крупномасштабных количественных задач, то есть либо для улучшения своей способности справляться с крупномасштабными величинами, либо для разделения и разделения и завоевания. .
В соответствии с ИТ-индустрией из-за ограниченной вычислительной мощности традиционных мини-компьютеров существуют мэйнфреймы. Что делать, если вам не нужен мейнфрейм? Нам пришлось разделить сервисы, поэтому у нас были микросервисы.
Классические вопросы интервью
интервьюер: Предположим, у вас есть только 100M доступной памяти, и теперь есть файл размером 1G, в котором хранятся целые числа, и каждое целое число хранится в 4 байта.Если вы хотите отсортировать данные в этом файле, какое решение вы есть?
я: Позвоните девушке-администратору и попросите у нее один8GКарта памяти DDR4, чтобы выразить ей благодарность, я попросил ее выйти на ужин, может быть, она сможет гладко отделаться от заказа.
интервьюер: Эммм….., вернуться и так далее.
решение
я: Чтобы решить эту задачу, сначала нам нужно разделить на два случая:
Данные не повторяютсяЕсли данные не повторяются, мы можем использовать растровое изображение, чтобы пометить соответствующие данные, и перемещаться по растровому изображению, когда нам нужно вывести результат (эта схема относительно проста и выходит за рамки этой статьи).
дублирование данныхПоскольку доступно только 100M памяти, полное использование этих 100M памяти означает, что мы можем отсортировать 26214400 целых чисел (100 * 1024 * 1024/4 ) за раз, а это значит, что мы должны читать файл поэтапно и читать Сортировать содержимое каждой сортировки и сохранять результаты каждой сортировки в файловую систему, а затем объединять эти файлы.
интервьюер: Можете ли вы показать это с рисунком?
я: Процесс показан на рисунке ниже
интервьюер: Да почему бы вам не написать код на месте?
Реализация решения
Реализация решения обычно состоит из следующих шагов
Согласно количеству данных, соответствующих размеру прочитанного буфера, и поместите их в массив целых чисел, отсортированные и записаны в файл, этот шаг повторяется до тех пор, пока не будет читать исходные данные.
Объединяйте эти отсортированные файлы, пока не останется только один файл
Разбирая проблему, нам нужно решить следующие подзадачи
- Поскольку мы используем 4 байта данных для хранения целых чисел, нам нужно решить проблему доступа к целым числам по байтам
Вы можете подумать, почему мы используем четыре байта для доступа к целым числам вместо того, чтобы преобразовывать их в строки.
- Алгоритм объединения отсортированных файлов
Вариант 1. Предварительно прочитать часть данных и записать в кэш, а затем выполнить сортировку слиянием (данные в разделенном файле в порядке), когда данные израсходуются, прочитать их из файла и повторить этот шаг, пока нет данных для чтения
Схема II, время, когда файл читается из двух целого числа, по сравнению, а затем больше / меньше (в зависимости от вы хотите увеличить или убывать порядок) данных, записанных в файл.
Вариант 1 относительно прост и быстр для всех.
Что касается второго решения, поскольку в недавней разработке задействован конечный автомат, для второго решения я принял шаблон проектирования конечного автомата для его реализации.
Государственная машина выглядит так
Чтобы дать вам ссылку, решение, которое я реализовал, еще имеет место для дальнейшей оптимизации 😄
контрольная работа
Для наглядности сортируем файл размером 16мб, буфер выставляем 512кб.
Ниже приведены результаты испытаний
-
На этапе разделения файлов видно, что время, используемое для разделения файлов, аналогично
-
На этапе объединения видно, что время, необходимое для объединения отсортированных файлов, постоянно увеличивается, поскольку размер объединенных файлов постоянно увеличивается.
Что, если мы прямо установим буфер равным 16 МБ? Ниже приведены результаты теста, даже фаза слияния не используется.
интервьюер: Очень хорошо, тогда можете назвать сценарий применения?
я: Сортировка файлом (sort) работает = filesort, вроде где-то видел...
интервьюер: подсказывает вам словоexplain
FileSort
я: Если подумать, скажем, у нас есть стол
CREATE TABLE `users` (
`id` int(11) NOT NULL,
`account` varchar(45) COLLATE utf8mb4_bin DEFAULT NULL,
`nickname` varchar(45) COLLATE utf8mb4_bin DEFAULT NULL,
`password` varchar(45) COLLATE utf8mb4_bin DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin
Если нам нужно продолжить сортировку по полю, а индекс не добавляется, то используйтеexplainЕсли запрос SQL будет виден в Дополнительныхfilesort
Как показано ниже
Это означает, что MySQL не может сортировать данные по индексу (если есть индекс, просто получить его напрямую, операция сортировки не требуется).
Мне нужно отсортировать поля для сортировки, но объем данных в производственной среде может быть очень большим.Если все данные будут загружены в память, это неизбежно приведет к нехватке памяти и вызовет сбой базы данных.Поэтому для сортировки должна быть выделена специальная область памяти. , и эта область памяти может не вместить такой огромный объем данных, поэтому она должна быть отсортирована внешней файловой системой, котораяfilesortпроисхождение
интервьюер: Очень хорошо, тогда вы умеете видеть размер этой памяти?
я: буфер =buffer, в соответствии с последовательной традицией mysql следующий оператор должен быть в состоянии найти
show variables like '%buffer%'
(Область, отмеченная синим цветом на рисунке,
sort_buffer_size)
интервьюер: Очень хорошо, тогда вы знаете, как его оптимизировать?
я: Проиндексированные пение, но также Zeyang или вызов на серверную работу и обслуживание плюс палку памяти? Или завод зубной пасты (Intel) процессора в CPU фермы (AMD! Да)
интервьюер: Пока тебе нравится AMD, мы сводные братья. О, нет, я спрашивал, как добавить индекс
я: Мы знаем, что индекс в порядке.Если информация по индексу уже удовлетворяет наши потребности, то нет необходимости использовать filsort.
Например, упомянутая выше таблица пользователей
мы создали индекс
alter table users add index(nickname, account)
Подумайте, требует ли следующий оператор сортировки файлов.
select nickname,account from users order by nickname
select * from users order by nickname
select * from users order by account
ответ
- Первый оператор не нуждается в файловой сортировке, потому что индекс уже содержит нужную нам информацию.
- Второй оператор может напрямую использовать индекс (индекс хранится упорядоченным образом). После считывания значения первичного ключа, соответствующего индексу, соответствующие данные могут быть извлечены и возвращены непосредственно клиенту. Нет необходимости использовать
sort_buffer
- Третье утверждение требует
filesort, но поскольку учетная запись и псевдоним объединены в индекс, учетные записи, соответствующие каждому псевдониму, упорядочены, поэтому учетные записи, соответствующие разным псевдонимам, могут использоваться для сортировки слиянием (как упоминалось выше на этапе слияния).
Суммировать
Сегодняшнее резюме на трех цифрах
приложение
Q1: Зачем использовать 4 байта для хранения целых чисел
Экономьте место, если вы используете строки для хранения, у вас будет столько байтов, сколько целых чисел.
Q2: Как использовать внешнюю сортировку DEMO, представленную в этой статье
Три файла в исходном коде
- распечатать данные из файла
- Сортировка указанного файла
- Создать файл случайных чисел
Q3: Зачем использовать конечный автомат для реализации сортировки слиянием
Должен сказать, что использование конечного автомата для разбора логики относительно понятно, советую и вам попробовать. Но в этом случае производительность будет намного выше, если вы используете буфер для хранения целочисленного массива.
использованная литература
«Высокопроизводительный MySQL (третье издание)»
Части, связанные с индексом
«Дорога к королю MySQL»
Раздел 3.4