Студенты, знакомые с алгоритмом Paxos, должны знать, что алгоритм Paxos требует, чтобы идентификатор предложения был глобально уникальным (и увеличивался). На самом деле генерация глобально уникального идентификатора (и приращения) сама по себе требует некоторых технических гарантий. На самом деле существует множество способов создания глобального уникального идентификатора, но удовлетворить требования высокого количества запросов в секунду, высокой доступности и низкой задержки непросто. Как новичок, у которого нет возможности участвовать в системах с высокой степенью параллелизма, я могу понимать и учиться только через совместное использование больших фабрик. Проще говоря, содержание этой статьи состоит в том, чтобы обобщить уникальные решения для генерации идентификаторов для производственных сред трех крупных компаний, для методов, которые не соответствуют условиям (высокий QPS, высокая доступность и низкая задержка). , я пропущу их здесь. Кроме того, может быть много других продвинутых методов, но из-за моих ограниченных знаний я не знаю.
1. Алгоритм снежинки Twitter
Алгоритм снежинки на самом деле является относительно простым и распространенным алгоритмом генерации уникальных идентификаторов. Алгоритм генерации ID внутри MongoDB очень близок к снежинке. snowflake генерирует 64-битный идентификатор, который представлен в программе long (JVM-подобный язык).Сгенерированная структура идентификатора выглядит следующим образом:
Ниже приводится краткое объяснение структуры идентификатора. Первый бит — это идентификационный бит, поскольку идентификатор часто представляется длинным. Этот бит равен 0, что указывает на то, что это положительное число, следующий - 41-битная метка времени, а единица времени — миллисекунды, это событие обычно является относительным временем, затем следующие 10 бит используются для представления разных машин, 5 бит представляют центр обработки данных, а 5 бит представляют идентификатор машины в центре обработки данных. Следующие 12 бит — это порядковый номер идентификатора, который отличает разные идентификаторы, сгенерированные одной и той же машиной за одну и ту же миллисекунду.
Twitter открыл исходный код алгоритма снежинки, но похоже, что он больше не поддерживается. Здесь я вырезал кусок кода IDWorker, используя Scala, но если вы не знаете Scala, это не повлияет на ваше чтение.
/** Copyright 2010-2012 Twitter, Inc.*/
package com.twitter.service.snowflake
import com.twitter.ostrich.stats.Stats
import com.twitter.service.snowflake.gen._
import java.util.Random
import com.twitter.logging.Logger
class IdWorker(val workerId: Long, val datacenterId: Long, private val reporter: Reporter, var sequence: Long = 0L)
extends Snowflake.Iface {
private[this] def genCounter(agent: String) = {
Stats.incr("ids_generated")
Stats.incr("ids_generated_%s".format(agent))
}
private[this] val exceptionCounter = Stats.getCounter("exceptions")
private[this] val log = Logger.get
private[this] val rand = new Random
//开始生成ID的时间戳
val twepoch = 1288834974657L
//机器id或者是线程id所占用的位数
private[this] val workerIdBits = 5L
//数据中心所占用的位数
private[this] val datacenterIdBits = 5L
private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits)
private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits)
private[this] val sequenceBits = 12L
private[this] val workerIdShift = sequenceBits
private[this] val datacenterIdShift = sequenceBits + workerIdBits
private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits
private[this] val sequenceMask = -1L ^ (-1L << sequenceBits)
//上一次生成ID的时间戳
private[this] var lastTimestamp = -1L
// sanity check for workerId
if (workerId > maxWorkerId || workerId < 0) {
exceptionCounter.incr(1)
throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0".format(maxWorkerId))
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
exceptionCounter.incr(1)
throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId))
}
log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId)
//获取ID的方法
def get_id(useragent: String): Long = {
if (!validUseragent(useragent)) {
exceptionCounter.incr(1)
throw new InvalidUserAgentError
}
val id = nextId()
genCounter(useragent)
reporter.report(new AuditLogEntry(id, useragent, rand.nextLong))
id
}
def get_worker_id(): Long = workerId
def get_datacenter_id(): Long = datacenterId
def get_timestamp() = System.currentTimeMillis
//生成ID的方法
protected[snowflake] def nextId(): Long = synchronized {
var timestamp = timeGen()
//时钟回拨，直接产生异常
if (timestamp < lastTimestamp) {
exceptionCounter.incr(1)
log.error("clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds".format(
lastTimestamp - timestamp))
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask
//sequence在同1ms内溢出，则等待到下一ms再返回ID
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp)
}
} else {
sequence = 0
}
lastTimestamp = timestamp
((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence
}
protected def tilNextMillis(lastTimestamp: Long): Long = {
var timestamp = timeGen()
while (timestamp <= lastTimestamp) {
timestamp = timeGen()
}
timestamp
}
protected def timeGen(): Long = System.currentTimeMillis()
val AgentParser = """([a-zA-Z][a-zA-Z\-0-9]*)""".r
def validUseragent(useragent: String): Boolean = useragent match {
case AgentParser(_) => true
case _ => false
}
}
Как видно из кода, алгоритм Snowflake прост. В приведенном выше фрагменте кода следует обратить внимание на два ключевых момента: первый — это проблема обратного вызова часов. Из-за наличия синхронизации времени и високосных секунд подход алгоритма снежинки к обратному вызову часов заключается в прямом выдаче исключения. Вторая — проблема переполнения 12-битного серийного номера, то есть количество идентификаторов, сгенерированных запросом в течение 1 мс, превышает 4096 идентификаторов. Алгоритм снежинки делает это, ожидая, пока следующая мс не сгенерирует идентификатор.
Однако такая ситуация должна возникнуть с трудом.Согласно скорости 4096 идентификаторов в миллисекунду, теоретическая мощность одного сервера генерации идентификаторов может достигать 350 миллиардов/день. Так как Snowflake может поддерживать до 1024 экземпляров развертывания. Согласно сообщению команды WeChat, количество обращений к сервису генерации серийных номеров WeChat составляет триллионы в день. Так что с точки зрения QPS алгоритм снежинки в порядке.
2. Leaf, служба генерации идентификаторов Meituan-Dianping.
По словам технической команды Meituan Dianping, они использовали распределенную систему генерации идентификаторов под названием Leaf. В системе «Листок» реализованы две схемы, первая называется «Листок-снежинка». Это решение мало чем отличается от обычной снежинки Twitter, в которой leaf-snowflake использует Zookeeper для настройки id машины, что позволяет в определенной степени улучшить масштабируемость и отказоустойчивость системы. Схема архитектуры листика-снежинки выглядит следующим образом:
Кроме того, узлы Leaf-snowflake слабо зависят от ZooKeeper, а локальный узел также будет иметь альтернативный идентификатор машины. Это вполне понятно, так как для снежинки реестр не нужен в первую очередь. Лично самая большая роль Zookeeper заключается в облегчении высшего управления и мониторинга.
Лист-снежинка кратко упоминался выше, а затем давайте посмотрим на лист-сегмент. Основная идея Leaf-segment на самом деле очень проста: «превратить ноль в целое». В алгоритме Leaf-segment используется метод централизованного управления базой данных. На верхнем уровне базы данных идентификаторов находится несколько прокси-серверов.Прокси-сервер каждый раз запрашивает сегмент идентификаторов в базе данных, а затем использует эти идентификаторы в качестве пула идентификаторов для предоставления идентификаторов внешним клиентам. Общая архитектура Leaf-сегмента выглядит следующим образом:
На самом деле, глядя на эту архитектурную схему, все становится ясно с первого взгляда. Основным узким местом этой системы является единственная точка отказа сервера базы данных. С этой целью подход команды Meituan Dianping заключается в использовании основной архитектуры базы данных. Ведомая база данных продолжает работать после выхода из строя основной базы данных, что повышает доступность. Метод подписки на binlog, принятый в базе данных master, может быть не синхронизирован, что является дефектом. Если здесь используется система CP, такая как ZooKeeper, может возникнуть проблема, связанная с тем, что QPS не может подняться. Здесь явно присутствует компромисс.
Кроме того, стоит упомянуть, что прокси-сервер Leaf-сегмента использует двойную буферизацию для оптимизации максимальной задержки запроса, что очень похоже на двойную буферизацию дисплея оконной системы.
3. WeChat seqsvr
Seqsvr WeChat также используется для генерации серийных номеров. Однако, как приложение для обмена мгновенными сообщениями, режим генерации идентификатора WeChat имеет определенные особенности. Самая большая особенность личного понимания WeChat заключается в том, что он принадлежит знакомой социальной сети. В WeChat, кажется, всегда было ограничение на количество друзей, и отношения между друзьями взаимны. Таким образом, информацию о пользователе можно легко сегментировать по горизонтали, например просто сегментировать по идентификатору пользователя. Архитектуру seqsvr можно разделить на два уровня, а именно StoreSvr и AllocSvr (уровень хранения и средний уровень кэша). Его общая структура выглядит следующим образом:
С вертикальной точки зрения AllocSvr отвечает за распределение последовательностей напрямую клиентам, а StoreSvr отвечает за надежное хранение текущего максимального номера последовательности (реализовано через NRW). С этой точки зрения он очень похож на листовой сегмент Meituan Dianping. Основное отличие заключается в двух моментах: первый заключается в том, что последовательность, сгенерированная seqsvr, является идентификатором под UID (идентификатором пользователя), иными словами — UID + последовательность = глобальный идентификатор; второй момент заключается в том, что seqsvr использует NRW для достижения сильного непротиворечивость хранения данных пола.
С горизонтальной точки зрения seqsvr использует UID для горизонтальной сегментации для достижения балансировки нагрузки. Анализ одного набора показывает, что AllocSvr может полностью работать в памяти без реализации постоянства. Потому что в худшем случае некоторые идентификаторы в AllocSvr не работают до их использования, а после перезапуска применяется новый идентификатор, поэтому некоторые идентификаторы пропускаются. Однако порядковый номер WeChat имеет 64 бита и расположен ниже UID, поэтому пропуск идентификатора вполне допустим.
Таким образом, основное давление seqsvr по-прежнему приходится на StoreSvr.Даже если выполняется сегментация Set, режим хранения NRW все равно должен платить пропускной способностью. Вероятно, после дальнейших экспериментов seqsvr был дополнительно оптимизирован — разделяемое хранилище номеров сегментов. Как показано на рисунке ниже, max_seq — это текущий максимальный порядковый номер. Группа пользователей имеет общий max_seq, и метод группировки по-прежнему делится по UID. Таким образом, нагрузка на StoreSvr в seqsvr становится меньше. Например, если рабочая частота у всех одинаковая, то давление записи StoreSvr снижается до 1/N перед разделением (N — количество пользователей в группе). Давление нагрузки StoreSvr на данные также снижено до 1. /Н.
После некоторого анализа можно обнаружить, что дизайн seqsvr WeChat по-прежнему очень хорош, ведь за кулисами должно быть много мастеров, чтобы сделать такое успешное приложение. Кроме того, у seqsvr есть много дизайнов для аварийного восстановления, о которых я не буду здесь писать.
Использованная литература:
【1】Дизайн и эволюция архитектуры генератора серийных номеров WeChat
【2】Лист — Распределенная система генерации идентификаторов Meituan Dianping