Видеоразбор этой задачи на русском языке можно посмотреть здесь - https://www.youtube.com/watch?v=U_qR7HFZIbE

Проектирование Tinder

Постановка задачи

❤️ Что такое Tinder?

Tinder - это мобильное приложение для знакомств. Пользователи видят профили друг друга и свайпают (смахивают, swipe) вправо, если профиль понравился, и влево - если нет. Приложение использует геоданные и пользовательские фильтры, чтобы показывать потенциальные матчи (совпадения, match) поблизости.

Функциональные требования

Основные требования

Пользователи могут создать профиль с предпочтениями (например, возрастной диапазон, интересы) и указать максимальную дистанцию.
Пользователи могут просматривать список потенциальных матчей, соответствующих их предпочтениям и находящихся в пределах максимальной дистанции от текущей локации.
Пользователи могут свайпать вправо/влево по одному профилю за раз, выражая “да” или “нет” по отношению к другим пользователям.
Пользователи получают уведомление о матче, если они взаимно свайпнули друг друга вправо.

За рамками задачи

Пользователи могут загружать фотографии.
Пользователи могут общаться в личных сообщениях после матча.
Пользователи могут покупать и использовать другие premium функции.

Важно отметить, что в этой задаче обычно фокусируются на “ленте рекомендаций” и пользовательском опыте свайпов, а не на вспомогательных возможностях. Если вы не уверены, на каких функциях сфокусироваться для такого приложения, стоит выяснить у интервьюера, какая часть системы для него наиболее важна. Обычно это либо часть продукта, которая делает его уникальным, либо наиболее сложная часть продукта.

Нефункциональные требования

Основные требования

Система должна обеспечивать сильную согласованность (strong consistency) для свайпов. Если пользователь свайпнул “да” на человека, который уже свайпнул “да” на него, оба должны получить уведомление о матче.
Система должна масштабироваться под большое количество ежедневных активных / одновременных пользователей (20 млн DAU, в среднем ~100 свайпов на пользователя в день).
Система должна быстро формировать список потенциальных матчей (< 300 мс).
Система не показывает повторно профили, по которым пользователь уже свайпал.

За рамками задачи

Система должна предотвращать использование фейковых профилей.

На доске это могло бы выглядеть примерно так:

Подготовка

Планирование подхода

Прежде чем переходить к проектированию системы, важно на секунду остановиться и продумать стратегию. К счастью, для “продуктовых” задач план обычно простой: последовательно собирать дизайн, проходя по функциональным требованиям одно за другим. Так вы сохраните фокус и не утонете в деталях.

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

Проектирование API

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

Для Tinder основные сущности довольно очевидны:

User: это и пользователь приложения, и профиль, который показывают другим пользователям.
Swipe: выражение “да” или “нет” по отношению к профилю другого пользователя. Содержит информацию о пользователе, который свайпает (swiping_user), и пользователе, которого свайпают (target_user).
Match: связь между двумя пользователями, возникающая в результате взаимного свайпа “да”.

В реальном интервью короткого списка, как выше, часто достаточно. Главное - проговорить сущности с интервьюером и убедиться, что вы оба одинаково их понимаете.

API - основной интерфейс, через который пользователи взаимодействуют с системой. Его полезно определить с самого начала, поскольку он направляет high-level дизайн. Обычно нам нужен один эндпоинт на каждое функциональное требование.

Первый эндпоинт - создание/обновление профиля пользователя. Конечно, в реальном Tinder там будут фото, биография и т. п., но в этой задаче сфокусируемся на предпочтениях для поиска и сопоставления.

POST /profile
{
  min_age,
  max_age,
  max_distance,
  interested_in: "female" | "male",
  ...
}

Далее нужен эндпоинт, который возвращает “ленту” профилей потенциальных кандидатов.

GET /feed?lat={}&long={} -> User[]

Заметьте: нам не нужно передавать фильтры (возраст, интересы, дистанцию и т. п.), потому что мы считаем, что пользователь уже сохранил их в настройках - и мы можем подгрузить их на сервере. Текущая локация может постоянно меняться, поэтому мы передаем ее с клиента.

Может возникнуть желание заранее продумать пагинацию для GET /feed. Для Tinder это обычно избыточно, вместо формирования страниц, приложение просто вызовет эндпоинт еще раз, если текущий список потенциальных кандидатов закончился.

Также нужен эндпоинт для свайпа:

POST /swipe/{userId}
{
  "decision": "yes" | "no"
}

В каждом из этих запросов информация о пользователе передается в заголовках (через session token или auth token). Это распространенный паттерн, так мы можем обеспечивать аутентификацию/авторизацию и безопасность. Не стоит передавать пользовательские данные в теле запроса: в этом случае их можно легко подделать.

Высокоуровневый дизайн

1. Пользователи могут создать профиль с предпочтениями и указать максимальную дистанцию

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

Мы принимаем запрос POST /profile и сохраняем настройки в базе. Для старта нам достаточно простой архитектуры Клиент -> Сервер -> База данных. При этом, если сразу очевидно, что мы будем использовать несколько сервисов, то можно сразу добавить на схему API Gateway для маршрутизации запросов.

Клиент: пользователи взаимодействуют с системой через мобильное приложение.
API Gateway: маршрутизирует запросы в нужные сервисы. В данном случае - в сервис профилей.
Сервис профилей: обрабатывает запросы на профили, обновляя предпочтения в базе.
Хранилище профилей: хранит информацию о профилях, предпочтениях и другие релевантные данные.

Когда пользователь создает профиль:

Клиент отправляет POST /profile с данными профиля в теле запроса.
API Gateway направляет запрос в сервис профилей.
Сервис профилей обновляет предпочтения пользователя в базе.
Результат возвращается клиенту.

2. Пользователи могут просматривать список потенциальных матчей

Когда пользователь открывает приложение, он сразу видит список профилей для свайпа. Эти профили должны соответствовать фильтрам (возраст, интересы и т. п.), а также географии пользователя (например “< 2 км”, “< 5 км”, “< 15 км”).

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

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

Простейший запрос мог бы выглядеть так:

SELECT * FROM users
WHERE age BETWEEN preferredAgeMin AND preferredAgeMax
AND gender = preferredInterestedIn
AND lat BETWEEN userLat - preferredDistance AND userLat + preferredDistance
AND long BETWEEN userLong - preferredDistance AND userLong + preferredDistance

Когда пользователь запрашивает новый набор профилей:

Клиент отправляет GET /feed, передавая текущую локацию через query‑параметры.
API Gateway направляет запрос в сервис профилей.
Сервис профилей запрашивает базу данных, выбирая пользователей по предпочтениям и локации.
Результаты возвращаются клиенту.

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

3. Пользователи могут свайпать вправо/влево и выражать да/нет по отношению к другим пользователям

Когда пользователи получили список профилей, они готовы свайпать. Система должна записывать каждый свайп и сообщать пользователю о матче, если тот, кому он свайпнул “да”, уже ранее свайпнул “да” пользовательский профиль.

Нам нужен способ сохранять свайпы и проверять, произошел ли матч. Снова начнем с простого (и неидеального) решения и улучшим его в детальном погружении.

Добавим два новых компонента:

Сервис свайпов: сохраняет свайпы и проверяет матчи.
Хранилище свайпов: хранит данные свайпов.

Почему мы выбрали отдельный сервис и отдельное хранилище?

Обоснование: создание/обновление профиля происходят существенно реже, чем запись свайпов. Разделив сервисы, мы можем независимо масштабировать сервис свайпов. Аналогично, по данным, свайпов будет очень много. При 20 млн DAU × 100 свайпов/день × ~100 байт на свайп получается порядка ~200GB данных в день. Такой объем и нагрузку хорошо сможет обработать хранилище оптимизированное для записи такое как Cassandra (которое может быть не лучшим выбором для профилей). Кроме того, отдельное хранилище позволяет оптимизировать паттерны доступа и кэширование для свайпов без влияния на сервис профилей.

Такое разделение - не универсальный ответ для всех систем. Но здесь плюсы перевешивают минусы.

Поскольку свайп - действие почти без усилий, можно ожидать большой поток записей. Если принять 20 млн DAU и в среднем 100 свайпов/день, это 2 млрд записей в день. Это почти наверняка означает, что данные нужно партиционировать.

Cassandra хорошо подходит как хранилище свайпов. Мы можем партиционировать по swiping_user_id. Тогда проверка “свайпал ли пользователь A пользователя B” будет быстрой: мы предсказуемо идем в один раздел (partition). Также Cassandra хорошо выдерживает большие объемы записей благодаря архитектуре своего хранения (CommitLog + Memtables + SSTables). Недостатком использования Cassandra здесь является конечная согласованность для данных о свайпах. Мы обсудим способы нивелировать этот недостаток когда будем погружаться в детали.

Когда пользователь свайпает:

Клиент отправляет POST /swipe/{userId} с userId профиля и результатом свайпа (вправо/влево).
API Gateway направляет запрос в сервис свайпов.
Сервис свайпов записывает свайп в хранилище свайпов.
Сервис свайпов проверяет наличие обратного свайпа и, если он есть, сообщает клиенту о матче.

4. Пользователи получают уведомление о матче при взаимном свайпе

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

Уведомить Боба просто: это мы уже делаем. Поскольку он - второй, сразу после свайпа вправо мы проверяем, лайкнула ли Алиса, и если да - показываем уведомление на устройстве Боба.

Но что насчет Алисы? Она могла свайпнуть Боба несколькими днями ранее. Нам нужно отправить push‑уведомление на устройство Алисы, сообщив, что у нее новый матч.

Для этого будем использовать нативные сервисы push-уведомлений, такие как Apple Push Notification Service (APNS) или Firebase Cloud Messaging (FCM).

APNS и FCM - это службы push‑уведомлений, с собственным набором API и SDK, которые мы можем использовать для отправки push‑уведомлений на пользовательские устройства.

Кратко повторим полный процесс свайпа с учетом пушей:

Некоторое время назад Алиса свайпнула вправо Боба, и мы сохранили это в хранилище свайпов.
Боб свайпает вправо Алису.
Сервер проверяет наличие обратного свайпа и находит его.
Мы показываем уведомление о матче на устройстве Боба сразу после свайпа.
Мы отправляем push‑уведомление через APNS/FCM Алисе, что у нее новый матч.

Исходя из функциональных требований, мы не должны заботиться о том, что происходит после матча, поэтому мы можем не углубляться в детали хранения матчей. Также можно предположить, что за доставку push‑уведомлений отвечает внешний сервис. Важно проговаривать такие допущения с интервьюером.

Потенциальные погружения в детали

К этому моменту у нас есть базовая работающая система, удовлетворяющая функциональным требованиям. Но есть несколько областей, куда полезно углубиться, чтобы улучшить производительность, масштабируемость и т.д. В зависимости от вашего уровня, от вас ожидается, что вы будете направлять дискуссию на эти темы, представляющие наибольший интерес.

1. Как обеспечить согласованность и низкую задержку при свайпах?

Рассмотрим проблемный сценарий. Представим, что Алиса и Боб почти одновременно свайпают друг друга вправо. Порядок операций может оказаться примерно таким:

Свайп Алисы приходит на сервер - мы проверяем обратный свайп. Его нет.
Свайп Боба приходит на сервер - мы проверяем обратный свайп. Его нет.
Мы сохраняем свайп Алисы на Боба.
Мы сохраняем свайп Боба на Алису.

В итоге свайпы сохранены, но мы упустили момент создания матча и уведомления. Оба человека будут жить дальше, не зная о совпадении - настоящая любовь так и не случится. Мы не можем этого допустить!

Стоит заметить: можно решить эту проблему и без сильной согласованности. Например, сделать отдельный процесс согласования (reconciliation), который периодически пробегает по свайпам и создает матчи там, где они должны были появиться. Для таких случаев можно отправить уведомления обоим пользователям. Оба пользователя решат, что второй человек свайпнул их прямо сейчас. Это позволило бы приоритизировать доступность перед согласованностью и было бы интересным компромиссом для обсуждения. Однако, задача собеседования станет менее сложной, и, в целях оценки ваших навыков, интервьюер может предложить все же спроектировать решение, которое приоритизирует согласованность.

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

Хорошее решение: Транзакции

Подход

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

В Cassandra есть базовая поддержка того, что они называют легковесные транзакции (Lightweight Transactions, LWT), но это не полноценные ACID‑транзакции. LWT используют консенсусный протокол Paxos для обеспечения линеаризуемой согласованности (linearizable consistency) для конкретных операций, но только в рамках одного раздела (partition). Между разделами они не дают атомарности, уровней изоляции и откатов. Также LWT имеют существенные накладные расходы из‑за нескольких сетевых коммуникаций (round-trips) между нодами. Это делает такие транзакции подходящими в основном для простых условных обновлений.

Проблемы

Главная проблема при этом подходе - масштабируемость. 2 млрд свайпов в день не поместятся в один раздел, а транзакции на несколько разделов LWT не поддерживают.

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

Отличное решение: Транзакции в одном разделе

Подход

Можно использовать LWT транзакции Cassandra, атомарно обрабатывая свайпы. Ключевая идея - гарантировать, что все свайпы между двумя пользователями попадают в один раздел.

Сперва создадим таблицу с составным ключом, который группирует пару пользователей:

CREATE TABLE swipes (
    user_pair text,      -- ключ партиционирования: smaller_id:larger_id
    from_user uuid,      -- кластерный ключ
    to_user uuid,        -- кластерный ключ
    direction text,
    created_at timestamp,
    PRIMARY KEY ((user_pair), from_user, to_user)
);

При свайпе формируем user_pair, отсортировав id, для обеспечения согласованности:

def get_user_pair(user_a, user_b):
    # Отсортируем id так, чтобы (A->B) и (B->A) были в одном разделе
    sorted_ids = sorted([user_a, user_b])
    return f"{sorted_ids[0]}:{sorted_ids[1]}"

def handle_swipe(from_user, to_user, direction):
    user_pair = get_user_pair(from_user, to_user)

    # Обе операции выполняются атомарно в одном разделе
    batch = """
    BEGIN BATCH
        INSERT INTO swipes (user_pair, from_user, to_user, direction, created_at)
        VALUES (?, ?, ?, ?, ?);

        SELECT direction FROM swipes
        WHERE user_pair = ?
        AND from_user = ?
        AND to_user = ?;
    APPLY BATCH;
    """

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

Проблемы

Хотя это решение элегантно реализует необходимую функциональность, оно создает некоторые эксплуатационные проблемы. По мере того, как пары пользователей со временем накапливают историю, размеры разделов могут значительно вырасти, что потенциально влияет на производительность. Кроме того, высокоактивные пользователи могут создавать “горячие” разделы, получающие непропорционально большой объем трафика. Чтобы решить эти проблемы, нам нужна надежная стратегия архивирования или удаления старых данных свайпов, предотвращающая неограниченный рост разделов и сохраняющая при этом важные исторические данные.

Отличное решение: Redis для атомарных операций

Подход

Redis еще лучше подходит для согласованности, которая нужна в логике матчинга по свайпам. Cassandra хороша для надежного хранения огромных объемов данных, но не так хорошо при исполнении атомарных операций, которые нужны для обнаружения матча в реальном времени. Поэтому можно использовать Redis для атомарной обработки свайпов, а Cassandra - как надежный слой хранения.

Ключевая идея та же: свайпы между одной и той же парой пользователей должны попадать на один шард Redis. Можно добиться этого, формируя ключ из двух user_id в детерминированном порядке.

Структура ключа и значения:

Key: "swipes:123:456"
Value: {
  "123_swipe": "yes",
  "456_swipe": "no"
}

def get_key(user_a, user_b):
    # Отсортируем id так, чтобы (A->B) и (B->A) были в одном разделе
    sorted_ids = sorted([user_a, user_b])
    return f"swipes:{sorted_ids[0]}:{sorted_ids[1]}"

def handle_swipe(from_user, to_user, direction):
    key = get_key(from_user, to_user)

    # Используем Redis хеш для хранения свайпов обоих пользователей
    # Хеш имеет два поля: user1_swipe и user2_swipe
    script = """
    redis.call('HSET', KEYS[1], ARGV[1], ARGV[2])
    return redis.call('HGET', KEYS[1], ARGV[3])
    """

    # Выполняем атомарно используя Lua скрипт
    other_swipe = redis.eval(
        script,
        keys=[key],
        args=[
            f"{from_user}_swipe",  # поле для установки
            direction,             # наш свайп
            f"{to_user}_swipe"     # поле для проверки
        ]
    ) # Возвращает значение другого пользователя

    # Если другой пользователь тоже свайпнул вправо, это матч!
    if direction == 'right' and other_swipe == 'right':
        create_match(from_user, to_user)

Используя атомарные операции Redis через Lua скрипт, мы можем гарантировать, что запись свайпа и проверка совпадения выполняются как одна операция. Это дает нам необходимую согласованность и высокую производительность благодаря тому, что Redis работает в памяти. Система масштабируется горизонтально, поскольку мы можем добавлять больше узлов Redis, а согласованное хеширование гарантирует, что связанные свайпы остаются вместе.

Проблемы

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

Управление памятью - еще один фактор, который следует учитывать, но поскольку мы используем Cassandra в качестве надежного уровня хранения, мы можем быть агрессивными в отношении истечения срока хранения данных из Redis. Мы можем периодически сбрасывать данные свайпов из Redis в Cassandra и сохранять в Redis только недавние свайпы. Если мы когда-либо потеряем данные Redis из-за сбоя узла, мы потеряем только возможность обнаруживать матчи для самых недавних свайпов - пользователи всегда могут свайпнуть снова, и мы не теряем историческую запись в Cassandra.

Этот гибридный подход дает нам лучшее из обоих инструментов: строгую согласованность и атомарные операции Redis для обнаружения матчей в реальном времени в сочетании с надежностью Cassandra и возможностями хранения исторических данных. Система остается высокодоступной и масштабируемой, одновременно удовлетворяя нашему основному требованию согласованности и немедленного обнаружения матчей.

2. Как обеспечить быструю загрузку списка потенциальных матчей?

Когда пользователь открывает приложение, он хочет начать свайпать сразу. Он не хочет ждать, пока мы построим ему список потенциальных матчей.

В высокоуровневом дизайне мы делали медленный запрос каждый раз, когда нужно сгенерировать новый список:

SELECT * FROM users
WHERE age BETWEEN preferredAgeMin AND preferredAgeMax
AND gender = preferredInterestedIn
AND lat BETWEEN userLat - preferredDistance AND userLat + preferredDistance
AND long BETWEEN userLong - preferredDistance AND userLong + preferredDistance

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

Хорошее решение: Индексированные БД для real-time запросов

Подход

Один из способов добиться низкой задержки - использовать индексированные БД для запросов реального времени. Если создать индексы по полям, используемым при построении списка (предпочтения, возраст, и особенно geo‑данные), можно сильно ускорить время ответа. Геопространственный индекс позволяет эффективно находить пользователей в заданной области.

Для масштабируемости и требований Tinder можно использовать БД оптимизированную для поиска вроде Elasticsearch или OpenSearch. Они заточены под быстрый поиск и сложные запросы, что делает их пригодными для обработки больших объемов данных с минимальной задержкой.

Индексированные БД для запросов списка потенциальных матчей

Проблемы

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

Обычно это решают через механизм Change Data Capture (CDC). Это шаблон, который фиксирует изменения базы данных (вставки, обновления, удаления) и передает их в другие системы. Часто реализуется путем мониторинга журнала упреждающей записи (write-ahead log) базы данных.

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

Хорошее решение: Предварительные вычисления и кэширование

Подход

Другой подход - асинхронно предвычислять (pre‑compute) и кешировать списки потенциальных матчей. Периодические фоновые cron задания формируют списки по предпочтениям и локации и кладут их в кэш, чтобы при открытии приложения выдавать мгновенно - без вычислений.

Такой кэшированный список дает пользователю моментальный доступ к профилям, улучшая UX. Предвычисления можно делать в “непиковое” время, а сокращение частоты запуска cron задания помогут держать списки потенциальных матчей актуальными.

Предварительные вычисления и кэширование

Проблемы

Очень активные пользователи быстро “съедят” кэшированные списки, и затем придется подгружать/генерировать новые списки - это медленно и неэффективно.

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

Отличное решение: Комбинация предвычислений и индексированной БД

Подход

Хорошая новость в том, что мы можем получить лучшее из обоих решений, объединив преимущества как предварительных вычислений, так и запросов в реальном времени с использованием индексированной базы данных. Мы периодически предварительно вычисляем и кэшируем списки потенциальных матчей для пользователей на основе их предпочтений и местоположения.

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

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

Комбинация: предварительные вычисления + индексированная база данных

Как мы можем решить проблему устаревших списков?

Кэширование списков пользователей может привести к тому, что мы будем предлагать “устаревшие” профили:

пользователь, предложенный в списке, возможно, изменил местоположение и больше не находится достаточно близко, чтобы соответствовать критериям фильтра
пользователь, предложенный в ленте, может изменить свой профиль (например, интересы) и больше не соответствует критериям фильтра

Чтобы смягчить эту проблему, можно:

поставить строгий TTL на кэш списков (например, < 1 часа) и пересчитывать по расписанию
предвычислять списки только для действительно активных пользователей, а не для всех

Преимущество заключается в том, что можно тюнить несколько параметров: TTL для кэшированных профилей, количество кэшированных профилей, набор пользователей, для которых мы кэшируем списки, и т. д.

Когда система имеет параметры, которые можно тюнить без изменения логики, это упрощает эксплуатацию. Параметры можно изменить, чтобы найти эффективную конфигурацию для масштаба/варианта использования системы, и корректировать ее с течением времени без необходимости изменения системы.

Также есть вполне определенные пользовательские действия, которые делают кэш устаревшим:

пользователь поменял фильтры - профили в кэше больше не релевантны
пользователь значительно изменил местоположение (например, переехал в другой район/город) - кэш больше не соответствует фильтру “поблизости”

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

3. Как избежать повторного показа профилей, по которым пользователь уже свайпал?

Было бы довольно неприятно, если бы пользователям повторно показывали профили, которые они пролистнули. У пользователя может сложиться впечатление, что его свайпы вправо (“да”) не были записаны, или это может раздражать пользователей, когда они снова видят людей, которых они раннее свайпнули влево (“нет”). Мы должны разработать решение, которое исключит этот неприятный пользовательский опыт.

Плохое решение: Запрос в хранилище свайпов

Подход

Сервис построения списка может запросить хранилище свайпов и сделать проверку на наличие свайпов пользователя, чтобы отфильтровать профили, по которым уже свайпали. Запрос “все свайпы пользователя” будет эффективным, потому что попадет в один раздел по swiping_user_id.

Проблемы

С этим подходом есть две проблемы:

Если система предпочитает доступность над согласованностью, часть свайпов могла не попасть на все реплики - мы рискуем “пропустить” свайпы и повторно показать профиль.
Если у пользователя огромная история свайпов, вернется много id, и проверка на наличие свайпов становится все более дорогой.

Отличное решение: Кэш + запрос в хранилище свайпов

Подход

Развивая предыдущий подход, можно добавить кэш последних свайпов, чтобы уменьшить проблемы ориентированной на доступность системы. Однако, этот кэш мы можем хранить не на бэкенде, а на клиенте.

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

Этот клиентский кэш особенно полезен, когда пользователь быстро исчерпывает предвычисленный список. Представьте, что пользователь свайпает 200 заранее подгруженных профилей. Примерно на ~150 профиле клиент может:

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

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

Проблемы

Остается проблема пользователей с очень большой историей свайпов: проверка на contains по большому множеству id будет все медленнее по мере роста истории.

Отличное решение: Кэш + запрос в хранилище свайпов + фильтр Блума

Подход

Этот подход может выглядеть слегка “over-engineered”, но это вполне разумный сценарий для фильтра Блума: поддержать построение списка для пользователей с огромной историей свайпов.

Если история свайпов превышает определенный порог (когда проверка на contains становится дорогой), мы строим и кэшируем фильтр Блума и используем его для фильтрации.

Фильтр Блума иногда дает ложноположительные результаты (false positives) (например, что профиль уже свайпали, хотя это не так), но никогда не дает ложноотрицательные (false negatives) (например, что профиль не свайпали, если его свайпали). Значит мы точно избегаем повторных показов, но можем не показать пользователю небольшое количество профилей из-за ложноположительных результатов.

Фильтр Блума обычно имеет настраиваемый процент ошибки, связанный с размером фильтра (сколько памяти он занимает), так что можно подобрать компромисс между числом ложноположительных результатов, потреблением памяти и скоростью фильтрации.

Кэш + запрос в хранилище свайпов + фильтр Блума

Проблемы

Основная сложность - управление кэшем фильтров Блума: их нужно обновлять и восстанавливать при отказах. Фильтр Блума легко пересобрать из данных свайпов, но на больших объемах данных пересборка при падении узла может быть дорогостоящей операцией.

Что ожидается на каждом уровне?

Хорошо, мы обсудили много всего. Возникает резонный вопрос: “сколько из этого реально ожидается от меня на интервью?”. Разберем по уровням.

Middle

Ширина vs глубина: от Middle кандидата чаще ожидается ширина кругозора и знаний (примерно 80% vs 20%). Вы должны собрать понятный высокоуровневый дизайн, закрывающий все функциональные требования, но многие компоненты могут оставаться абстракциями, которые вы проработали и обсудили с интервьюером на поверхностном уровне.

Проверка базовых знаний: интервьюер будет прощупывать базу, чтобы удостовериться, что вы понимаете, что делает каждый компонент. Например, добавив API Gateway, ожидайте вопрос “что он делает” и “как работает”.

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

Задача Tinder: от Middle кандидата ожидается четко определенный API и модель данных, а также высокоуровневый дизайн, который функционально покрывает показ списка потенциальных матчей и обработку свайпов. Не обязательно знать глубокие детали конкретных технологий, но ожидается дизайн, поддерживающий и обычные фильтры, и фильтры по геолокации. Также ожидается решение, которое не показывает повторно просмотренные профили.

Senior

Глубина экспертизы: от Senior кандидата ожидания смещаются к глубине - примерно 60% ширины и 40% глубины. Нужно уметь уходить в детали там, где у вас есть практический опыт.

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

Аргументация решений: вы должны уметь ясно объяснять плюсы/минусы архитектурных решений и их влияние на масштабирование, производительность и поддерживаемость, проговаривая компромиссы.

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

Задача Tinder: от Senior кандидата ожидается, что вы быстро пройдете высокоуровневый дизайн и потратите время на детальное обсуждение масштабируемой генерации списка потенциальных матчей и корректного создания матчей. Ожидается, что вы будете проактивно проговаривать компромиссы для построения списка потенциальных матчей, иметь представление о типе индексов которые помогут делать это эффективно, и помнить, когда кэш списка потенциальных матчей становится устаревшим.

Staff+

Акцент на глубину: от Staff+ кандидата ожидается глубокий разбор нюансов - примерно 40% ширины и 60% глубины. Важна демонстрация того, что, даже если вы не решали именно эту задачу раньше, вы решали достаточно похожих задач в реальном мире, чтобы уверенно спроектировать решение, опираясь на опыт.

Интервьюер понимает, что вы знаете основы (REST, нормализация данных и т. п.), так что вы можете быстро пройти это на high-level дизайне и перейти к самому интересному.

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

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

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

Задача Tinder: от Staff+ кандидата ожидается высокое качество решений по сложным задачам, которые обсуждались выше. Сильные кандидаты глубоко разбирают каждую тему, от них также ожидается четкое понимание компромиссов между различными решениями и способность ясно их сформулировать.

Разборы задач по System Design:

Проектируем Ticketmaster, сервис бронирования билетов

Проектируем Uber, сервис для заказа такси

System Design: проектируем сервис быстрых знакомств