Привет, меня зовут Нуржан Сактаганов, я ведущий разработчик в Почте и Облаке Mail. Хочу рассказать о нашей библиотеке Go-VShard-router и поделиться трюками и выводами, которые мы сделали при разработке.

Введение

Если вкратце, то мы взяли open-source библиотеку VShard от авторов Tarantool, написанную на Lua, и переписали её часть на Go.

Tarantool — промежуточное ПО для работы с данными, которое ускоряет цифровые сервисы и снижает нагрузку на core-cистемы. Сочетает в себе сервер приложений, гибридное хранилище с гибкой схемой данных и мощные средства масштабирования. Если вы не знакомы с этим продуктом, можно начать с этой статьи.

А VShard — это модуль, библиотека для Tarantool, которая автоматически шардирует и решардирует данные. Позволяет указывать различные правила: задавать веса шардам и репликам, как балансировать запросы и многое другое. Подробнее о возможностях библиотеки рассказано здесь.

Как работает шардинг

В VShard шардинг реализован классически: данные разбиваются на большое количество кусков — бакетов, — которые раскидываются по физическим шардам.

А решардинг работает так (см. анимацию ниже). Допустим, сначала у вас было три шарда. Со временем данных стало больше и вы добавили новые шарды. После чего существующие бакеты автоматически перераспределяются с учётом новых шардов.

Как пользоваться VShard

В первую очередь нужно выбрать количество бакетов: N. Это делается только один раз, потом поменять нельзя. Затем нужно выбрать ключ для шардирования данных. Например, взять поле userid или fullname. Потом вы должны задать отображение, какие данные попадают в какой бакет: key → 1...N. Допустим, остаток от деления на количество бакетов (userid % N) + 1 или хеш от fullname и остаток от деления (crc32(fullname) % N) + 1.

И в завершение вам нужно bootstrap-ить кластер.

Архитектура библиотеки VShard

VShard состоит из двух частей: VShard storage и VShard router. Storage работает на экземплярах Tarantool, на которых хранятся данные, и под капотом делает всю магию шардирования и решардирования. Router работает на отдельных экземплярах Tarantool, предназначенных для маршрутизации. Использует API storage для служебных задач, например, построения карты кластера. Также этот компонент предоставляет API для прозрачной работы с кластером, чтобы пользователю не нужно было заботиться о маршрутизации.

Пусть у нас есть приложение на Go. Тогда схема взаимодействия выглядит так:

Приложение обращается к router-у, а тот перенаправляет запросы в соответствующие Tarantool-ы, где хранятся данные.

Зачем понадобилось переписывать библиотеку на Go

Поскольку Lua в Tarantool работает в однопоточном режиме и интерпретируется, требуется много router-ов. Например, у нас в Облаке есть большой кластер с 256 шардами и 112 router-ами (соотношение примерно 2 к 1). Кроме того, в Lua VShard-router есть некоторые нерешённые проблемы, которые мешают во время учений. Также в оригинальной библиотеке приходится писать на Lua, причём довольно разветвлённую логику. И наконец, есть лишний hop: app → router → storage.

Так что мы решили написать свою реализацию на Go, чтобы избавиться от всех этих недостатков.

К слову, на Go мы решили переписать не только библиотеку, но и ВКонтакте! А если быть точнее, мы запустили большой технологический проект по переводу ВКонтакте на сервисную архитектуру и построению единой платформы разработки.
Приглашаем Go-разработчиков на VK Go Meetup 2025, который пройдёт уже 24 апреля. Расскажем о том, как планируем решать настолько масштабную задачу. Подробности и регистрация уже на сайте.

Как мы делали Go-VShard-router

Мы взяли из Tarantool официальный Go-коннектор, воспользовались VShard storage API и повторили на Go всё то же самое, что делает Lua VShard-router. Теперь библиотека встроена в приложение на Go и мы ходим за данными напрямую.

Как пользоваться библиотекой

vshardRouter, err := vshardrouter.NewRouter(ctx, vshardrouter.Config{
       Loggerf:          &vshardrouter.StdoutLoggerf{},
       DiscoveryTimeout: time.Minute,
       DiscoveryMode:    vshardrouter.DiscoveryModeOn,
       TopologyProvider: static.NewProvider(cfg.Storage.Topology),
       TotalBucketCount: cfg.Storage.TotalBucketCount,
       PoolOpts: tarantool.Opts{
           Timeout: time.Second,
       },
   })

   bucketID := (userID % cfg.Storage.TotalBucketCount) + 1

   resp, err := vshardRouter.CallRW(ctx, bucketID, "get_user", []interface{}{userID}, vshardrouter.CallOptions{
       Timeout: 1 * time.Second,
   })

Мы просто создаём экземпляр router-a (пропустим аргументы NewRouter). Дальше смотрим на строку с bucketID. Допустим, мы хотим получить пользователя с ID, равным userID. Тогда вычисляем, в каком bucket-е этот пользователь находится, вызываем CallRW и передаём туда bucket, имя метода и его аргументы, и получаем ответ.

Трюки и выводы

Основной тип данных у нас называется router:

// Может использоваться из разных горутин
type Router struct {
   mutex            sync.RWMutex
   nameToReplicaset map[string]*Replicaset
   // . . .
}

nameToReplicaset — это map, где в качестве ключа имя, а в качестве значения Replicaset, а Replicaset — это шард. Так как шард может состоять из нескольких реплик, поэтому мы так его назвали.

Какие операции можно выполнять с полем nameToReplicaset map[string]*Replicaset:

добавлять или удалять элементы из-за изменения топологии;
пользователь может итерироваться по map;
мы сами можем по итерироваться по map.

И всё это из разных горутин. То есть существует конкурентный доступ к этой map по чтению и записи.

Например, есть метод RouteAll, который позволяет пользователю итерироваться по map.

func (r *Router) RouteAll() map[string]*Replicaset {
   return r.nameToReplicaset
}

В этом коде что-то не так. Вспомним, что map – ссылочный тип. Допустим, пользователь получил map, и хочет обратиться по некоторому ключу:

// получили мапку
name2Rs := r.RouteAll()

// плохо, name2Rs может конкурентно меняться и получим панику
rs := name2Rs["name1"]

// ещё хуже, пользователь либы может изменить внутренние данные библиотеки
name2Rs["name2"] = rs

Как избежать всех этих возможных проблем? Просто создайте копию map и экспортируйте её. Теперь пользователь может делать с ней всё, что угодно.

func (r *Router) RouteAll() map[string]*Replicaset {
   // это всё под мьютексом
   copy := make(map[string]*Replicaset)
   for k, v := range r.nameToReplicaset {
       copy[k] = v
   }
   return copy
}

В библиотеке есть метод MapCallRW, который итерируется по map:

func (r *Router) MapCallRW(...) error {
   // Берем референс/локи в каждом репликасете
   for _, rs := range r.nameToReplicaset {
       rs.Ref()
   }
   // Освобождаем референс/локи в каждом репликасете
   for _, rs := range r.nameToReplicaset {
       rs.Unref()
   }
   return nil
}

Сначала идём по наборам реплик, устанавливаем блокировки, делаем свои дела и снимаем блокировки. Но пока мы что-то делаем, map может измениться, и тогда, например, мы можем снять не все блокировки. Решение здесь такое же, как и в предыдущем примере: нужно зафиксировать состояние, создав копию.

func (r *Router) MapCallRW(...) error {
   // нужно зафиксировать состояние мапы создав копию
   name2Replicaset := r.name2ReplicasetCopy()
   for _, rs := range nameToReplicaset {
       // . . .
   }
   // . . .
   return nil
}

Да, каждый раз делать копии неудобно. Чтобы упростить себе жизнь, воспользуемся свойством неизменяемости. Идея в том, что map не будет меняться после создания.

func (r *Router) AddReplicaset(name string, rs *Replicaset) {
   // всё это под локом
   newMap := make(map[string]*Replicaset)
   // копируем в newMap из r.nameToReplicaset
   //...
   newMap[name] = rs
   r.nameToReplicaset = newMap
}

То же самое делаем для RemoveReplicaset.

В результате нам больше не надо создавать копии для внутренних структур. Мы получили ссылку на map и знаем, что map не изменится: мьютекс теперь защищает не данные, а переменную r.nameToReplicaset. Можно даже заменить мьютекс на atomic. Всё это мы можем делать при каждом изменении топологии, потому что вряд ли она станет часто меняться, и это вообще недорого.

Промежуточные выводы:

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

Вернёмся к нашему типу данных Router. В нём есть поле bucketMap — слайс указателей. С ним связано другое поле.

type Router struct {
   // . . .
   bucketMap        []*Replicaset
   knownBucketCount int
}

BucketMap — это карта нашего кластера, информация о том, где какой бакет лежит. Допустим, мы хотим узнать, где лежит пятый бакет. Тогда мы просто обращаемся к элементу с индексом 5 этого слайса, и получаем указатель на Replicaset, где находится этот бакет. Если там лежит nil, значит информация о расположении бакета нам ещё неизвестна.

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

Какие операции с полем возможны в нашей библиотеке

func (r *Router) bucketSet(bucketID uint64, rs *Replicaset) {
   if r.bucketMap[bucketID] == nil {
       r.knownBucketCount += 1
   }
   r.bucketMap[bucketID] = rs
}

У нас есть метод bucketSet. Он позволяет установить для такого-то bucketID такой-то Replicaset. Если был nil, то увеличиваем счётчик и устанавливаем его значение.

Ещё есть метод bucketReset, в котором стирается информация, и в случае необходимости счётчик уменьшается.

Есть discovering-горутина, в которой циклически с какой-то периодичностью вызывается bucketSet.

Наконец, на каждый запрос происходит маршрутизация: обращение к некоторому элементу слайса r.bucketMap[bucketID]. То есть мы опять убедились, что есть конкурентный доступ по чтению и записи к элементам слайса.

Как синхронизировать доступ к элементам

Слайс BucketMap может содержать тысячи, десятки или сотни тысяч элементов. Например, у нас в Облаке есть кластер, в котором 2²⁰ бакетов — 1 048 576. И ещё может быть очень много запросов, каждый из которых — это обращение к элементу слайса.

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

Другой вариант использовать по мьютексу на каждый элемент. Но миллион мьютексов меня как-то смущает.

Может, создадим массив мьютексов? Чтобы каждый из них защищал свой диапазон элементов? Например, N мьютексов: bucketID % N := номер мьютекса для этого бакета.

Но есть вариант ещё проще — atomic-и!

type Router struct {
   // . . .
   bucketMap        []atomic.Pointer[Replicaset]
   knownBucketCount atomic.Int32
}

По сути, мы превращаем наш слайс указателей в слайс atomic-указателей. И счётчик превращаем в atomic-счётчик. Тогда метод bucketSet будет выглядеть так:

func (r *Router) bucketSet(rs *Replicaset, bucketID uint64) {
   if old := r.bucketMap[bucketID].Swap(rs); old == nil {
       r.knownBucketCount.Add(1)
   }
}

func (r *Router) bucketReset(bucketID uint64) {
   if old := r.bucketMap[bucketID].Swap(nil); old != nil {
       r.knownBucketCount.Add(-1)
   }
}

Мы просто устанавливаем новые значения, а потом смотрим старые. Если там раньше был nil, значит нам надо увеличить счётчик. Аналогично и с bucketReset, только счётчик мы уменьшаем.

Всё это возможно потому, что:

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

И вроде бы всё хорошо, но у нас есть операция RouteMapClean(): мы очищаем карту кластера, то есть создаём новый слайс и присваиваем 0 полю r.knownBucketCount.

func (r *Router) RouteMapClean() {
   r.mutex.Lock()
   r.bucketMap = make([]atomic.Pointer[Replicaset], totalBucketCount)
   r.mutex.Unlock()
   r.knownBucketCount.Store(0) // присваивание - не коммутативная операция
}

Однако это присваивание уже не обладает свойством коммутативности и всё ломается. Что делать? Давайте подумаем. Вряд ли RouteMapClean() будет вызываться часто. А раз это редкая операция, то можно просто создать новый объект с корректным начальным значением, как в предыдущем случае с неизменяемостью.

Давайте вынесем два поля в отдельную структуру:

type bucketMapView struct {
   bucketMap        []atomic.Pointer[Replicaset]
   knownBucketCount atomic.Int32
}

type Router struct {
   view atomic.Pointer[bucketMapView]
}

В Router-е будем хранить указатель на эту структуру. Метод bucketSet приобретает такой вид: берём актуальный указатель и делаем всё, что нам нужно, только с этой новой структурой.

func (r *Router) bucketSet(rs *Replicaset, bucketID uint64) {
   view := r.view.Load()

   if old := view.bucketMap[bucketID].Swap(rs); old == nil {
       view.knownBucketCount.Add(1)
   }
}

func (r *Router) RouteMapClean() {
   view := &bucketMapView{
       bucketMap: make([]atomic.Pointer[Replicaset], totalBucketCount),
   }
   r.view.Store(view)
}

RouteMapClean просто создаёт новый объект с корректным начальным значением и подменяет указатель. BucketSet и RouteMapClean не приводят к некорректному состоянию.

Выводы

Несогласованность данных в течение нескольких наносекунд бывает не страшна.
Конкурентность — это не только про блокировки, но и про:
- atomic-и;
- свойства используемых операций: в нашем случае сложения и присваивания;
- неизменяемость.
Используя эти техники, получили wait-free библиотеку. Бенчмарки можно посмотреть в репозитории.
Atomic-и не являются серебряной пулей! Есть ситуации, когда решение с atomic-ом даже в 100 раз медленнее, чем без.

Мы закончили активную разработку, библиотека теперь в open-source и готова к эксплуатации.

А если хотите обсудить какие-то технические детали лично или больше узнать про смену архитектуры и инструменты, которые сделают разработку в разы проще, приходите на VK Go Meetup 2025, который мы уже заспойлерили выше. Будет много технических деталей. Разберём богатства Go 1.24 и недостатки новой map, тулинг мини-аппов и нашу самую масштабную задачу последних лет.