предисловие
Интервьюер: Мальчик, ты меня помнишь? Я был интервьюером, который брал у вас интервью в прошлый раз.
Я подумал про себя: иду, как же не вспомнить, я не юношеский слабоумие, в прошлый раз столько картинок нарисовал, и больше часа стучал в комп, мой разум полон твоей тени .
Я: Помню, здравствуйте, я очень рад, что могу продолжать обмениваться с вами техническими вопросами через вторую сторону.
Неужели я могу сказать это против своей совести, скажем один раз, неужели так сложно взять интервью?
Интервьюер быстро просмотрел резюме, наверное, прошло больше недели с тех пор, как я видел его в последний раз, видимо, он забыл мое резюме.
Интервьюер: Я вижу в вашем резюме, что вы глубоко разбираетесь в дистрибутиве, и вы также работали над распределенными проектами, что хорошо.Знаете ли вы, как генерировать распределенные идентификаторы в распределенных проектах?
Я: Я знаю, что в основном существуют следующие методы генерации распределенных идентификаторов:
- Идентификатор автоинкремента базы данных.
- База разбивается по горизонтали, устанавливается начальное значение и такой же шаг автоинкремента.
- Подайте заявку на автоматическое увеличение идентификаторов в пакетном режиме.
- Генерация UUID.
- Путь Редиса.
- Алгоритм снежинки.
- Алгоритм Baidu UidGenerator
- Алгоритм Meituan Leaf
Интервьюер: О, да, вы можете так много говорить.Можете ли вы рассказать о своем анализе и понимании каждого из вышеперечисленных методов?
Я подумал про себя: иду, неловко сейчас, их так много, я только основные знаю, как же мне понять и углубить каждое, и сразу столько сказать, не это ли копать яму для сам?
Эй, нет возможности выйти и потусоваться, ты всегда должен отплатить, ты можешь только сказать, что знаешь это? Если вы не знаете, это, вероятно, грубо и пропущено.
Идентификатор автоинкремента базы данных
Я: Мммм, хорошо. Самоинкремент базы данных понять несложно, разработчики знают, что при создании таблицы нужно указывать первичный ключ.auto_increment(самоувеличение) может быть достигнуто.
Я: Но использование самоувеличивающегося идентификатора базы данных, хотя это и просто, приведет к проблеме дублирования идентификаторов, а идентификатор автономной версии самоувеличивается, и каждый раз, когда создается идентификатор, доступ к базе данных будет осуществляться один раз, и нагрузка на БД также велика, и о производительности Concurrency говорить нечего.
Интервьюер: Ну.
Я вижу,что интервьюер прислушивается ко вкусу.Время от времени я прикасаюсь к его редкому лбу,и его глубокие глаза выдают его спокойствие.В этом может быть прелесть зрелого архитектора.Пусть сколько отморозков читают "Программирование на Java" Мысль», «Основная технология Java», «Effectice java», «Практика параллельного программирования на Java», «Путь чистого кода», «Рефакторинг: улучшение дизайна существующего кода»… достиг, я беру жару Ударить железом, то ответ ниже.
База данных разбивается по горизонтали, устанавливая начальное значение и одинаковый размер шага автоинкремента.
Я: В ответ на вышеупомянутые проблемы с самоувеличивающимся идентификатором базы данных: повторение идентификатора, низкая производительность. Существует кластерная версия схемы распределенного идентификатора поколения."База данных разбивается по горизонтали, устанавливая начальное значение и одинаковый размер шага автоинкремента."и"Подать заявку на автоматическое увеличение идентификаторов в пакетном режиме".
Я:"База данных разбивается по горизонтали, устанавливая начальное значение и одинаковый размер шага автоинкремента."Это означает, что в среде кластера БД база данных делится по горизонтали, а затем каждая база данных устанавливается"разные начальные значения"и"одинаковый размер шага", чтобы избежать дублирования идентификаторов.
Интервьюер: Мальчик, извините, что прерываю, вы можете нарисовать картинку, я не понимаю, что вы имеете в виду?
Что делать?Нет абсолютно никакой возможности.Я могу только достать из кармана брюк ручку и бумагу и быстро нарисовать картинку.
Я: Здесь я предполагаю, что есть три базы данных, задаю начальное значение для каждой базы данных, а начальное значение можно установить с помощью следующего sql:
set @@auto_increment_offset = 1; // 设置初始值
set @@auto_increment_increment = 2; // 设置步长
Я: Начальные значения трех данных установлены соответственно на 1, 2 и 3. Как правило, размер шага устанавливается для данных базы данных.Здесь количество баз данных равно 3, поэтому размер шага также установлено значение 3.
Интервьюер: Что, если вы снова столкнетесь с ситуацией расширения мощностей?
Я: Ну, ситуация с расширением является недостатком этого метода. Размер шага, который я упомянул выше, обычно устанавливается в соответствии с количеством баз данных. Это делается для того, чтобы на более позднем этапе не было расширения. Если будет определено, что существует будет расширение на более позднем этапе, в ранней версии вы можете установить длину шага больше."Зарезервируйте некоторые начальные значения для последующего расширения".
Я: Вкратце, у этого решения есть плюсы и минусы, но есть и свои плюсы."На более позднем этапе вы можете столкнуться с дилеммой, что нет начального значения идентификатора, которое нужно отделить.База данных всегда является базой данных, и устойчивость к высокому параллелизму также ограничена.".
Я: Преимущество этого в том, что оно решено"Единственная проблема БД".
Интервьюер: Ну.
Подать заявку на автоматическое увеличение идентификаторов в пакетном режиме
Я:"Подать заявку на автоматическое увеличение идентификаторов в пакетном режиме"Решение может решить проблему невозможности разделения идентификатора, его принцип заключается в выделении пакета значений идентификатора в соответствующую базу данных для использования за один раз, а затем вернуться к применению после использования.
На этот раз я сознательно вынул из кармана брюк ручку и бумагу и нарисовал картинку ниже, история всегда так поразительно похожа.
Я: На начальном этапе проектирования вы можете создать таблицу с полем начального значения и полем шага. Когда вы хотите подать заявку на идентификатор партии, вы можете перейти к таблице, чтобы подать заявку. После каждого приложения"Начальное значение = предыдущее начальное значение + размер шага".
Я: Таким образом, начальное значение можно сохранить как максимальное значение идентификатора каждого приложения, избегая повторения идентификатора, и каждый раз, когда будет использоваться идентификатор, будет генерироваться пакет идентификаторов для использования в определенное время. время, так что количество обращений к базе данных значительно сокращается.
Я: Но у этого решения все еще есть свои недостатки, и оно все еще не может сопротивляться высокому параллелизму в истинном смысле этого слова.
Генерация UUID
я: Четвертый способ — использовать"Генерация UUID"Способ генерации распределенного идентификатора, основная идея UUID заключается в использовании"Сетевая карта машины, местное время, случайное число"для создания UUID.
я: способ использовать UUID просто нужно позвонитьUUID.randomUUID().toString()Его можно сгенерировать Этот метод удобен и прост, генерируется локально и не потребляет сеть.
Я: Простые вещи в то время вызывали больше проблем, что было бы неблагоприятно для хранения.16 байт и 128 бит, обычно представленные строками длиной 36 бит, не подходили для многих сценариев.
Я: И неупорядоченная строка, сгенерированная UUID, имеет низкую эффективность запросов, не имеет фактического бизнес-значения и не имеет функции самоувеличения, поэтому UUID не будет использоваться в качестве распределенного идентификатора.
Интервьюер: Ну, вы знаете, как генерировать UUID? Неважно, если вы не знаете, это просто расширение.
Я: это я знаю только может пройти"Текущая временная метка и MAC-адрес машины"Чтобы сгенерировать его, вы можете сделать так, чтобы сгенерированный UUID был уникальным в мире, а остальные не были поняты.
Интервьюер: Хм, все в порядке.
Путь Redis
Я: Чтобы решить проблему, связанную с тем, что описанная выше чистая реляционная база данных генерирует распределенные идентификаторы, которые не могут противостоять высокому параллелизму, можно использовать Redis для создания распределенных идентификаторов.
я: у самого Redis естьincrиincrebyТакие самоинкрементные команды обеспечивают атомарность, а сгенерированные идентификаторы также упорядочены.
Я: Redis основан на работе с памятью, обладает высокой производительностью, не зависит от базы данных, а данные упорядочены естественным образом, что способствует подкачке и сортировке.
Я: Но у этого решения также будут свои недостатки, потому что добавляется промежуточное программное обеспечение, а рабочая нагрузка по кодированию и реализации должна увеличиваться и усложняться.
Я: Способ использования Redis также учитывает постоянство.В Redis есть два типа постоянства."РБД и АОФ","RDB сохраняется в виде снимков, и данные от последнего снимка до этого времени будут потеряны.".
Я:"AOF может сохраняться один раз в секунду, а потерянные данные — в течение нескольких секунд.", также может быть проблема в том, что идентификатор в течение нескольких секунд после последнего автоинкремента не является постоянным.
Я: Но этот метод намного превосходит описанный выше метод создания распределенных идентификаторов для реляционных баз данных.
Я: Если объем данных относительно велик, перезапуск Redis займет много времени, и можно использовать кластерный метод Redis.
Интервьюер: Можете ли вы написать код инструмента Redis для создания распределенных идентификаторов?
Я раздавлен.Я больше всего боюсь рукописного ввода,потому что такие инструменты в основном пишутся один раз в начале проекта,а потом повторно используются в дальнейшем.Если я не могу его запомнить,то приходится писать от руки. Бар.
Я: Рукописный ввод не должен работать, потому что некоторые API не запоминаются, класс инструмента в основном пишется в начале проекта, а в продолжении я его не читал и специально не запоминал .
Я: Могу я воспользоваться твоим компьютером? Эти инструменты должны быть в состоянии быть напечатаны с помощью компьютера.
Опрашивающий: Да, вот вам компьютер, вы должны быть под этим тестовым заданием.
Я: Хорошо, спасибо.
Время идет.....
Примерно через несколько минут набора я потерял силы, и, наконец, я вырубил его.Есть много API, которые я не могу вспомнить, поэтому я могу только медленно их находить.Я написал два основных метода для генерации распределенных идентификаторов.
Первый заключается в использованииRedisAtomicLongАтомарные классы используют операции CAS для создания идентификаторов.
@Service
public class RedisSequenceFactory {
@Autowired
RedisTemplate<String, String> redisTemplate;
public void setSeq(String key, int value, Date expireTime) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
counter.set(value);
counter.expireAt(expireTime);
}
public void setSeq(String key, int value, long timeout, TimeUnit unit) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
counter.set(value);
counter.expire(timeout, unit);
}
public long generate(String key) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
return counter.incrementAndGet();
}
public long incr(String key, Date expireTime) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
counter.expireAt(expireTime);
return counter.incrementAndGet();
}
public long incr(String key, int increment) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
return counter.addAndGet(increment);
}
public long incr(String key, int increment, Date expireTime) {
RedisAtomicLong counter = new RedisAtomicLong(key, redisTemplate.getConnectionFactory());
counter.expireAt(expireTime);
return counter.addAndGet(increment);
}
}
Второй заключается в использованииredisTemplate.opsForHash()и объединитьUUIDспособ генерации сгенерированного идентификатора.
public Long getSeq(String key,String hashKey,Long delta) throws BusinessException{
try {
if (null == delta) {
delta=1L;
}
return redisTemplate.opsForHash().increment(key, hashKey, delta);
} catch (Exception e) { // 若是redis宕机就采用uuid的方式
int first = new Random(10).nextInt(8) + 1;
int randNo=UUID.randomUUID().toString().hashCode();
if (randNo < 0) {
randNo=-randNo;
}
return Long.valueOf(first + String.format("%16d", randNo));
}
}
Я вернул компьютер интервьюеру, и он быстро просканировал мой код и что-то сказал.
Опрашивающий: Молодой человек, не пишите комментарии, это дурная привычка.
Я: О, спасибо, что напомнили, извините, в следующий раз буду внимательнее.
Алгоритм снежинки
я: шестой способ"Алгоритм снежинки", который также является популярным методом создания распределенных идентификаторов на рынке.
После разговора я понял, что рисовать снова необходимо, поэтому начал рисовать на столе. Интервьюер с любопытством посмотрел на меня, понял, что я делаю, и терпеливо ждал.
Я: Он использует 64-битный тип генерации идентификатора и делит 64-битный на несколько сегментов, как показано на рисунке ниже.
Я вручил ему нарисованную мной картинку и затем объяснил ее.
Я: Первый бит используется как бит идентификации, потому что длинный тип в Java — это символ эры, а бит ID — положительное число, поэтому первый бит равен 0.
Я: Следующие 41 бит — это временные метки, битовые единицы на уровне миллисекунд.Обратите внимание, что временная метка здесь относится не к временной метке текущего времени, а к разнице между значениями ("текущее время - время начала").
Я: Время запуска здесь обычно относится к времени запуска генератора идентификаторов, которое задается самой нашей программой.
Я: за которым следуют следующие 10 бит: включая 5 бит"Идентификатор центра обработки данных (datacenterId) и 5-значный идентификатор компьютера (workerId)", который может идентифицировать до 1024 узлов (1
Я: Последние 12 бит — это серийный номер, а 12-битный порядок счета позволяет каждому узлу генерировать 4096 серийных номеров каждую миллисекунду (1
Я: Алгоритм Snowflake использует в качестве идентификаторов идентификатор центра обработки данных и идентификатор машины, который не генерирует повторяющихся идентификаторов и генерируется локально, не потребляя сеть.Он очень эффективен.Согласно данным, он может генерировать 260 000 идентификаторов в секунду.
Я: Но у алгоритма снежинки есть и свои недостатки, потому что расчет алгоритма снежинки зависит от времени, и если системное время будет отброшено назад, будут дублироваться идентификаторы.
Интервьюер: У вас есть лучшее решение для ситуации, когда обратные вызовы времени генерируют дублирующиеся идентификаторы?
Я: В реализации алгоритма снежинки, если предыдущее время равно текущему, будет выброшено исключение, а также можно отключить обратный вызов времени.
Я: Для тех, у кого короткое время обратного вызова, вы можете подождать, пока истечет время обратного вызова, прежде чем генерировать идентификатор.
Интервьюер: Можете ли вы дать мне алгоритм снежинки? Я даю вам эту клавиатуру.
Я:. . .
я: хорошо.
Время проходит...
Через несколько минут я наконец-то вырубил алгоритм Снежинки, это реально отстой, почему так сложно попасть на собеседование?
/**
* 雪花算法
* @author：黎杜
*/
public class SnowflakeIdWorker {
/** 开始时间截 */
private final long twepoch = 1530051700000L;
/** 机器id的位数 */
private final long workerIdBits = 5L;
/** 数据标识id的位数 */
private final long datacenterIdBits = 5L;
/** 最大的机器id，结果是31 */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/** 最大的数据标识id，结果是31 */
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
/** 序列的位数 */
private final long sequenceBits = 12L;
/** 机器ID向左移12位 */
private final long workerIdShift = sequenceBits;
/** 数据标识id向左移17位 */
private final long datacenterIdShift = sequenceBits + workerIdBits;
/** 时间截向左移22位*/
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
/** 生成序列的掩码 */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
/** 工作机器ID(0~31) */
private long workerId;
/** 数据中心ID(0~31) */
private long datacenterId;
/** 毫秒内序列(0~4095) */
private long sequence = 0L;
/** 上次生成ID的时间截 */
private long lastTimestamp = -1L;
/**
* 构造函数
* @param workerId 工作ID (0~31)
* @param datacenterId 数据中心ID (0~31)
*/
public SnowflakeIdWorker(long workerId, long datacenterId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
this.workerId = workerId;
this.datacenterId = datacenterId;
}
/**
* 获得下一个ID (该方法是线程安全的)
* @return SnowflakeId
*/
public synchronized long nextId() {
long timestamp = getCurrentTime();
//如果当前时间小于上一次生成的时间戳，说明系统时钟回退过就抛出异常
if (timestamp < lastTimestamp) {
throw new BusinessionException("回拨的时间为："+lastTimestamp - timestamp);
}
//如果是同一时间生成的，则进行毫秒内序列
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
//毫秒内序列溢出
if (sequence == 0) {
//获得新的时间戳
timestamp = tilNextMillis(lastTimestamp);
}
} else { //时间戳改变，毫秒内序列重置
sequence = 0L;
}
//上次生成ID的时间截
lastTimestamp = timestamp;
//移位并通过或运算拼到一起组成64位的ID
return ((timestamp - twepoch) << timestampLeftShift) // 计算时间戳
| (datacenterId << datacenterIdShift) // 计算数据中心
| (workerId << workerIdShift) // 计算机器ID
| sequence; // 序列号
}
/**
*获得新的时间戳
* @param lastTimestamp 上次生成ID的时间截
* @return 当前时间戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = getCurrentTime();
// 若是当前时间等于上一次的1时间就一直阻塞，知道获取到最新的时间（回拨后的时间）
while (timestamp <= lastTimestamp) {
timestamp = getCurrentTime();
}
return timestamp;
}
/**
* 获取当前时间
* @return 当前时间(毫秒)
*/
protected long getCurrentTime() {
return System.currentTimeMillis();
}
Для того, чтобы оставить хорошее впечатление у интервьюера, я тоже написал здесь заметку, чтобы он больше не говорил обо мне, а я после набора отодвинул к нему компьютер обратно.
Интервьюер: Ну, у вас есть прочная основа для сравнения цен, вы должны были хорошо подготовиться перед собеседованием и прочитать много материалов интервью.
Я подумал про себя, как мне подготовиться к интервью? Я готовился снова, с работы до сих пор, я суммировал свои знания и формировал свою собственную систему знаний, чтобы угодить ему, я могу только сказать да.
Я: Ну да, я долго готовилась, этого вполне достаточно.
Интервьюер: Ну, вы все еще понимаете последние два алгоритма?
Лист и UidGenerator
Я: У меня действительно нет глубокого понимания последних двух.Я видел информацию в Интернете до того, что алгоритм листа Meituan должен полагаться на базу данных, ZK, а также может обеспечить уникальность глобального идентификатора, который увеличивается. по одному пункту.
Я: Алгоритм Baidu UidGenerator реализован на основе алгоритма Snowflake, который также требует помощи базы данных.В отличие от алгоритма Snowflake,"UidGenerator поддерживает пользовательскую метку времени, идентификатор центра основного предложения и идентификатор машины, количество цифр серийного номера.".
Интервьюер: Хм, ладно, на сегодняшнем интервью все, увидимся в следующий раз.
В восторге...