Спасибо за тёплые слова и поздравления - всех обнял 😘

Мой забег по собесам пока закончился. Иногда буду ходить, но уже на суммы от $10k+ (если такие вакансии вообще существуют 💸)

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

Я тут весь в делах - с кайфом залетел в мини-стартап(парт-тайм). Постараюсь писать стабильно, чтобы не было больших пауз🤑

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

У меня начались флэшбэки с собесов и задач которые мне давали, буду по-тихоньку их разбирать. На интервью по гошке часто просят реализовать кэш. Звучит несложно, hashmap + mutex/rwmutex

get(key)
 mx.RLock()
 defer mx.RUnlock()

 val, ok := data[key]

 return val, ok


put(key, val)
 mx.Lock()
 defer mx.Unlock()

 data[key] = val

И тут всплывает главное отличие между data race и race condition.

Data race - это непредсказуемое поведение при одновременном доступе к памяти без синхронизации. У нас используется mutex, всё безопасно.

Race condition - это логическая гонка.
Даже если синхронизация есть, результат может зависеть от порядка выполнения горутин. Что если 1000 горутин будут обновлять значение по одному и тому же ключу(cache stampede). Сжигаем cpu и создаём лишнюю нагрузку - все конкурируют за один и тот же mutex, хотя данные у всех одинаковые. Важно, нижеперечисленные оптимизации работают только если значения одинаковые и важен первый write, который затирает остальные.

Если же бизнесу важен последний апдейт - эти оптимизации не помогут, нужен совсем другой подход

1) Double checking
Просто и понятно, в put мы добавляем две проверки на наличие ключа. Тем самым горутина внутри мьютекса не будет перезаписывать значение если оно уже есть. Но все равно есть конкурентный доступ к мапе

put(key, val)
 mx.RLock()
 val, ok := data[key]
 mx.RUnlock()

 if ok {
   return 
 }

 mx.Lock()
 defer mx.Unlock()
 _, ok := data[key] // second check

 if ok {
   return 
 }

 data[key] = val

2) Сын маминой подруги - single-flight😎. Реализуется через киллер-фичу гошки - каналы. Вкратце - создается еще одна мапа calls, ключ любой key и value - канал, через который другие горутины будут ждать результат. Первая горутина, которая успела захватить мьютекс, создаёт канал и кладёт его в calls. Все остальные, кто пришел с этим ключом, ждут значение через канал

getOrput(key, val)
 mx.RLock()
 val, ok := data[key]
 mx.RUnlock()

 if ok {
   return 
 }

 mx.Lock()
 if _, ok = calls[key]; ok {
  mx.Unlock()
  return <- calls[key] // читаем из канала
 }

 ch := make(chan value, 1) // буф. канал чтобы не блокировать писателя
 calls[key] = ch

 data[key] = val
 delete(calls, key) // удаляем чтобы горутины не блокировались вечно на чтение и не читали старое значение
 mx.Unlock()

 ch <- val
 close(ch)

 return val

P.S
Эта задача была в индрайв - я разложил эту задачу до атомов, упомянув все перечисленные выше оптимизации, на сеньора не прошел 😧

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

С начала года яндекс изменили процесс интервью(не везде), теперь у них есть секция по коду, для Go обычно это имплементация load balancer. Два раза я ходил на собес и два раза мне попалась эта задача. Накидываем слайс бэкендов и атомик для round robin.

type Request interface {
}
type Response interface{}

type Backend interface {
 Invoke(req Request) (Response, error)
}

type LoadBalancer struct {
 backends []Backend
 index    int64
}

func (lb *LoadBalancer) GetBackend() Backend {
 idx := atomic.AddInt64(&lb.index, 1)
 return lb.backends[(idx - 1) % int64(len(lb.backends))]
}

func (lb *LoadBalancer) Invoke(req Request) (Response, error) {
 backend := lb.GetBackend()

 return backend.Invoke(req)
}

Далее идет follow up, нужно отправлять запросы только на живые backend, health check никто не гарантирует.
Я не нашел ничего лучше как в Invoke маркировать живые бэкенды и в GetBackend это учитывать. Но я переусложнил потому что неживым бэкендам нужно давать "второй шанс" и пытаться отправлять на них запросы. Будет мапа которая маркирует живые, неживые и спустя какое-то окно мы будем давать неживым "второй шанс".
В общем самое простое решение - отправлять запрос до тех пор пока не получим ok от бэкенда

func (lb *LoadBalancer) Invoke(req Request) (Response, error) {
 for i := 0; i < len(lb.backends); i++ {
  backend := lb.GetBackend()
  response, err := backend.Invoke(req)

  if err == nil {
   return response, nil
  }
 }

 return nil, fmt.Errorf("no live backend available")
}

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

Отключение AWS, из-за которого легла часть пользовательских сервисов - Snapchat, Fortnite, Duolingo, Signal, в Plata часть hr-сервисов тоже не работали, произошло из-за race condition в DynamoDB.

Коротко - два инстанса применяли DNS план, отправляя DNS записи в DNS Service(Route53).

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

За это время второй инстанс применил новый план, обновил DNS Service и удалил старые версии, включая предыдущую. Когда первый инстанс закончил, он перезаписал новый план старым, уже удалённым, в итоге все ip адреса были удалены.

Далее всё каскадно упало из-за DynamoDB

Concurrency - база получается 🗒

Ссылка на оригинал

Менти из этого поста получил офер в плату😬. Хотел поделиться своей радостью, я видел как ему было тяжело и стрессово. В плате был его первый систем дизайн который он успешно прошел, хоть он и сам в этом сомневался. Теперь для него собачка справа станет чуть подкаченной 😎

Перекат с Java на Go

При переходе в WB +1.5x к зарплате, спустя полгода оффер на 6500 usdt в беттинг компанию(не принял), а сейчас работаю в Plata, делаю бэк для банкоматов.

Как выглядел мой переход
1) Около трёх месяцев привыкания к языку
2) Изучение популярных вопросов по Go и подготовка к ним. Язык сейчас довольно популярный, поэтому мок интервью легко найти на ютубе
3) Выход на рынок, прохождение интервью

Большая часть собесов в этой статистике была по Go

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

Сейчас изучаю Rust - купил подписку на Codecrafters и пишу свой мини-Redis🗒, буду делиться апдейтами

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

По написанию redis на rust(codecrafters), закончил первый stage - чтение и обработка запросов. Идет хорошо, хоть и местами тяжело. В комменты скину ссылки для вкатывания, велком кому интересно.

Есть идея сделать пост по вопросам бд и кафки на собесах, но есть ощущение что это никому не нужно. Ставь 👍 если интересно

Вопросы по бд🤑
Составил общие вопросы которые мне задавали

1) Индексы
- Кластеризованные vs некластеризованные (за всю жизнь спросили 1 раз)
- B-Tree vs B+ Tree. Почему B-Tree лучше, чем hash
- Плюсы/минусы индексов
- Составные, покрывающие, частичные индексы
- Селективность индекса
- В чем подвох Create index concurrently?
- Explain vs explain analyze

2) Уровни изоляции
- Какие бывают, чем отличаются, как работают(mvcc)

3) Локи
- Оптимистик/пессимистик и как их реализовать

4) Sql vs NoSql (вопрос больше на кругозор)
- Строковые vs колоночные
- Реляционная модель vs документо-ориентированная

5) Скейлинг бд
- Партиционирование, шардинг, репликации

6) Задача на написание join + group by и having. Тут всегда помогает литкод чтобы вспомнить как писать такие запросы

Вопросы по Кафке 🗒

1) Гарантии доставки(Самый популярный вопрос)
- Transactional inbox/outbox
- Auto commit vs ручной коммит
- Флаг идемпотентности

2) Устройство брокера
- Партиции, топики, оффсеты

3) Продьюсеры и консьюмеры
- Consumer group
- Consumer lag
- Ребалансировка
- Балансировка сообщений на стороне продьюсера

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

Что нового я узнал

1. Чтобы узнать о наличии повторяющегося шаблона в строке, например s = abab, нужно проверить содержится ли эта строка в (s+s) без первого и последнего символов

2. Самая интересная задача на граф - DAG, сначала нужно найти кол-во путей от start до end. Далее усложнение - найти кол-во путей которые еще содержат точки А и E
start -> A -> E -> B -> end (1)
start -> A -> E -> D -> end (1)
start -> C -> F -> G -> end
start -> C -> F -> B -> end

В примере таких путей 2
Разбиваем задачу на поиск кол-ва путей start -> A, A -> E, E -> end и после перемножим эти результаты. Остается понять порядок точек А и E через топологическую сортировку. Код

3. Была задача на DSU(Disjoint Set Union или Union Find). Сделаю отдельный пост про него

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

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

На этой неделе закончился испытательный срок в плату, проект банкоматы, фидбэк - положительный

Впечатления

По стэку стильно, модно, молодежно - свежая версия гошки, postgres, redis, mongo, кубер, aws. Из-за духа стартапа приходится доставать социальные навыки, чтобы выяснить как/что нужно сделать, если раньше этого не делали. Также происходит много дискуссий на архитектурных встречах, убеждать людей/себя не так просто.

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

Понял что мне надоело писать код, сейчас вошел в стадию кризиса 30 поиска себя⌛️

В adventofcode была задача на dsu. О нем я узнал решая литкод, по началу обходил его стороной, потому что почти все задачи на dsu решаются через dfs/bfs, но на некоторые задачи он хорошо ложится и, зная реализацию, задача решается за пару строк

Disjoint Set Union(DSU) - структура данных которая поддерживает разбиение элементов на непересекающиеся множества.

Под капотом dsu - массив и имеет следующие методы

DSU на 3 элемента

arr - [0, 1, 2] # изначально каждый элемент - корень своего множества. 

# Поиск родителя элемента
def find(x): 
 if self.arr[x] == x:
     return self.arr[x]

 return self.find(self.arr[x])

# Объединение элементов и их родителей в одно множество
def union(x, y): 
 real_x = self.find(x)
 real_y = self.find(y)

 self.arr[real_x] = real_y

# Принадлежность элементов к одному и тому же множеству
def is_same(x, y): 
 return self.find(x) == self.find(y)

Возьмем для примера ребра - [[0,1],[0,2],[1,2]], вызовем union для каждого ребра
получим arr - [1, 2, 2]

Получилась связь 0 -> 1 -> 2, все точки принадлежат одному множеству, можно заметить что ребро [1,2] лишнее. В этой задаче как раз это нужно сделать

Реализация dsu которую я привел не оптимальна из-за рекурсии, есть union find быстрее - size и rank реализации

Забавный факт - я проводил интервью по алгоритмам еще в тиньке на студенческую стипендию где была задача на dsu, пришел олимпиадник и закрытыми глазами написал оптимальную реализацию через rank🤨

Поздравляю всех с Новым Годом⛄️⛄️⛄️. Желаю легких алго/систем дизайн собесов, жирных оферов, меньше стресса, больше радости

Спасибо за поддержку и подписку 💗💗💗