Forwarded from бегущий по собесам
Skip List
В рамках реализации Redis CodeCrafters есть глава sorted set, который применяется в дизайне рейтинговых систем(Leaderboards). Sorted set как и некоторые LSM-tree: Cassandra, LevelDB, RocksDB используют под капотом skip list.
Давайте решим design skip list на литкоде. Имейджин твое лицо когда на собесе дали эту задачу😂
Из интересного, skip list вероятностная(probabilistic) структура данных. Я постарался дать небольшое введение для удобного переключения на скрины
Структура skip list - уровни, каждый уровень - отсортированный связный список.
Node - содержит val и массив nexts, через nexts[i] мы выбираем уровень, len(nexts) говорит о высоте текущей Node.
Килер-фича skip list - поиск, вставка, удаление за log(n), все потому что высота ноды выбирается случайно через
Search
Вкратце алгоритм - пока следующий элемент меньше
Insert
Используется доп массив update для сохранения потенциальных ссылок после которых добавится новое значение. Функция -
Erase
С массивом update работаем как и в insert. Уточнение - дубликаты в skip list могут быть и выглядеть как несколько башен, здесь мы решаем удалить самую первую -
В рамках реализации Redis CodeCrafters есть глава sorted set, который применяется в дизайне рейтинговых систем(Leaderboards). Sorted set как и некоторые LSM-tree: Cassandra, LevelDB, RocksDB используют под капотом skip list.
Давайте решим design skip list на литкоде. Имейджин твое лицо когда на собесе дали эту задачу
Из интересного, skip list вероятностная(probabilistic) структура данных. Я постарался дать небольшое введение для удобного переключения на скрины
Структура skip list - уровни, каждый уровень - отсортированный связный список.
Node - содержит val и массив nexts, через nexts[i] мы выбираем уровень, len(nexts) говорит о высоте текущей Node.
Килер-фича skip list - поиск, вставка, удаление за log(n), все потому что высота ноды выбирается случайно через
probability(обычно это 0.5)Search
Вкратце алгоритм - пока следующий элемент меньше
target двигаемся вправо, если значения равны элемент найден. Иначе спускаемся внизInsert
Используется доп массив update для сохранения потенциальных ссылок после которых добавится новое значение. Функция -
get_random_level вычисляет уровень по который мы добавим новый элемент. Описание функции не влезло на скрин поэтому вставлю сюда
def get_random_level(self) -> int:
level = 1
while random.random() < self.probability and level < self.max_level:
level += 1
return level
Erase
С массивом update работаем как и в insert. Уточнение - дубликаты в skip list могут быть и выглядеть как несколько башен, здесь мы решаем удалить самую первую -
candidate = update[0].nexts[0]Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
Forwarded from Sergei Gorlov
Может ли чужая транзакция привести к инциденту в вашей таблице?
Запрос на чтение по нашей таблице деградировал с 10 мс до 1.2 с. Эта таблица участвует в критичном бизнес-процессе, и такая задержка для нас — инцидент. В самой таблице не изменилось ничего: те же индексы, тот же объём запросов, те же данные. Проблема была не на нашей стороне. Чужая транзакция висела более 12 часов и нашей таблицы не касалась.
Дело в том, как Postgres хранит данные.
Поэтому чужая транзакция, пока висела эти 12 часов, запрещала
Почему проблема случилась именно у нас.
Как мы это нашли.
По деградации времени выполнения запроса и увеличению количества мёртвых строк в таблице мы поняли, что кто-то мешает
Мы выполнили следующий запрос для поиска самой старой открытой транзакции.
Нашли транзакцию и убили её.
Вывод: одна долгая транзакция тормозит очистку мусора во всей базе, и первым ложится не тот, кто её открыл, а самая горячая на обновления таблица.
Зачем нужны версии строк и что такое
Запрос на чтение по нашей таблице деградировал с 10 мс до 1.2 с. Эта таблица участвует в критичном бизнес-процессе, и такая задержка для нас — инцидент. В самой таблице не изменилось ничего: те же индексы, тот же объём запросов, те же данные. Проблема была не на нашей стороне. Чужая транзакция висела более 12 часов и нашей таблицы не касалась.
Дело в том, как Postgres хранит данные.
UPDATE не меняет строку на месте, а создаёт новую версию и помечает старую мёртвой. Со временем мёртвых версий накапливается много, и их подчищает фоновый процесс autovacuum. Но удалить мёртвую версию он может, только когда она уже точно никому не видна, то есть когда её не может прочитать ни одна живая транзакция.autovacuum ориентируется на самую старую активную транзакцию во всей базе. Пока она жива, её снапшот теоретически может обратиться к старым версиям строк, поэтому вакуум обязан их сохранить. Не в той таблице, где выполняется транзакция. Во всех сразу.Поэтому чужая транзакция, пока висела эти 12 часов, запрещала
autovacuum чистить мусор по всей базе.Почему проблема случилась именно у нас.
autovacuum встал для всех таблиц одинаково, но страдают те, которые быстро накапливают мусор. У нас это таблица со статусной моделью: воркер непрерывно гоняет по ней UPDATE (одна запись может обновляться до 10-20 раз в короткий интервал времени). Каждая смена статуса плодит мёртвую версию. Обычно autovacuum успевает. Но когда он встал на 12 часов, мусор копился непрерывно, таблица распухла, и запрос пошёл через гору мёртвых строк.Как мы это нашли.
По деградации времени выполнения запроса и увеличению количества мёртвых строк в таблице мы поняли, что кто-то мешает
autovacuum их удалять. Мы выполнили следующий запрос для поиска самой старой открытой транзакции.
SELECT pid, state,
xact_start, now() - xact_start AS duration, query
FROM pg_stat_activity
WHERE state <> 'idle'
ORDER BY xact_start ASC;
Нашли транзакцию и убили её.
autovacuum тут же подчистил мусор, мёртвые строки ушли в ноль и запрос вернулся к 10 мс. Вывод: одна долгая транзакция тормозит очистку мусора во всей базе, и первым ложится не тот, кто её открыл, а самая горячая на обновления таблица.
Зачем нужны версии строк и что такое
MVCC — разберу отдельным постом, а может, и видео.Полезный бенч для тех, кто запускает PostgreSQL в AWS
Коллега с курса, @anivaniuk, прогнал PostgreSQL на разных AWS тачках и собрал результаты в классный интерактивный тул. Удобно, если нужно быстро прикинуть, какой инстанс даст лучшее соотношение цены и производительности.
https://postgres.saneengineer.com/
Коллега с курса, @anivaniuk, прогнал PostgreSQL на разных AWS тачках и собрал результаты в классный интерактивный тул. Удобно, если нужно быстро прикинуть, какой инстанс даст лучшее соотношение цены и производительности.
https://postgres.saneengineer.com/
PostgreSQL on AWS
PostgreSQL on AWS: Size & Benchmark EC2 Instances
Find the cheapest AWS EC2 instance that clears your PostgreSQL throughput target — real benchmarks of 26 instance types across 8 families.
Писать код и закрывать задачи - нет!
Сидеть на встречках - да!
Хз, как я до этого докатился.
На скрине мой реальный календарь на завтра. И нет, я не ушёл в менеджмент, я всё ещё бэкенд-инженер.
#xBackend_КорпоБудни
Как вы разруливаете такие накладки в календаре?
Anonymous Poll
39%
Открываю обе встречи и просто молчу
3%
Выбираю созвон рандомно
35%
Иду туда, где интересно
15%
Говорю, что инет лагает и спокойно пишу код
8%
Свой вариант в комментах
Please open Telegram to view this post
VIEW IN TELEGRAM
Перф....
У нас в компании начался перформанс ревью. Для тех, кто не знает, это такое корпо мероприятие длиной в полтора-два месяца. В это время решают, кому насыпать денег или повысить грейд, а кого просто похлопать по плечу.
Это мой второй перф в этой компании. В прошлый раз меня технично прокатили сказав, что я большой молодец и отлично поработал, но по итогу не дали нихера - ни бабок, ни грейд-апа.
Повторять этот факап я не хочу, поэтому мне нужны ваши лайфхаки по борьбе с корпо бюрократией.
Поделитесь пожалуйста в комментах опытом:
• Как заполнять селф ревью, чтоб прям не докопаться?
• Как правильно подсвечивать свои факапы, чтобы они выглядели как зоны роста, а не провалы?
• Как писать пир ревью, чтобы и коллегам не подгадить и себе в ногу не выстрелить?
• Как защитить результат, если вдруг включится режим "бюджета нет"?
В общем, спасайте работягу)
У нас в компании начался перформанс ревью. Для тех, кто не знает, это такое корпо мероприятие длиной в полтора-два месяца. В это время решают, кому насыпать денег или повысить грейд, а кого просто похлопать по плечу.
Это мой второй перф в этой компании. В прошлый раз меня технично прокатили сказав, что я большой молодец и отлично поработал, но по итогу не дали нихера - ни бабок, ни грейд-апа.
Повторять этот факап я не хочу, поэтому мне нужны ваши лайфхаки по борьбе с корпо бюрократией.
Поделитесь пожалуйста в комментах опытом:
• Как заполнять селф ревью, чтоб прям не докопаться?
• Как правильно подсвечивать свои факапы, чтобы они выглядели как зоны роста, а не провалы?
• Как писать пир ревью, чтобы и коллегам не подгадить и себе в ногу не выстрелить?
• Как защитить результат, если вдруг включится режим "бюджета нет"?
В общем, спасайте работягу)
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥18 7 7
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥19👍8 5
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥10👍5 5
Please open Telegram to view this post
VIEW IN TELEGRAM
👍10 4🔥3
Please open Telegram to view this post
VIEW IN TELEGRAM
20🔥13🍌3 2💩1
Барса Флика - ты прекрасна!
Болею за Барсу с 2010 года. За это время было много разных версий этой команды: тики-така Гвардиолы, трио Месси-Суарес-Неймар, была и бесхребетная Барса, которая раз за разом вылетала из плейофф ЛЧ.
Как по мне, нынешняя Барса - это просто идеальная реклама футбола. Каждый матч - фестиваль голов на любой вкус и цвет. И сами забьют, и сопернику дадут забить. Скучно вообще не бывает.
Если хотите просто посмотреть футбик и получить удовольствие, то включайте матчи Барсы. Не пожалеете)
Болею за Барсу с 2010 года. За это время было много разных версий этой команды: тики-така Гвардиолы, трио Месси-Суарес-Неймар, была и бесхребетная Барса, которая раз за разом вылетала из плейофф ЛЧ.
Как по мне, нынешняя Барса - это просто идеальная реклама футбола. Каждый матч - фестиваль голов на любой вкус и цвет. И сами забьют, и сопернику дадут забить. Скучно вообще не бывает.
Если хотите просто посмотреть футбик и получить удовольствие, то включайте матчи Барсы. Не пожалеете)
👍6💯6💩2🔥1
Не всегда проблема в коде
Год назад, когда только устроился на работу, мне дали задачу: понять, почему сервис не всегда может загрузить файлы в S3. В нашем случае это был селф-хостед MinIO.
Небольшие файлы обычно загружались нормально, а вот большие падали с ошибкой:
Начал с бизнесового кода. Ничего криминального там не нашёл. Потом решил, что проблема может быть в либе: в ошибке чётко говорится, что значение хедера не соответствует количеству полученных байт. Может, либа как-то не так режет файлы? Нет, там тоже всё ок.
При этом я был настолько уверен, что проблема именно в коде, что другие варианты даже не рассматривал🤦♂ 🤦♂ 🤦♂
В какой-то момент мне надоело копаться в коде и я решил пойти к девопсам. Те сказали, что перед S3 стоит nginx и нужно глянуть конфиги.
Ну полез я в его конфиги и нашёл директиву😎 😎 😎
Я это всё к тому, что сервисы сейчас обмазаны проксями, балансерами, файрволами и прочим. Я сам себе сузил область поиска до кода и из-за этого долго копал не туда. Поэтому иногда полезно посмотреть, что происходит за пределами сервиса. Возможно, это сэкономит вам часы)
Если у вас на работе были похожие истории, делитесь в комментах. Интересно почитать)
#xBackend_Инфра #xBackend_Сети
Год назад, когда только устроился на работу, мне дали задачу: понять, почему сервис не всегда может загрузить файлы в S3. В нашем случае это был селф-хостед MinIO.
Небольшие файлы обычно загружались нормально, а вот большие падали с ошибкой:
IncompleteBody: You did not provide the number of bytes specified by the Content-Length HTTP header.Начал с бизнесового кода. Ничего криминального там не нашёл. Потом решил, что проблема может быть в либе: в ошибке чётко говорится, что значение хедера не соответствует количеству полученных байт. Может, либа как-то не так режет файлы? Нет, там тоже всё ок.
При этом я был настолько уверен, что проблема именно в коде, что другие варианты даже не рассматривал
В какой-то момент мне надоело копаться в коде и я решил пойти к девопсам. Те сказали, что перед S3 стоит nginx и нужно глянуть конфиги.
Ну полез я в его конфиги и нашёл директиву
chunked_transfer_encoding off. Чуйка подсказала мне, что во всём виновата именно она. Решили потестить. Убрали директиву, раскатали и все файлы начали нормально загружаться Я это всё к тому, что сервисы сейчас обмазаны проксями, балансерами, файрволами и прочим. Я сам себе сузил область поиска до кода и из-за этого долго копал не туда. Поэтому иногда полезно посмотреть, что происходит за пределами сервиса. Возможно, это сэкономит вам часы)
Если у вас на работе были похожие истории, делитесь в комментах. Интересно почитать)
#xBackend_Инфра #xBackend_Сети
Please open Telegram to view this post
VIEW IN TELEGRAM
👍13🔥5 2😈1
Please open Telegram to view this post
VIEW IN TELEGRAM
💯11👍4🔥4💩2
Переквалификация из инженера в повара идёт полным ходом)
Нужно поработать над подачей, но получилось очень вкусно
Может когда-нибудь сделаю курс "Айтишник на кухне", продам его и на заработанные деньги открою кулинарную мастерскую
Если захотите приготовить такую же курицу в сливочно-горчичном соусе - алгоритм в комментах)
Нужно поработать над подачей, но получилось очень вкусно
Может когда-нибудь сделаю курс "Айтишник на кухне", продам его и на заработанные деньги открою кулинарную мастерскую
Если захотите приготовить такую же курицу в сливочно-горчичном соусе - алгоритм в комментах)
1😁15🔥12 2💩1 1