DSA, system design и behavioral для финального рывка
Я завершил собирать свою 'боевую' библиотеку для финального рывка подготовки.
Приехали вот только что:
- новая книга Остина МакДоналда из Меты про подготовку к бихейву like a pro. Она неожиданно оказалось цветной внутри, с красивыми акварельными иллюстрациями 😍
- второй том Алекса Ху по system design. Формат подрос как и количество деталей в самой книге, выглядит скорее как v2.0, чем просто второй том. Но формат уже менее travel-friendly
- паттерны решения DSA/LeetCode снова от Алекса. Захотел попробовать альтернативу моей любимой EPIP с глубоким погружением в алгоритмы. У Алекса как и в system design книге много очень схем и картинок, книга-кандидат в refresher перед интервью как один из сценариев.
Посмотрю их в деле, расскажу вам.
@faangiscalling
Я завершил собирать свою 'боевую' библиотеку для финального рывка подготовки.
Приехали вот только что:
- новая книга Остина МакДоналда из Меты про подготовку к бихейву like a pro. Она неожиданно оказалось цветной внутри, с красивыми акварельными иллюстрациями 😍
- второй том Алекса Ху по system design. Формат подрос как и количество деталей в самой книге, выглядит скорее как v2.0, чем просто второй том. Но формат уже менее travel-friendly
- паттерны решения DSA/LeetCode снова от Алекса. Захотел попробовать альтернативу моей любимой EPIP с глубоким погружением в алгоритмы. У Алекса как и в system design книге много очень схем и картинок, книга-кандидат в refresher перед интервью как один из сценариев.
Посмотрю их в деле, расскажу вам.
@faangiscalling
👍2🔥1🙏1
Snowflake ID: как Twitter решил проблему генерации уникальных ID в распределённой системе 🪪
Раньше писал про UUID — уникальный ID без центрального сервера, но случайный и не сортируется по времени в классической версии v4.
Twitter хотел одновременно:
– генерировать ID на сотнях серверов независимо
– гарантировать уникальность
– обходиться без центральной БД
– получать ID, отсортированные времени с определенной точностью
– уложиться в 64 бита для уменьшения размера индексов, кеша
Главный челлендж здесь — разрешить конфликт между уникальностью, распределённостью и упорядоченностью по времени.
Так в 2010 году появился snowflake (не связан с хранилищем для аналитики Snowflake, а просто отражение концепции, что snowflake, то есть снежинка по-русски, никогда не повторяется, они все разные, что и ждешь от генератора ID).
Идея: один 64-битный ID с определенной структурой, решающей челлендж:
⁃ 1 резервный бит
⁃ timestamp (41 бит)
⁃ worker ID (10 бит)
⁃ sequence (12 бит)
Timestamp — миллисекунды с эпохи Twitter (с 2010 года, а не 1970 как у UNIX), в старших битах → дает простое числовое сравнение ID = сортировка по времени с точностью до миллисекунды. Этой длины в 41 бит хватит почти на 70 лет
Worker ID — какой датацентр (5 бит) и какой сервер (еще 5 бит) создал ID, по сути номер “воркера” (0 - 1023).
Sequence — номер ID внутри текущей миллисекунды у конкретного "воркера", каждую миллисекунду обнуляется (0 - 4095)
Два "воркера" создают ID независимо и эти ID никогда не пересекаются:
Какое максимальное количество ID можно генерировать в секунду?
12 бит sequence = 4096 ID с одного "воркера" за 1 миллисекунду → ~4 млн ID с одного “воркера” за 1 секунду (1000 миллисекунд)→ ~4 млрд ID на 1024 “воркерах” за секунду. Более чем достаточно для Twitter и для других практических ситуаций.
Сама идея «timestamp внутри ID» не нова — сила snowflake в удачной комбинации: distributed generation + uniqueness + temporal ordering + 64-bit integer.
Отсюда пошли Sonyflake, Instagram-style ID и другие «flake»-форматы, а позже — ULID и UUIDv7, развивающие ту же идею.
Так что хороший system design — это не всегда новый алгоритм. Иногда это просто удачно разложить требования по битам. 🙂
@faangiscalling
Раньше писал про UUID — уникальный ID без центрального сервера, но случайный и не сортируется по времени в классической версии v4.
Twitter хотел одновременно:
– генерировать ID на сотнях серверов независимо
– гарантировать уникальность
– обходиться без центральной БД
– получать ID, отсортированные времени с определенной точностью
– уложиться в 64 бита для уменьшения размера индексов, кеша
Главный челлендж здесь — разрешить конфликт между уникальностью, распределённостью и упорядоченностью по времени.
Так в 2010 году появился snowflake (не связан с хранилищем для аналитики Snowflake, а просто отражение концепции, что snowflake, то есть снежинка по-русски, никогда не повторяется, они все разные, что и ждешь от генератора ID).
Идея: один 64-битный ID с определенной структурой, решающей челлендж:
⁃ 1 резервный бит
⁃ timestamp (41 бит)
⁃ worker ID (10 бит)
⁃ sequence (12 бит)
Timestamp — миллисекунды с эпохи Twitter (с 2010 года, а не 1970 как у UNIX), в старших битах → дает простое числовое сравнение ID = сортировка по времени с точностью до миллисекунды. Этой длины в 41 бит хватит почти на 70 лет
Worker ID — какой датацентр (5 бит) и какой сервер (еще 5 бит) создал ID, по сути номер “воркера” (0 - 1023).
Sequence — номер ID внутри текущей миллисекунды у конкретного "воркера", каждую миллисекунду обнуляется (0 - 4095)
Два "воркера" создают ID независимо и эти ID никогда не пересекаются:
timestamp | worker 17 | sequence 42
timestamp | worker 18 | sequence 7
Какое максимальное количество ID можно генерировать в секунду?
12 бит sequence = 4096 ID с одного "воркера" за 1 миллисекунду → ~4 млн ID с одного “воркера” за 1 секунду (1000 миллисекунд)→ ~4 млрд ID на 1024 “воркерах” за секунду. Более чем достаточно для Twitter и для других практических ситуаций.
Сама идея «timestamp внутри ID» не нова — сила snowflake в удачной комбинации: distributed generation + uniqueness + temporal ordering + 64-bit integer.
Отсюда пошли Sonyflake, Instagram-style ID и другие «flake»-форматы, а позже — ULID и UUIDv7, развивающие ту же идею.
Так что хороший system design — это не всегда новый алгоритм. Иногда это просто удачно разложить требования по битам. 🙂
@faangiscalling
👍5🙏1
Качество жизни: Франция или не Франция🇫🇷
Мой друг, который выбирает страну для релокации спросил меня вчера про Францию 🇫🇷 и про мои впечатления. И про свое желание релоцироваться с 'улучшением качества жизни'. Сравнивает с Лондоном 🇬🇧 и Дубаем 🇦🇪
По умолчанию он представлял себе в голове концепцию улучшения качества жизни как увеличение дохода.
Я объяснил ему, что концепция самой Франции 🇫🇷 про 'улучшение качества жизни' не столько про увеличение дохода, а сколько про увеличение:
- стабильности (почти нельзя уволить)
- вкусности (очень вкусные продукты)
- красоты (шато на каждом шагу, парки, горы, пляжи)
- свободного времени (отпуск 2 месяца, спокойные обеды по 1-2 часа)
- спортивных активностей (огромное количество оборудованных веломаршрутов, бегунов, скалолазов)
- культурных мероприятий (выставки всего и вся, парижский автосалон, фестивали вина, сыра, ретро-автомобилей, фейерверков, музыки, Роби Вильямсов и Леди Гаг)
- отдыха в красивых местах (полно недорогих кемпингов)
Если нужно именно увеличить доход/капитал, то это однозначно Лондон 🇬🇧
Если достаточно просто улучшить качество жизни и жить популярный сейчас формат slow life – bienvenue en France! 🇫🇷
@faangiscalling
Мой друг, который выбирает страну для релокации спросил меня вчера про Францию 🇫🇷 и про мои впечатления. И про свое желание релоцироваться с 'улучшением качества жизни'. Сравнивает с Лондоном 🇬🇧 и Дубаем 🇦🇪
По умолчанию он представлял себе в голове концепцию улучшения качества жизни как увеличение дохода.
Я объяснил ему, что концепция самой Франции 🇫🇷 про 'улучшение качества жизни' не столько про увеличение дохода, а сколько про увеличение:
- стабильности (почти нельзя уволить)
- вкусности (очень вкусные продукты)
- красоты (шато на каждом шагу, парки, горы, пляжи)
- свободного времени (отпуск 2 месяца, спокойные обеды по 1-2 часа)
- спортивных активностей (огромное количество оборудованных веломаршрутов, бегунов, скалолазов)
- культурных мероприятий (выставки всего и вся, парижский автосалон, фестивали вина, сыра, ретро-автомобилей, фейерверков, музыки, Роби Вильямсов и Леди Гаг)
- отдыха в красивых местах (полно недорогих кемпингов)
Если нужно именно увеличить доход/капитал, то это однозначно Лондон 🇬🇧
Если достаточно просто улучшить качество жизни и жить популярный сейчас формат slow life – bienvenue en France! 🇫🇷
@faangiscalling
👍4❤2🔥2