«Интервью», чтобы получить письмо о намерениях от станции Б

Это путешествие на собеседование по разработке сервера Bilibili можно охарактеризовать как захватывающее, но благодаря овладению большинством процедур вопросов на собеседовании я выиграл его без происшествий Давайте посмотрим, являются ли эти неряшливые вопросы обычным явлением и не могут ли они больше быть обычными. Вы можете прочитать эти вопросы интервью? Конечно нет, просто используйте эти вопросы, чтобы понять, чего не хватает и какие материалы можно посмотреть.

1 Относится к операционной системе

• В чем разница между спин-блокировкой и общей блокировкой? Зачем использовать спин-блокировки?

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

Каковы общие проблемы со спин-блокировками?

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

Так в чем же разница между спин-блокировками и другими блокировками?

Из состояния потока состояние спин-блокировки — run-run-run. Состояние не-спин-блокировки работает---блокировка---выполняется, поэтому спин-блокировка будет более эффективной.

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

Итак, как реализовать спин-блокировку в Java

public class SpinLock {
    private AtomicReference<Thread> cas = new AtomicReference<Thread>();
    public void lock() {
        Thread current = Thread.currentThread();
        // 利用CAS
        while (!cas.compareAndSet(null, current)) {
            // DO 
        }
    }
    public void unlock() {
        Thread current = Thread.currentThread();
        cas.compareAndSet(current, null);
    }
}

В приведенном выше коде CAS, используемый блокировкой метода, когда поток A получает блокировку, успешное получение не войдет в цикл while. Если поток A не снимет блокировку в это время, когда поток B получит блокировку, потому что он не удовлетворяет CAS, он войдет в цикл whilei и будет непрерывно оценивать, удовлетворен ли CAS, пока поток A не вызовет команду unlock, чтобы освободить ее.

Каковы преимущества спин-блокировок?

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

• Узнайте, какие модели ввода-вывода?

Сначала организуйте модель ввода-вывода, а затем подробно опишите модель ввода-вывода, с которой я знаком, и представьте сценарии приложений.Этот установленный X относительно совершенен.Конкретный и очень подробный в следующей статье, вот краткое введение. Эта часть была подробно объяснена в предыдущей статье

блокировка ввода-вывода

Мы знаем, что при вызове функции есть только два случая, либовернуться немедленно, а затем выполните следующую бизнес-обработку в соответствии с возвращаемым значением. когда используешьблокировка ввода-вывода, приложение будет безжалостновешать, ожидая завершения операции ядром, потому что ядро ​​в это время может переключить процессорное время на другие нужные процессы, и наше приложение как будто зависло (заблокировано).

Неблокирующий ввод-вывод

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

Модель повторного использования ввода-вывода

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

Сигнальный ввод-вывод

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

Асинхронный ввод-вывод

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

• Расскажите о разнице между select и epoll?

Та же процедура здесь, сначала укажите использование двух, а затем преимущества и недостатки двух.

Недостаток выбора

• select возвращает массив, содержащий весь дескриптор, и приложению необходимо просмотреть весь массив, чтобы узнать, какие дескрипторы имеют события.
• Триггерный метод выбораГоризонтальный триггер, если приложение не завершает операцию ввода-вывода над готовым файловым дескриптором, то каждый последующий вызов select все равно будет уведомлять процесс об этих файловых дескрипторах
• Проблема копирования памяти ядра/пользовательского пространства, select будет изменять структуру данных дескриптора, установленную в ядре каждый раз, поэтому каждый раз, когда вызывается select, все структуры данных дескриптора необходимо копировать из пользовательского пространства в пространство ядра, что приводит к огромным накладным расходам.
• Количество отдельных процессов можно отслеживать дескриптор файловСуществует максимальный предел, обычно 1024, количество конечно можно изменить

реализация epoll

epoll будет поддерживатькрасно-черное деревоиДвусвязный список, красно-черное дерево хранит события, добавленные в объект epoll через метод epoll_ctl, поэтому нет необходимости копировать все структуры событий каждый раз, когда вызывается epoll_wait. В двусвязном списке хранятся готовые события.Все события, добавленные в epoll, установят отношение обратного вызова с драйвером устройства (сетевой карты), то есть этот метод обратного вызова будет вызываться при возникновении соответствующего события.Этот метод обратного вызова называется ep_poll_callback в ядре это добавит событие в двусвязный список rdlist. Вызов epoll_wait напрямую вернет событие готовности в связанном списке, что очень эффективно.

• Выбор подходит для небольшого количества активных соединений, обычно несколько тысяч.

• epoll подходит для большого количества менее активных подключений.

• Вы понимаете оптимистическую блокировку и пессимистическую блокировку?

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

Что такое пессимизм и оптимизм, мы не должны быть оптимистичными при интервьюировании. Я хочу дать на интервью волну официальных объяснений, а затем почти такую ​​же волну просторечных объяснений.

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

• Что такое проникновение в кеш? Как этого избежать? Что такое кэш-лавина? Как этого избежать?

проникновение в кеш

Вообще говоря, система кэширования будет использовать ключ для кэширования запроса. Если соответствующего значения нет, он должен обратиться к серверной системе (например, БД), чтобы найти его. В это время, если придут какие-то вредоносные запросы, он будет намеренно запрашивать несуществующий ключ.Когда количество запросов в определенный момент очень велико, это вызовет большую нагрузку на серверную систему. Это называется проникновением в кэш.

Как этого избежать?

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

Кэш Лавина

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

Как этого избежать?

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

В качестве кеша второго уровня A1 является исходным кешем, A2 — кешем копии, и когда A1 выходит из строя, вы можете получить доступ к A2.Время аннулирования кеша A1 установлено на краткосрочный период, а A2 — на долгосрочный.

Для разных ключей установите разное время истечения срока действия, чтобы сделать момент аннулирования кеша как можно более однородным.

2 редис связанных

Если вы являетесь интервьюером на стороне сервера / на стороне сервера, вы все равно можете найти книгу Redis, чтобы увидеть ее, вероятность ее возникновения настолько велика, не забывайте помнить. Посмотрим, какие вопросы задают на станции Б.

• Вы понимаете стратегию исключения и удаления Redis?

Можете ли вы сказать, что не понимаете? Даже если вы не слышали об этом, вы можете сказать: «Извините, интервьюер, это не очень глубоко, но я понимаю Барабару буквально», так что как бы не запутаться. Давайте посмотрим на стратегию кэширования Redis.

Redis В Maxmemory Parations, установленные верхним пределом использования памяти, Redis, если максимальное использование памяти превышает набор, он будет удален путем выбора файлов конфигурации ключей политики, чтобы быть удалены, что оставив место для новых ключей. Шесть из главной ключевой стратегии

1. volatile-lru

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

2. allkeys-lru

Удалить последний использованный ключ

3. volatile-random

Установите время истечения срока действия в ключевом пространстве и удалите ключ случайным образом

4. allkeys-random

Случайно удалить ключ

5. noeviction

Когда использование памяти достигает порогового значения, все команды, вызывающие использование памяти, будут сообщать об ошибке;

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

1. Регулярно удалять

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

2. ленивое удаление

Проверяйте срок действия ключа каждый раз, когда вы получаете ключ из пространства ключей, если он истекает, удаляйте его.

3. регулярно удалять

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

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

3 mysql

• Какая блокировка mysql используется? При использовании блокировки строки, когда он будет использовать блокировки таблицы?

Блокировка строки в InnoDB реализована элементом индекса в индексе.Основная особенность заключается в том, что INNODB будет использовать блокировку строки только при извлечении данных по условиям индекса, в противном случае INNODB будет использовать блокировку таблицы.

Обратите внимание, что в Mysql блокировки на уровне строк являются не блокировочными записями, а индексами. Существует два типа индексов: индексы первичного ключа и индексы непервичного ключа. Если в операторе манипулируют индексом непервичного ключа, Mysql заблокирует индекс непервичного ключа, а затем заблокирует соответствующий индекс первичного ключа.

• Слышали ли вы о гэп-локах? Как определяется диапазон блокировки гэп-лока?
• Вы знаете о B+ деревьях? Когда произойдет разделение узла в дереве B+?

Этот ответ был подробно описан в дереве B+ предыдущей статьи. Кратко опишите здесь

1. Разделите полный узел, сгенерируйте новый узел из узла M/2 после полного узла и укажите первый элемент нового узла на родительский узел.
2. Родительский узел кажется заполненным, а родительский узел продолжает быть разделенным.
3. Всегда разделяйте, если корневой узел заполнен, корневой узел необходимо отсортировать, а высота дерева в это время увеличивается.

• База данных зависает до того, как транзакция будет выполнена, что произойдет, когда она перезапустится?
• Что такое журналы отмены и журналы повтора?

журнал повторов журнал повторов — это уровень механизма хранения InnDB, используемый для обеспечения безопасности транзакций. Перед тем, как транзакция будет зафиксирована, каждая операция модификации будет записывать измененные данные и сохранять данные физического журнала, чтобы предотвратить временной момент сбоя, если есть грязные страницы, которые не записаны на диск, при перезапуске mysql, журнал повторов используется для перезапуска, чтобы обеспечить устойчивость транзакций

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

• Простой разговор о реализации принципа базы данных MVCC?

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

• Когда будет использоваться журнал binlog mysql?

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

1. Режим 1-рядный режим

Данные каждой строки изменяются и записываются в журнал, а затем те же данные изменяются в ведомом сегменте. Например, «обновить xx, где идентификатор в (1,2,3,4,5)», при использовании этого режима будет записано 5 записей.

2. Режим 2 - режим заявления

SQL-запрос, изменяющий данные, будет записан в бинлог мастера. Когда ведомое устройство реплицируется, поток sql будет разобран на тот же sql, выполненный исходным мастером и выполненный здесь.

3. Режим 3 - смешанный режим

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

Краткое описание процесса:

Мастер будет записывать журнал binlog после выполнения операции добавления, удаления и модификации. Когда требуется синхронизация, он будет активно уведомлять подчиненный узел. После получения уведомления ведомый будет использовать IO THREAD для активного чтения binlog и записи в владелец.relaylog (журнал транзита), а затем заставить SQL THREAD завершить анализ журнала ретрансляции, а затем операцию хранения для завершения синхронизации.

4 Основные структуры данных

• При использовании LRU, если есть большой объем данных, которые используются только один раз за короткий период времени, это может привести к удалению большого количества часто используемых кэшей.Есть ли какое-либо решение?
• Вы слышали о круговых связанных списках? Как рассчитывается его длина?

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

• Какая структура данных может поддерживать быструю вставку, удаление, поиск и т. д.?

Размышляя об этой проблеме, мы часто вспоминаем хороший бинарный поиск, который опирается на характеристики случайного доступа к массивам, а его временная сложность поиска составляет O(log n). Хорошо ли работает бинарный поиск, если мы помещаем элементы в связанный список? Это таблица пропусков, которой я делюсь с вами сегодня.

Понимание таблицы пропуска

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

Чтобы найти элемент в связанном списке, естественно пройти с самого начала, чтобы найти элемент, который нужно найти.Временная сложность в это время составляет O (n). Итак, какой метод можно использовать для повышения эффективности запроса? Вопрос в добавлении индекса, как добавить, извлекаем из этой части данных несколько элементов в виде отдельного связанного списка, как показано на следующем рисунке]

Предполагая, что в этот момент мы ищем элемент 16, мы сначала ищем по индексу первого уровня.Когда элемент 14 найден, значение следующего узла равно 18, что означает, что искомое число находится в середине из этих двух чисел. В этот момент переместитесь непосредственно вниз от указателя узла 14 к исходному связанному списку ниже и продолжайте движение, просто следующий элемент — это 16, которые мы ищем. Итак, давайте подытожим, если мы находим элемент 16 из исходного связанного списка, нам нужно пройти и сравнить 8 раз.Если мы ищем по индексному связанному списку, нам нужно только 5 раз.

Мы продолжаем находить элемент 16, после чего количество сравнений становится равным 4. Таким образом, количество добавлений слоя индексного поиска уменьшается.Если элементов n, сколько индексов?

Предполагая, что мы извлекаем один узел в качестве индексного узла предыдущего уровня в соответствии с каждыми двумя узлами, количество узлов в первом слое равно n/2, количество узлов во втором слое равно n/4, а количество узлов узлов в индексе x-го уровня составляет 1/2 от количества узлов в индексе x-1-го уровня, тогда количество узлов индекса x-го уровня равно n/(2^x). Предполагая, что индекс имеет y уровней, мы можем получить n/(2^y)=2, что приводит к y=log2n-1.

Так много индексов пустой тратой памяти?

Предполагается, что исходный список размером n, что индекс первого уровня составляет приблизительно n/2 узлов, индекс второго уровня составляет приблизительно n/4 узлов и т. д., каждый из них в восходящей половине сокращается до 2 узлов. Если мы выпишем количество узлов в каждом индексе, это будет геометрическая прогрессия. Сумма этих индексов на уровне узла составляет n/2 + n/4 + n/8... + 8 + 4 + 2 = n-2. Следовательно, сложность таблицы прыжков в космос составляет O (n). Это не может уменьшить некоторые из них. Предположим, вы должны рассматривать три узла на узел как индекс для извлечения списка узлов.

Списки переходов и бинарные деревья поиска

Временная сложность поиска для обоих O(logn) Каковы преимущества таблицы пропуска?

Сначала посмотрите на бинарное дерево поиска,

Эта структура приведет к тому, что эффективность поиска бинарного дерева поиска станет равной O(n).

Стол для прыжков с красно-черным деревом

Если честно, красно-черное дерево действительно сложнее.Во время интервью вас попросили написать о красно-черном дереве, а вы на него наговорили?

Красно-черное дерево должно вращаться влево и вправо, чтобы поддерживать баланс размера дерева. Таблица пропуска поддерживает вышеупомянутый «баланс» с помощью случайной функции. Когда мы вставляем данные в таблицу пропуска, мы можем одновременно вставлять эти данные в часть индексного слоя. Как выбрать, к каким индексным слоям присоединиться? Мы используем случайную функцию, чтобы решить, в какой уровень индексов вставить этот узел.Например, если случайная функция генерирует значение K, то мы добавляем этот узел в индекс K-уровня с первого уровня до K-го уровня. Когда мы вставляем данные в таблицу пропуска, мы можем одновременно вставлять эти данные в часть индексного слоя.

резюме

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

• Вы обычно любите читать технические блоги? Поделитесь последним техническим блогом? Вы обычно ездите на станцию ​​B?

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

Интервьюер: Я потираю, я обратил внимание на то, что сказала Нима, неудивительно, что вы можете сказать раз, два или три, когда я что-то спрашиваю.

5 Резюме

Обратите внимание на следующие моменты:

• Компания набирает вас на работу, и не снизит стандарт ваших требований из-за того, что вы делаете.
• Написание кода на инструменте полностью отличается от разрыва кода вручную.
• Цените каждую возможность интервью и учитесь анализировать.
• Для первокурсников основной проверкой является овладение базовыми компьютерными знаниями.Требования к проекту не столь высоки.Если делать самому,то придется много работать над деталями и делать тесты.Только так вы будете знать какие задачи вам предстоит решать. столкнуться, с какими трудностями вы столкнетесь и как их решить. . Чтобы мы могли говорить красноречиво.
• Не бойся неклассов, если будешь бояться, то проиграешь! Должен попробовать больше.

---

Я Сяо Лан, синий человек, который делится опытом интервью со всеми. Если вы считаете, что статья хороша или полезна для вас, спасибо, что поделились ею с друзьями, или вы можете поставить Xiaolan лайк ниже, это очень важно для Xiaolan, спасибо, увидимся в следующем выпуске.