Comments 23
Совсем недавно на хабре была очень хорошая статья на аналогичную тему
https://habr.com/ru/articles/746602/
Как ваша схема отличается от представленной в оригинале?
Если у вас есть N серверов для хостинга API, то они образуют кластер (Cluster) и возникает необходимости в балансировщике нагрузки (Coordinator), а также инстансы (Workers) - ровно как и в оригинальном решении. Рискну предположить, что API Gateway в оригинале предназначен для вывода сервиса из интранета в интернет, что вам так же так или иначе необходимо было решить. LCU в вашей архитектуре похож на in-memory кэш инстанса. Это означает, что каждый инстанс будет иметь свой собственный кэш, что может быть неэффективно как на чтение, так и на запись, особенно в случае необходимости его инвалидации (например функция "удаление ссылки" или "истечения срока ссылки"). В оригинале под кэшем подразумевается инстанс Redis, используемый в качестве распределенного кэша и для обеспечения отказоустойчивости (хотя конкретно это вызывает некоторые сомнения).
Обработку батчем мы опустим. В оригинале к ней есть вопросы.
Что касается проверки занятости короткой ссылки, то в оригинальной статье она реализована некорректно, а в вашем примере вообще отсутствует. Необходимо использовать оптимистичную конкуренцию в DynamoDB — добавлять запись только в том случае, если ключ отсутствует в базе используя ConditionExpression. Если ключ уже занят, следует использовать в качестве ключа хэш от модифицированной ссылки, но это отдельная тема.
Возвращаясь к сути вопроса: в чем принципиальная разница между вашим решением и решением, представленным в оригинальной статье?
P.S. Не заметил, что это перевод.
Эффективность локального инмемори кеша обеспечивается локальностью запросов. Иногда это называют прилипанием. Это типовая фича всех нормальных балансеров.
hash(url1) ->server1
hash(url2) ->server2
Ответ из мапы в памяти настолько быстр, что неравномерности нагрузки можно не бояться.
Инвалидацию обычно делают просто через ТТЛ записей в локальном кеше. Все работает само. Даже код писать не нужно обычно.
Если протекло что-то не то и локальный кеш срочно сбросить надо - рестарт поможет. Но что там такого может протечь непонятно.
Такой вариант возможен, но не отказоустойчив.
url1 кешируетя на Server 1; Server 1 теряет выход в сеть; мы не хотим, чтобы половина пользователей отваливалась, когда у нас отваливается одна нода, балансер по хэш ринг перекидывает запросы на Server 2; url1 попадает в кеш Server 2; пользователь удаляет/отключает/перенаправляет короткую ссылку через Server 2; Server 1 восстанавливает соединение; балансер с высокой вроятностью снова может направлять запросы url1 на Server 1. Кеш url1 уже невалиден в Server 1.
Получаем неконсистентность, которую может быть сложно отловить.
Возможные решения:
позволяем серверу отвалиться и перестаем обслуживать клиентов по данному сегменту хэшей - понижает доступность = потеря денег;
выносим кеш в отдельный кластер и получаем возможность игнорировать его в случае недоступности и идти напрямую в базу - повышает косты;
делаем время жизни инмемори кеша достаточно небольшим, например, 30 секунд, чтобы даже если такое произойдет система быстро самовосстановилась - просто, с высокой вероятностью решает 99.99 кейсов, немного повышает косты;
предусмотреть мануальный ресет кеша на ноде или просто сделать ребут ноды- просто, решает 99,99%, не повышает косты, добавляет человеческий фактор или необходимость настаивать триггер по алерту;
подлючить DynamoDB DAX - косты сопоставимы с кластером кеша, но нет трат на обслуживание, соответственно косты с учетом ФОТ могут быть ниже.
Типичный сокращаешь не позволяет редактировать ссылки.
Типичней некуда: https://helpdesk.tinyurl.com/faqs/how-to-edit-your-tinyurl-links
Если нет необходимости в редактировании, то, на первый взгляд, решение с локальным кешом выглядит рабочим.
В этом случае получается, что вам места под кэш нужно кратно количеству инстансов приложухи, что немного расточительно по памяти, плюс это создает дополнительную нагрузку на базу, потому что каждый инстанс приложухи будет лазить в базу, чтобы закэшировать данные у себя.
Локальность же. Данные в кешах будут пресекаться но слабо. На практике 95+ процентов данных уникальными получаются и лишнего расхода памяти нет.
Тогда я не понял :-)
Получается что перед всеми серваками должен стоять еще и балансировщик, который будет считать хэши и отправлять на разные сервера.
Конечно. Балансировщик в любом случае нужен любому хайлоаду.
Он нужен только в случае, если там у вас несколько инстансов за ним :-)
Я про то, что у вас тогда часть логики переносится на балансировщик и здесь у вас уже L7 балансировка, а не просто разбрасывание раунд-робином. И это даже не совсем sticky-sessions, потому что у вас сервер зависит не от пользователя, а от урла, с которым обратились.
Самый смак будет - когда удастся реализовать вообще без хранилища БД. По сути это некий алгоритм сжатия и распаковки, когда в самом коротком урл будет содержаться все что надо. Как пример - азбука Морзе.
Не очень понял что вы имеете в виду. По вашему описанию получится удлинитель ссылок.
Азбука Морзе занимает раза в три больше места, чем исходная информация. А также не представляет из себя ничего без алфавита.
Сжатие конечно применимо, но на небольших объемах данных и с высокой энтропией, как у ссылок по одиночке, оно будет неэффективным. Скорее всего займет столько же места, либо совсем немного меньше. Однако сжатые данные обычно являются байтами, а значит их придётся каким-то образом закодировать. Например, используя base64. И тогда получится, что хранить длинную ссылку выгоднее, чем её сжатую и закодированную версию.
Я имел ввиду какие либо принципиально новые алгоритмы или подходы, может быть даже новое железо, типа квантовых компьютеров.
Азбука Морзе не может увеличивать в три раза. Там все буквы кодируются точкой тире (это по сути бит). Каждая буква от 1 до 4 или 5 «битов». Код символа ASCII - 1 байт или 8 бит. То есть сокращается на 50% и больше. Но в азбуке Морзе есть аналоговые паузы, которые сообщают о начале буквы. Возможно, если это подружить с нейросеткой - она научится выдергивать правильные буквы из непрерывного потока 0 и 1.
У урл ссылок тоже есть алфавит - это буквы англ алфавита и спецсимволы. Всего порядка 50-60 штук, лень точно считать.
Если даже взять 64 штуки то их можно закодировать 6 битами а не 8. Это уже сокращение на 25%. Разумеется это не совсем то, что требуется по условию задачи.
занимаясь архивированием вы только что променяли нагрузку по памяти, на нагрузку по процессору :-)
То что вы предлагаете - это применить алгоритмы сжатия без потерь. Изобрести здесь что-то принципиально новое невозможно. В лучшем случае можно увеличить сжатие на 5% в каких-то случаях - и это будет тянуть уже на великое научное достижение. Никакие квантовые вычисления тут не применимы, они про другое. Дальше. Да, текст хорошо сжимается, "хорошо" именно за счёт маленького словаря используемого в текстах. НО. Вам же нужно будет уменьшенный результат (в байтах, допустим на 30-50%) снова в маленький текстовый словарь допустимых в URL символов запихать, соответственно снова раздуть на ту же величину. И алгоритмы сжатия основаны на кодировании повторений, эффект будет на больших текстах, а тут только сжатие из-за словаря. В сухом остатке типичная ссылка в 100 символов после сжатия и повторного кодирования УВЕЛИЧИТСЯ в размерах, с учётом домена самого сервиса, это 100%.
Там все буквы кодируются точкой тире (это по сути бит)
Если немного подумать, то буквы в азбуке Морзе кодируются точкой, тире и пробелом. Без пробела между буквами, вы не сможете узнать границы букв: три точки - это "С", или "ЕЕЕ", или "ЕИ", или "ИЕ"? Соответственно, тут троичная система счисления. Причём, возможно, выбрана не самая оптимальная стратегия кодирования букв, но так уж исторически сложилось
Не нужно оверинжинирить сокращатель ссылок