Глава 8. Проблемы распределённых систем

Повторяющейся темой нескольких последних глав была обработка нештатных ситуаций системой. Например, мы обсуждали переключение реплик («Обработка выходов узлов»), задержку репликации («Проблемы с задержкой репликации») и контроль параллелизма для транзакций (Глава 7). Постепенно изучая различные критические ситуации, которые могут возникнуть в реальных системах, мы начинаем лучше с ними справляться.

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

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

В конечном итоге задачей для нас в качестве инженеров является создание систем, которые выполняют свою работу (т.е. соответствуют ожиданиям пользователей), несмотря на всё, что может пойти не так. В Главе 9 мы рассмотрим примеры алгоритмов, способных оправдать эти ожидания в распределённой системе. Но сначала в этой главе мы должны понять, с какими проблемами мы сталкиваемся.

Эта глава представляет собой тщательный пессимистический обзор того, что может пойти не так в распределённой системе. Мы рассмотрим проблемы с сетями («Ненадёжные сети»); часы и проблемы времени («Ненадёжные часы») и обсудим, насколько они неизбежны. Последствия всех этих проблем приводят к дезориентации, поэтому мы узнаем, как оценить состояние распределённой системы и как делать выводы из того, что произошло («Знание, истина и ложь»).

При написании программы на одном компьютере она обычно ведёт себя достаточно предсказуемо: либо она работает, либо нет. Проблемы в программном обеспечении могут создать впечатление, что у компьютера иногда «плохое настроение» (его часто устраняют перезагрузкой), но это в основном является следствием плохо написанного программного обеспечения.

Нет фундаментальной причины для того, чтобы программное обеспечение на одном компьютере было нестабильным: при правильной работе аппаратного обеспечения одна и та же операция всегда дает одинаковый результат (она детерминирована). Если есть проблема с аппаратным обеспечением (например, повреждение памяти или ненадёжное соединение), то обычно возникает полный сбой системы (например, kernel panic, «синий экран смерти», невозможность запуска). Индивидуальный компьютер с хорошим программным обеспечением обычно либо полностью функционален, либо полностью сломан, промежуточного состояния нет.

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

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

Некоторые части распределённой системы могут быть непредсказуемым образом сломаны, даже если другие части работают нормально. Это называется частичный сбой. Трудность заключается в том, что частичные сбои являются недетерминированными: если вы пытаетесь выполнить что-то, включающее несколько узлов и сеть, иногда это может сработать, а иногда вызывать непредсказуемый сбой. Как видите, вы можете даже не узнать, успешно ли что-то прошло, так как время, требуемое для передачи сообщения по сети, также не детерминировано!

Эта недетерминированность и возможность частичных сбоев усложняют работу с распределёнными системами.

Существует несколько философий построения вычислительных систем большого масштаба:

• На одном конце шкалы находится область высокопроизводительных вычислений (HPC — high-performance computing). Суперкомпьютеры с тысячами процессоров обычно используются для вычислительно-интенсивных задач научного характера, таких как прогнозирование погоды или молекулярная динамика (моделирование движения атомов и молекул).
• На другом конце находятся облачные вычисления (cloud computing), которые не очень хорошо описаны, но часто ассоциируются с многопользовательскими центрами обработки данных, компьютерами общего назначения, соединенными сетью IP (часто Ethernet), с выделением ресурсов гибко или по требованию, а также измеренной тарификацией.
• Традиционные корпоративные центры обработки данных находятся где-то посередине.

С этими философиями связаны крайне разные подходы к обработке сбоев. На суперкомпьютере служба обычно время от времени сохраняет состояние своей работы в надежное хранилище. Если один узел выходит из строя, стандартным решением является просто остановка всей рабочей нагрузки кластера. После восстановления неисправного узла вычисление снова запускается с последней точки сохранения. Таким образом, суперкомпьютер больше похож на компьютер с одним узлом, чем на распределённую систему: он справляется с частичным сбоем, позволяя ему эскалировать в полный сбой — если часть системы выходит из строя, то пусть выходит из строя всё (как сбой ядра на одном компьютере).

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

• Многие интернет-приложения работают онлайн, это значит, что им нужно быть в состоянии обслуживания пользователей с низкой задержкой в любое время. Недоступность услуги — например, остановка кластера для ремонта — недопустима. В отличие от этого офлайн (пакетные) службы, такие как симуляции погоды, могут быть остановлены и перезапущены почти без последствий.
• Суперкомпьютеры обычно строятся на специализированном оборудовании, где каждый узел вполне надёжен и узлы общаются через общую память и удалённый прямой доступ к памяти (RDMA - remote direct memory access). С другой стороны, узлы в облачных службах созданы из компьютеров общего назначения, которые могут предоставлять эквивалентную производительность при более низкой стоимости благодаря экономии масштаба, но также имеют более высокие уровни отказов.
• Большие сети центров обработки данных часто основаны на протоколах IP и Ethernet, устроенных по топологиям Клосса, для обеспечения высокой полосы пропускания поперечного сечения. Суперкомпьютеры часто используют специализированные топологии сетей, такие как многомерные сети и торы, обеспечивающие более высокую производительность для вычислительных задач с известными шаблонами обмена данными.
• Чем больше становится система, тем больше становится вероятность, что один из ее компонентов сломан. С течением времени сломанные части чинятся и происходят новые поломки, а в системе с тысячами узлов что-то всегда может быть сломано. Когда стратегия обработки ошибок состоит в том, чтобы просто сдаться, большой системе может понадобиться потратить много времени на восстановление после сбоев, вместо того чтобы выполнять полезную работу.
• Если система может выдержать отказ узлов и продолжать работать в целом, это очень полезно для операций и обслуживания: например, вы можете провести поэтапное обновление (см. Главу 4), перезапуская один узел за другим, в то время как служба продолжает обслуживать пользователей без прерывания. В облачных средах, если одна виртуальная машина работает неудовлетворительно, вы можете просто её уничтожить и запросить новую (в надежде, что новая будет быстрее).
• В распределённых системах, особенно в географически распределённых развёртываниях (где данные хранятся близко к пользователям для снижения задержки доступа), связь, скорее всего, происходит через интернет, который медленнее и менее надёжен по сравнению с локальными сетями. В то время как суперкомпьютеры, как правило, предполагают, что все их узлы находятся близко друг к другу.

Чтобы заставить распределённые системы работать, мы должны принять возможность частичных сбоев и встроить в программное обеспечение механизмы обеспечения отказоустойчивости. Другими словами, нам нужно создавать надёжные системы из ненадёжных компонентов. (Как обсуждалось в главе 1, не существует идеальной надёжности, поэтому нам нужно понимать пределы того, что мы можем реалистично обещать.)

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

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

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

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

Интернет и большинство внутренних сетей в центрах обработки данных (часто Ethernet) являются асинхронными пакетными сетями (asynchronous packet networks). В таком виде сети один узел может отправить сообщение (пакет) другому узлу, но сеть не предоставляет никаких гарантий относительно времени его доставки или того, дойдёт ли он вообще. Если вы отправляете запрос и ожидаете ответа, многое может пойти не так (некоторые примеры изображены на Рисунке 8-1):

1. Ваш запрос мог быть потерян (возможно, кто-то выдернул сетевой кабель).
2. Ваш запрос может ожидать в очереди и будет доставлен позже (возможно, сеть или получатель перегружены).
3. Удалённый узел может выйти из строя (возможно, он аварийно завершился или выключен).
4. Удалённый узел может временно прекратить отвечать (возможно, происходит длительная пауза сборки мусора; см. «Паузы Процесса»), но он начнет снова отвечать позже.
5. Удалённый узел может обработать ваш запрос, но ответ потерян в сети (возможно, сетевой коммутатор настроен неправильно).
6. Удалённый узел может обработать ваш запрос, но ответ задерживается и будет доставлен позже (возможно, сеть или ваша собственная машина перегружены).

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

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

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

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

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

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

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

Работа с сетевыми сбоями не обязательно означает толерантность к ним: если ваша сеть обычно достаточно надёжна, разумным подходом может быть просто показать сообщение об ошибке пользователям во время проблем с сетью. Однако вам необходимо знать, как ваше программное обеспечение реагирует на сетевые проблемы и обеспечивать возможность системе восстановиться от них. Может быть полезен намеренный вызов проблем с сетью и тест реакции системы. (в этом смысле стоит упомянуть Chaos Monkey; см. Главу 1).

Многие системы должны автоматически обнаруживать неисправные узлы. Например:

• Балансировщик нагрузки должен перестать отправлять запросы узлу, который отключён (то есть исключить его из оборота).
• В распределённой базе данных с репликацией с одним лидером, если лидер выходит из строя, одного из последователей нужно повысить до нового лидера (см. «Обработка отказов узлов»).

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

• Если вы можете подключиться к машине, на которой должен работать узел, но ни один процесс не прослушивает порт назначения (например, потому что процесс вышел из строя), операционная система дружелюбно закроет или откажет в TCP-соединениях, отправив RST или FIN-пакет в ответ. Однако, если узел вышел из строя во время обработки вашего запроса, у вас нет способа узнать, сколько данных фактически обработал удалённый узел.
• Если процесс узла вышел из строя (или был завершён администратором), но операционная система узла по-прежнему работает, сценарий может уведомить другие узлы об аварии, чтобы другой узел мог быстро его заменить, не дожидаясь истечения тайм-аута. Например, так делает HBase.
• Если у вас есть доступ к управляющему интерфейсу сетевых коммутаторов в вашем центре обработке данных, вы можете послеть к ним запросы, чтобы обнаружить отказы связи на аппаратном уровне (например, если удалённая машина отключена). Этот вариант исключается, если вы подключаетесь через интернет или если вы находитесь в общем центре обработке данных без доступа к самим коммутаторам или если вы не можете подключиться к управляющему интерфейсу из-за проблем с сетью.
• Если маршрутизатор уверен, что IP-адрес, по которому вы пытаетесь подключиться, недоступен, он может ответить вам пакетом ICMP Destination Unreachable. Однако и у маршрутизатора нет магической возможности обнаруживать сбои — он подчинён тем же ограничениям, что и другие участники сети.

Быстрая обратная связь о том, что удалённый узел недоступен, полезна, но на нее нельзя полагаться. Даже если TCP подтверждает, что пакет был доставлен, приложение может выйти из строя перед его обработкой. Если вы хотите быть уверены, что запрос был успешен, вам нужен положительный ответ от самого приложения.

Наоборот, если что-то пошло не так, вы можете получить ответ с ошибкой на каком-то уровне стека, но в общем случае приходится предполагать, что вы не получите ответа вообще. Вы можете повторить попытку несколько раз (TCP повторяет автоматически, но вы также можете повторить на уровне приложения), подождать истечения тайм-аута и в конечном итоге объявить узел мёртвым, если вы не получите ответ в течение тайм-аута.

Если тайм-аут это единственный надёжный способ обнаружения сбоя, то каким долгим он должен быть? К сожалению, простого ответа нет.

Долгий тайм-аут означает долгое ожидание, пока узел не будет объявлен мёртвым (и в течение этого времени пользователи могут быть вынуждены ждать или видеть сообщения об ошибке). Короткий тайм-аут обнаруживает сбои быстрее, но несёт больший риск ложного объявления узла мёртвым, когда на самом деле он просто замедлился временно (например, из-за всплеска нагрузки на узел или сеть).

Преждевременное объявление узла мёртвым проблематично: если узел действительно жив и находится в процессе выполнения некоторого действия (например, отправки электронной почты) и другой узел его перехватывает, действие может быть выполнено дважды. Мы рассмотрим этот вопрос более подробно в разделе «Знание, истина и ложь», а также в главах 9 и 11.

Когда узел объявляется мёртвым, его обязанности должны быть переданы другим узлам, что создаёт дополнительную нагрузку на другие узлы и сеть. Если система уже испытывает высокую нагрузку, преждевременное объявление узлов мёртвыми может ухудшить проблему. В частности, может произойти так, что узел на самом деле не был мёртв, а только медленно реагировал из-за перегрузки; передача его нагрузки другим узлам может вызвать каскадный сбой (в крайнем случае все узлы объявляют друг друга мёртвыми и всё перестает работать).

Представьте вымышленную систему с сетью, которая гарантирует максимальную задержку для пакетов — каждый пакет либо доставляется в течение некоторого времени d, либо потерян, но время доставки никогда не превышает d. Кроме того, предположим, что вы можете гарантировать, что не отказавший узел всегда обрабатывает запрос в течение некоторого времени r. В этом случае вы могли бы гарантировать, что каждый успешный запрос получает ответ в течение времени 2d + r — и если вы не получаете ответа в течение этого времени, вы знаете, что либо сеть, либо удалённый узел не работают. Если бы это было так, использование тайм-аута 2d + r было бы разумным.

К сожалению, большинство систем, с которыми мы работаем, не обладают ни одной из этих гарантий: асинхронные сети имеют неограниченные задержки (то есть они стараются доставлять пакеты как можно быстрее, но нет верхнего предела времени, которое может потребоваться для доставки пакета) и большинство реализаций серверов не могут гарантировать, что они могут обработать запросы в некоторое максимальное время (см. «Гарантии времени ответа»). Для обнаружения сбоев недостаточно, чтобы система была быстрой большую часть времени: если ваш тайм-аут низок, достаточно одного кратковременного всплеска во времени от отправки до получения ответа, чтобы вывести систему из равновесия.

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

• Если несколько различных узлов одновременно пытаются отправить пакеты ​​на один и тот же пункт назначения, коммутатор сети должен поставить их в очередь и поочередно направлять их по сетевому соединению назначения (как показано на Рисунке 8-2). На загруженном сетевом соединении пакету может потребоваться некоторое время, прежде чем он сможет занять свое место (это называется сетевой конгестией (network congestion)). Если поступающих данных так много, что очередь коммутатора заполняется, пакет удаляется и его необходимо повторно отправить — несмотря на то, что сеть функционирует нормально.
• Когда пакет достигает машины-назначения, если все ядра центрального процессора в данный момент заняты, входящий запрос из сети помещается в очередь операционной системой до тех пор, пока приложение не будет готово его обработать. В зависимости от загрузки машины это может занять произвольное время.
• В виртуализированных средах работающая операционная система часто приостанавливается на десятки миллисекунд, пока другая виртуальная машина использует ядро процессора. В это время ВМ не может потреблять данные из сети, поэтому входящие данные буферизуются монитором виртуальной машины, что ещё более увеличивает изменчивость сетевых задержек.
• TCP выполняет управление потоком (также известное как избегание перегрузки (congestion avoidance) или обратное давление (backpressure)), при котором узел ограничивает собственную скорость отправки для избежания перегрузки сетевого соединения или узла-получателя. Это означает дополнительную очередь на отправителе ещё до того, как данные войдут в сеть.

Более того, TCP считает пакет потерянным, если он не подтверждается в течение некоторого тайм-аута (который рассчитывается из наблюдаемого времени маршрута) и потерянные пакеты автоматически пересылаются. Хотя приложение не видит потерю пакета и повторную передачу, оно видит вызванную этим задержку (ожидание истечения тайм-аута, а затем ожидание подтверждения повторно отправленного пакета).

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

В облачных сервисах и центрах обработки данных с большим количеством клиентов ресурсы используются многими клиентами: сетевые каналы и коммутаторы, а также сетевые интерфейсы и процессоры каждой машины (при выполнении на виртуальных машинах) являются общими. Пакетные рабочие нагрузки, такие как MapReduce (см. Главу 10), легко могут насытить сетевые каналы. Поскольку у вас нет контроля или представления о том, как другие клиенты используют общие ресурсы, сетевые задержки могут быть чрезвычайно переменными, если кто-то рядом с вами (шумный сосед) использует много ресурсов.

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

Еще лучше, чем использование настроенных постоянных тайм-аутов, — непрерывное измерение времени ответов и их изменчивости (дрожание (jitter)) системой и автоматическая корректировка тайм-аутов в соответствии с наблюдаемым распределением времени ответа. Это можно сделать с помощью детектора сбоев Phi Accrual, который используется, например, в Akka и Cassandra. Также работают тайм-ауты TCP для повторной передачи.

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

Чтобы ответить на этот вопрос, интересно сравнить сети центров обработки данных с традиционной телефонной сетью с фиксированными линиями (не сотовой, не VoIP), которая является чрезвычайно надёжной: задержки звука и обрывы вызовов очень редки. Для телефонного звонка требуется постоянно низкая задержка между конечными точками и достаточная полоса пропускания для передачи аудиосемплов вашего голоса. Было бы неплохо иметь аналогичную надёжность и предсказуемость в компьютерных сетях, правда?

Когда вы совершаете вызов через телефонную сеть, устанавливается цепь: фиксированное гарантированное количество полос пропускания выделяется для вызова по всему маршруту между двумя абонентами. Эта цепь остается на месте до завершения вызова. Например, сеть ISDN работает на фиксированной скорости 4000 кадров в секунду. При установке вызова ему выделяется 16 бит пространства в каждом кадре (в каждом направлении). Таким образом, на протяжении вызова каждой стороне гарантируется возможность отправлять ровно 16 бит аудиоданных каждые 250 микросекунд.

Такая сеть является синхронной: даже когда данные проходят через несколько маршрутизаторов, они не страдают от очередей, потому что 16 бит пространства для вызова уже были зарезервированы в следующем узле сети. И поскольку нет очередей, максимальная конечная задержка сети фиксирована. Мы называем это ограниченной задержкой (bounded delay).

Обратите внимание, что цепь в телефонной сети существенно отличается от соединения TCP: цепь — это фиксированное количество зарезервированной полосы пропускания, которую никто другой не может использовать во время установленной цепи, тогда как пакеты соединения TCP единолично используют всю доступную полосу пропускания сети. Вы можете передать TCP переменный блок данных (например, электронное письмо или веб-страницу) и он постарается передать его за кратчайшее время. Когда соединение TCP неактивно, оно не использует полосу пропускания.

Если бы сети центров обработки данных и интернета были коммутационными сетями, можно было бы установить гарантированное максимальное время маршрута при установке цепи. Однако они таковыми не являются: Ethernet и IP — это коммутационные протоколы, которые страдают от очередей и следовательно, от неограниченных задержек в сети. У этих протоколов нет концепции цепи.

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

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

Существовали попытки создать гибридные сети, поддерживающие как коммутацию цепи, так и коммутацию пакетов, такие как ATM. InfiniBand имеет некоторые сходства: он реализует контроль потока от конечной точки к конечной точке на уровне канала, что уменьшает необходимость в очередях в сети, хотя она все равно может страдать от задержек из-за перегрузки канала. С тщательным использованием качества обслуживания (QoS, приоритезация и планирование пакетов) и контроля допуска (ограничение скорости отправителей) можно эмулировать коммутацию цепи в сетях с коммутацией пакетов или обеспечивать статистически ограниченную задержку.

Однако такое качество обслуживания в настоящее время не наблюдается в многозадачных центрах обработки данных и облачных сервисах или при взаимодействии через Интернет. В настоящее время используемая технология не позволяет нам давать какие-либо гарантии относительно задержек или надёжности сети: мы должны предполагать, что возникнут перегрузки сети, очереди и неограниченные задержки. Следовательно, нет «правильного» значения для тайм-аутов — их нужно определять экспериментально.

Часы и время важны. Приложения зависят от часов в различных вопросах, таких, как:

1. Превысил ли этот запрос тайм-аут?
2. Каково время ответа на 99-й перцентиль этого сервиса?
3. Сколько запросов в секунду обрабатывал этот сервис в среднем за последние пять минут?
4. Как долго пользователь провёл на нашем сайте?
5. Когда была опубликована эта статья?
6. На какую дату и время должно быть отправлено напоминание по электронной почте?
7. Когда истекает срок действия этой записи в кэше?
8. Какова временная метка этого сообщения об ошибке в файле журнала?

Примеры с 1 по 4 измеряют длительности (например, временной интервал между отправкой запроса и получением ответа), тогда как примеры с 5 по 8 описывают моменты во времени (события, происходящие в определенную дату и время).

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

Более того, у каждой машины в сети есть свои часы, которые являются реальным аппаратным устройством: обычно кварцевый кристаллический осциллятор. Эти устройства не являются идеально точными, поэтому у каждой машины есть свое представление о времени, которое может быть немного быстрее или медленнее, чем на других машинах. Возможна некоторая синхронизация часов: наиболее часто используемым механизмом является протокол сетевого времени (NTP — Network Time Protocol), который позволяет корректировать время компьютерных часов в соответствии с временем, сообщаемым группой серверов. Серверы, в свою очередь, получают свое время от более точного источника времени, такого как GPS-приемник.

У современных компьютеров есть как минимум два различных типа часов: часы истинного времени (time-of-day clock) и монотонные часы (monotonic clock). Хотя оба они измеряют время, важно различать их, поскольку они служат разным целям.

Часы истинного времени выполняют то, что вы интуитивно ожидаете от часов: они возвращают текущую дату и время согласно некоторому календарю (также известному как календарное время). Например, функция clock_gettime(CLOCK_REALTIME) в Linux и метод System.currentTimeMillis() в Java возвращают количество секунд (или миллисекунд) с момента начала эпохи: полночь по UTC 1 января 1970 года, согласно григорианскому календарю, без учета високосных секунд. Некоторые системы используют другие даты в качестве своей точки отсчёта.

Часы истинного времени обычно синхронизируются с NTP, что означает, что метка времени с одной машины (в идеале) означает то же самое, что и метка времени на другой машине. Тем не менее часы истинного времени также имеют различные особенности, как описано в следующем разделе. В частности, если локальные часы слишком опережают NTP-сервер, их могут принудительно сбросить и они могут казаться перемещенными назад к предыдущему моменту во времени. Эти скачки, а также подобные скачки, вызванные високосными секундами, делают часы времени суток непригодными для измерения прошедшего времени.

Часы истинного времени также исторически имели довольно крупное разрешение, например, двигаясь с шагом 10 мс на более старых системах Windows. На современных системах это уже не проблема.

Монотонные часы подходят для измерения длительности (временного интервала), такого как тайм-аут или время ответа сервиса: функция clock_gettime(CLOCK_MONOTONIC) в Linux и метод System.nanoTime() в Java являются монотонными часами, например. Название происходит от того, что они гарантированно всегда двигаются вперёд (в то время как часы истинного времени могут перемещаться назад во времени).

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

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

NTP может регулировать частоту движения монотонных часов вперёд (это известно как коррекция часов), если он обнаруживает, что кварцевый осциллятор компьютера движется быстрее или медленнее, чем NTP-сервер. По умолчанию NTP позволяет увеличивать или уменьшать частоту часов на 0,05%, но NTP не может заставить монотонные часы перемещаться вперёд или назад. Разрешение монотонных часов обычно довольно хорошее: на большинстве систем они могут измерять временные интервалы в микросекундах или даже меньше.

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

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

• Кварцевые часы в компьютере не очень точны: они дрейфуют (идут быстрее или медленнее, чем должны). Дрейф зависит от температуры машины. Google предполагает дрейф часов в размере 200 ppm (parts per million — частей на миллион) для своих серверов, что эквивалентно дрейфу в 6 мс для часов, ресинхронизируемых с сервером каждые 30 секунд или 17 секунд для часов, ресинхронизируемых раз в день. Этот дрейф ограничивает лучшую возможную точность, которой можно достичь, даже если всё работает правильно.
• Если часы компьютера слишком сильно расходятся с NTP-сервером, они могут отказаться синхронизироваться или локальные часы могут быть принудительно сброшены. Любые приложения, следящие за временем до и после этого сброса, могут видеть, как время идёт назад или внезапно прыгает вперёд.
• Если узел случайно отсоединен от NTP-серверов фаерволлом, неправильная конфигурация некоторое время может оставаться незамеченной. Анекдотические данные предполагают, что такие ситуации случаются на практике.
• Синхронизация NTP может быть эквивалентна задержке в сети, поэтому есть предел её точности при использовании перегруженной сети с переменной задержкой пакетов. Одним экспериментом было показано, что минимальная ошибка 35 мс достижима при синхронизации через интернет, хотя случайные всплески задержки в сети приводят к ошибкам около секунды. В зависимости от конфигурации большие задержки в сети могут заставить клиент NTP сдаться полностью.
• Некоторые серверы NTP предоставляют неверное или неправильно сконфигурированное время, отличающееся на часы. Клиенты NTP довольно устойчивы, потому что опрашивают несколько серверов и игнорируют выбросы. Тем не менее, для правильности ваших систем  немного опасно полагаться на время, которое вам сообщил незнакомец в интернете.
• Скачущая секунда (leap second) приводит к минуте, которая длится 59 или 61 секунду, что нарушает предположения о времени в системах, не предназначенных для учёта скачущих секунд. Тот факт, что скачущие секунды привели к сбоям во многих крупных системах, показывает, насколько легко неправильные предположения о часах могут проникнуть в систему. Лучший способ обработки скачущих секунд может заключаться в том, чтобы сделать серверы NTP «врущими», постепенно корректируя скачущие секунды в течение дня (это известно как размазывание), хотя реальное поведение серверов NTP различно на практике.
• В виртуальных машинах аппаратные часы виртуализированы, что создает дополнительные проблемы для приложений, которым необходима точность ведения времени. Когда ядро CPU используется несколькими виртуальными машинами, каждая виртуальная машина приостанавливается на десятки миллисекунд, пока работает другая виртуальная машина. С точки зрения приложения эта пауза проявляется как внезапный скачок времени вперёд.
• Если вы запускаете программное обеспечение на устройствах, которые вы не полностью контролируете (например, мобильных или встраиваемых устройствах), вы, вероятно, не можете доверять аппаратным часам устройства вообще. Некоторые пользователи намеренно устанавливают свои аппаратные часы с неправильной датой и временем, например, чтобы обойти временные ограничения в играх. В результате часы могут быть установлены на время, значительно отличающееся от текущего.

Можно достичь очень высокой точности часов, если вы уделите этому достаточно внимания и ресурсов. Например, проект MiFID II европейского регулирования для финансовых учреждений требует, чтобы все фонды высокочастотного трейдинга синхронизировали свои часы с точностью до 100 микросекунд по UTC, чтобы помочь выявлять аномалии на рынке, такие как «вспышки» и обнаруживать манипуляции на рынке.

Такая точность может быть достигнута с использованием GPS-приемников, Протокола точного времени (PTP — Precision Time Protocol), а также тщательного развёртывания и мониторинга. Тем не менее это требует значительных усилий и экспертизы, и существует множество способов, как синхронизация часов может пойти не так.

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

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

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

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

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

На Рисунке 8-3 показано опасное использование часов истинного времени в базе данных с многолидерной репликацией (пример похож на Рисунок 5-9). Клиент A пишет x = 1 на узле 1; запись реплицируется на узел 3; клиент B увеличивает x на узле 3 (теперь у нас x = 2); и наконец, обе записи реплицируются на узел 2.

На Рисунке 8-3, когда запись реплицируется на другие узлы, ей присваивается метка времени согласно часам истинного времени на узле, где произошла запись. В этом примере синхронизация часов очень хороша: расхождение между узлом 1 и узлом 3 менее 3 мс, что, вероятно, лучше, чем вы можете ожидать на практике.

Тем не менее метки времени на Рисунке 8-3 не способны правильно упорядочить события: у записи x = 1 есть метка времени 42,004 секунды, но у записи x = 2 есть метка времени 42,003 секунды, хотя x = 2 произошла однозначно позже. Когда узел 2 получает эти два события, он неправильно заключит, что x = 1 - это более свежее значение и отбросит запись x = 2. По сути, операция увеличения клиента B будет потеряна.

Эта стратегия разрешения конфликтов называется «побеждает последняя запись» (LWW — last write wins) и она широко используется как в многолидерной репликации, так и в базах данных без лидера, таких как Cassandra и Riak (см. «Последняя запись побеждает (отбрасывание одновременных записей)»). Некоторые реализации генерируют временные метки на клиенте, а не на сервере, но это не меняет фундаментальных проблем с LWW:

• Записи в базе данных могут таинственным образом исчезнуть: узел с отстающим временем не может перезаписать значения, ранее записанные узлом с быстрыми часами, пока не пройдет разница во времени между узлами. Этот сценарий может привести к произвольному удалению данных без каких-либо сообщений об ошибке приложению.
• LWW не может различать между записями, произошедшими последовательно в быстром темпе (на Рисунке 8-3 увеличение клиента B однозначно происходит после записи клиента A) и записями, которые были действительно конкурирующими (никакой из писателей не знал о другом). Дополнительные механизмы отслеживания причинности, такие как векторы версий, необходимы для предотвращения нарушений причинности.
• Возможно, что два узла независимо генерируют записи с одинаковой меткой времени, особенно если часы имеют точность до миллисекунд. Дополнительное значение-разделитель (которое может быть просто большим случайным числом) требуется для разрешения таких конфликтов, но такой подход также может привести к нарушениям причинности.

Таким образом, даже если соблазнительно разрешать конфликты, сохраняя самое «последнее» значение и отбрасывая другие, важно понимать, что определение «последнего» зависит от часов местного времени суток, которые могут быть неточными. Даже с тщательной синхронизацией часов NTP вы можете отправить пакет с отметкой времени 100 мс (согласно часам отправителя) и получить его с отметкой времени 99 мс (согласно часам получателя) — таким образом, кажется, что пакет пришел до того, как был отправлен, что невозможно.

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

Так называемые «логические часы» (logical clocks), основанные на увеличивающихся счетчиках вместо колеблющегося кварцевого кристалла, представляют собой более безопасную альтернативу для упорядочивания событий (см. «Обнаружение одновременных записей»). Логические часы не измеряют время суток или количество прошедших секунд, а только относительный порядок событий (произошло ли одно событие до или после другого). В отличие от часов истинного времени и монотонных часов, которые измеряют фактическое прошедшее время, их также называют физическими часами. Мы ещё вернемся к упорядочиванию в Главе 9.

Возможно, вы можете считывать время суток компьютера с точностью до микросекунды или даже наносекунды. Но даже если у вас есть такое точное измерение, это не означает, что значение действительно точное с такой точностью. Фактически, скорее всего, это не так — как упоминалось ранее, дрейф в нечётких кварцевых часах может легко составлять несколько миллисекунд, даже если вы синхронизируетесь с сервером NTP в локальной сети каждую минуту. С использованием NTP-сервера в общедоступной сети Интернет, наилучшая возможная точность, вероятно, составляет десятки миллисекунд и ошибка может легко возрасти до более 100 мс при наличии сетевой загрузки.

Таким образом, бессмысленно рассматривать чтение времени как точку во времени — это скорее похоже на диапазон времени в пределах доверительного интервала: например, система может с уверенностью утверждать, что время сейчас находится между 10,3 и 10,5 секундами после минуты, но она не знает более точно, чем это. Если мы знаем только время +/- 100 мс, то микросекундные цифры в метке времени фактически бессмысленны.

Границу неопределённости можно рассчитать на основе вашего времени. Если у вас есть GPS-приемник или атомные (цезиевые) часы, прямо подключённые к вашему компьютеру, диапазон ожидаемой ошибки сообщается производителем. Если вы получаете время с сервера, неопределённость основана на ожидаемом дрейфе кварца с момента последней синхронизации с сервером, плюс неопределённость NTP-сервера, плюс время двойного обмена с сервером (приближенно и с предположением, что вы доверяете серверу).

К сожалению, большинство систем не учитывают эту неопределённость: например, когда вы вызываете clock_gettime(), возвращаемое значение не сообщает вам ожидаемой ошибки метки времени, и вы не знаете, является ли её доверительный интервал пять миллисекунд или пять лет.

Интересным исключением является TrueTime API от Google в Spanner, который явно сообщает о доверительном интервале на локальных часах. Когда вы запрашиваете текущее время, вы получаете два значения: [earliest, latest], которые представляют собой самую раннюю и самую позднюю возможную метку времени. Исходя из своих расчетов неопределённости, часы знают, что фактическое текущее время находится где-то в этом интервале. Ширина интервала зависит, среди прочего, от того, как давно локальные кварцевые часы были в последний раз синхронизированы с более точным источником времени.

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

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

Однако, когда база данных распределена по многим машинам, потенциально в нескольких центрах обработки данных, сложно создать глобальный, монотонно возрастающий идентификатор транзакции (по всем разделам), потому что это требует координации. Идентификатор транзакции должен отражать причинную связь: если транзакция B считывает значение, записанное транзакцией A, то у B должен быть более высокий идентификатор транзакции, чем у A — в противном случае снимок не будет согласованным. С большим количеством маленьких, быстрых транзакций создание идентификаторов транзакций в распределённой системе становится неразрешимым узким местом.

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

Spanner реализует изоляцию снимков между центрами обработки данных именно таким образом. Он использует интервал доверительности часов, как сообщается TrueTime API и основан на следующем наблюдении: если у вас есть два интервала доверительности, каждый состоящий из самой ранней и самой поздней возможной метки времени (A = [Aearliest, Alatest] и B = [Bearliest, Blatest]) и эти два интервала не пересекаются (т.е. Aearliest < Alatest < Bearliest < Blatest), то B определенно произошло после A — сомнений быть не может. Только если интервалы перекрываются, мы не уверены, в каком порядке произошли A и B.

Чтобы гарантировать, что метки времени транзакций отражают причинную связь, Spanner намеренно ожидает длину интервала доверительности перед подтверждением транзакции чтения-записи. Таким образом, он обеспечивает, что любая транзакция, которая может прочитать данные, находится в достаточно позднем времени, чтобы их интервалы доверительности не перекрывались. Для минимизации времени ожидания Spanner должен поддерживать неопределённость часов как можно меньше; для этого Google устанавливает GPS-приемник или атомные часы в каждом центре обработки данных, позволяя часам синхронизироваться с точностью около 7 мс.

Использование синхронизации часов для семантики распределённых транзакций — это предмет активных исследований. Эти идеи интересны, но они ещё не были реализованы в основных базах данных за пределами Google.

Рассмотрим ещё один пример опасного использования часов в распределённой системе. Допустим, у вас есть база данных с единственным лидером на каждый раздел. Только лидер может принимать записи. Как узнает узел, что он все ещё лидер (что его не объявили мёртвым другие узлы) и что он может безопасно принимать записи?

Один из вариантов — лидер получает аренду (lease) от других узлов, что похоже на блокировку с тайм-аутом. Только один узел может удерживать аренду в любой момент времени. Таким образом, когда узел получает аренду, он знает, что он лидер в течение некоторого времени, пока аренда не истекает. Чтобы остаться лидером, узел должен периодически обновлять аренду перед её истечением. Если узел сбоит, перестав обновлять аренду, другой узел может взять её, когда аренда истечёт.

Можно представить себе цикл обработки запросов, выглядящий примерно так:

Что не так с этим кодом? Во-первых, он полагается на синхронизированные часы: время истечения аренды устанавливается на другой машине (где срок может быть рассчитан, например, как текущее время плюс 30 секунд) и оно сравнивается с локальными часами системы. Если часы не синхронизированы более чем на несколько секунд, этот код начнет вести себя странно.

Во-вторых, даже если мы изменяем протокол, чтобы использовать только локальные монотонные часы, есть ещё одна проблема: код предполагает, что между моментом проверки времени (System.currentTimeMillis()) и временем обработки запроса (process(request)) проходит очень мало времени. Обычно этот код выполняется очень быстро, поэтому буфер в 10 секунд более чем достаточен, чтобы обеспечить, чтобы аренда не истекла посередине обработки запроса.

Однако что, если происходит неожиданная пауза в выполнении программы? Например, представьте себе, что поток останавливается на 15 секунд вокруг строки lease.isValid(), прежде чем, наконец, продолжить. В этом случае, скорее всего, аренда истечет к моменту обработки запроса и другой узел уже станет лидером. Однако нет ничего, что скажет этому потоку, что он был приостановлен настолько долго, поэтому этот код не заметит, что аренда истекла, пока не следующей итерации цикла — к тому времени, возможно, он уже сделал что-то небезопасное, обработав запрос.

Не кажется ли странным предположение о том, что поток может быть приостановлен на столь долгий срок? К сожалению, нет. Есть различные причины, по которым это может произойти:

• Многие среды выполнения языков программирования (такие как Java Virtual Machine) имеют сборщик мусора (GC — garbage collector), который иногда должен останавливать все выполняющиеся потоки. Эти паузы сборки мусора типа «stop-the-world» иногда могут длиться несколько минут! Даже так называемые «конкурирующие» сборщики мусора, такие как CMS в JVM HotSpot, не могут полностью работать параллельно с кодом приложения — они также иногда должны останавливать мир. Хотя паузы часто можно уменьшить, изменяя шаблоны выделения памяти или настраивая параметры GC, мы должны предполагать худшее, если хотим предоставить надёжные гарантии.
• В виртуализированных средах виртуальную машину можно приостановить (приостановив выполнение всех процессов и сохраняя содержимое памяти на диск) и возобновить (восстанавливая содержимое памяти и продолжая выполнение). Эта пауза может произойти в любой момент выполнения процесса и может продолжаться произвольное время. Эта функция иногда используется для живой миграции виртуальных машин с одного хоста на другой без перезагрузки, в этом случае длительность паузы зависит от того, как быстро процессы пишут в память.
• На конечных устройствах, таких как ноутбуки, выполнение также может быть приостановлено и возобновлено произвольным образом, например, когда пользователь закрывает крышку своего ноутбука.
• Когда операционная система переключается на другой поток или когда гипервизор переключается на другую виртуальную машину (при выполнении в виртуальной машине), текущий выполняющийся поток может быть приостановлен в любой произвольной точке кода. В случае виртуальной машины время CPU, проведенное в других виртуальных машинах, известно как «время кражи». Если машина находится под тяжёлой нагрузкой, например, если есть длинная очередь потоков, ожидающих выполнения, потребуется некоторое время, прежде чем приостановленный поток снова начнет выполняться.
• Если приложение выполняет синхронный доступ к диску, поток может быть приостановлен в ожидании завершения медленной операции ввода-вывода с диском. На многих языках доступ к диску может происходить удивительно, даже если код явно не упоминает доступ к файлу — например, загрузчик классов Java лениво загружает файлы классов, когда они впервые используются, что может произойти в любое время выполнения программы. Паузы ввода-вывода и паузы GC могут даже сговориться и объединить свои задержки. Если диск фактически является сетевым файловым хранилищем или сетевым блочным устройством (например, Amazon's EBS), то задержка ввода-вывода также подвержена изменчивости сетевых задержек.
• Если операционная система настроена на разрешение подкачки на диск (страничный обмен), простое обращение к памяти может вызвать отказ страницы, который требует загрузки страницы с диска в память. Поток приостанавливается на время выполнения этой медленной операции ввода-вывода. При высоком давлении на память это в свою очередь может потребовать подкачки другой страницы на диск. В экстремальных случаях операционная система может проводить большую часть своего времени обменом страницами в память и выполнять мало фактической работы (это известно как трэшинг). Чтобы избежать этой проблемы, подкачка часто отключена на серверных машинах (если вы предпочтете завершить процесс, чтобы освободить память, чем рисковать трэшингом).
• Процесс Unix может быть приостановлен путем отправки ему сигнала SIGSTOP, например, нажатием Ctrl-Z в оболочке. Этот сигнал мгновенно останавливает процесс, лишая его возможности получать больше циклов CPU, пока он не возобновится с помощью SIGCONT, после чего он продолжает выполнение с того места, где он остановился. Даже если ваша среда обычно не использует SIGSTOP, его могут отправить случайно инженеры по эксплуатации.

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

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

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

Некоторое программное обеспечение работает в средах, где несоблюдение установленного времени отклика может вызвать серьёзные повреждения: компьютеры, управляющие воздушными судами, ракетами, роботами, автомобилями и другими физическими объектами, должны быстро и предсказуемо реагировать на данные своих датчиков. В этих системах установлен конкретный срок, к которому программное обеспечение должно ответить; если срок не соблюдается, это может вызвать сбой всей системы. Эти системы называются системами жёсткого реального времени (hard real-time).

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

Обеспечение гарантий реального времени в системе требует поддержки на всех уровнях программного стека: необходима операционная система реального времени (RTOS — real-time operating system), позволяющая планировать процессы с гарантированным выделением процессорного времени в определённые интервалы; библиотечные функции должны документировать свое максимальное время выполнения; динамическое выделение памяти может быть ограничено или вовсе запрещено (существуют сборщики мусора реального времени, но приложение все равно должно гарантировать, что оно не поручает слишком много работы сборщику мусора); и необходимо провести огромное количество тестирования и измерений, чтобы убедиться, что гарантии соблюдаются.

Все это требует большого объёма дополнительной работы и сильно ограничивает выбор языков программирования, библиотек и инструментов (поскольку большинство языков и инструментов не предоставляют гарантий реального времени). Поэтому разработка систем реального времени очень дорогостояща и используется в основном во встраиваемых устройствах с повышенными требованиями к безопасности. Более того, «реальное время» не равно «высокая производительность» — на самом деле системы реального времени могут иметь более низкую пропускную способность, поскольку им приходится приоритезировать своевременные ответы выше всего (см. также «Задержка и использование ресурсов»).

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

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

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

Вариантом этой идеи является использование сборщика мусора только для быстро умирающих объектов (которые собираются быстро) и периодический перезапуск процессов до того, как они накопят достаточно долгоживущих объектов, требующих полной сборки мусора. Один узел может быть перезапущен за раз и трафик может быть отведён от узла перед запланированным перезапуском, как в случае пошагового обновления (см. Главу 4).

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

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

Последствия этих проблем могут быть глубоко дезориентирующими, если вы не привыкли к распределённым системам. Узел в сети не может ничего знать наверняка — он может только делать предположения на основе сообщений, которые он получает (или не получает) через сеть. Узел может узнать о состоянии другого узла (какие данные он сохраняет, функционирует ли он правильно и так далее) только обмениваясь с ним сообщениями. Если удалённый узел не отвечает, нет способа узнать, в каком он состоянии, потому что проблемы в сети невозможно точно отличить от проблем на узле.

Обсуждение этих систем касается философии: что мы знаем как истину или ложь в нашей системе? Насколько мы можем быть уверены в этом знании, если механизмы восприятия и измерения ненадёжны? Должны ли программные системы подчиняться законам, которые мы ожидаем от физического мира, таким как причинно-следственные связи?

К счастью, нам не нужно углубляться так же, как при поиске смысла жизни. В распределённой системе мы можем формулировать предположения о поведении (модель системы) и проектировать систему так, чтобы она соответствовала этим предположениям. Алгоритмы могут доказано правильно работать в определенной модели системы. Это означает, что надёжное поведение достижимо, даже если основная модель системы предоставляет очень мало гарантий.

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

Представьте сеть с асимметричным сбоем: узел способен получать все сообщения, отправленные ему, но любые исходящие сообщения из этого узла отбрасываются или задерживаются. Несмотря на то что узел работает идеально и получает запросы от других узлов, остальные узлы не могут слышать его ответов. По прошествии некоторого времени остальные узлы объявляют его мёртвым, потому что они не слышали ничего от узла. Ситуация разворачивается как кошмар: полунедоступный узел тащат на кладбище, а он вырывается и кричит «Я не мёртв!» — но поскольку никто не слышит его криков, процессия продолжает идти со стойким решением.

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

В третьем сценарии представьте узел, проходящий через длительную паузу сборки мусора stop-the-world. Все потоки узла приостанавливаются сборщиком мусора на одну минуту, следовательно, никакие запросы не обрабатываются, и никакие ответы не отправляются. Другие узлы ждут, повторяют запросы, теряют терпение и в конце концов, объявляют узел мёртвым и загружают его на катафалк. Наконец, сборка мусора завершается и потоки узла продолжают работу, как будто ничего не произошло. Другие узлы удивлены, когда предполагаемо мёртвый узел вдруг поднимается из гроба, полностью здоровый и начинает весело болтать с окружающими. Сначала узел, где проходила сборка мусора, даже не понимает, что прошла целая минута и что его объявили мёртвым — с его точки зрения прошло всего ничего времени с момента последнего разговора с другими узлами.

Мораль этих историй заключается в том, что узел не всегда может доверять своему собственному суждению о ситуации. Распределённая система не может полностью полагаться на один узел, потому что узел может выйти из строя в любое время, что потенциально приведёт к зависанию системы и невозможности восстановления. Вместо этого многие распределённые алгоритмы полагаются на кворум (quorum), то есть голосование среди узлов (см. «Кворумы для чтения и записи»): для принятия решений требуется определённое минимальное количество голосов от нескольких узлов для снижения зависимости от какого-то конкретного узла.

Это включает в себя решения о том, объявлять ли узлы мёртвыми. Если кворум узлов объявляет другой узел мёртвым, то его следует считать мёртвым, даже если этот узел все ещё чувствует себя живым. Индивидуальный узел должен подчиниться решению кворума и отступить.

Чаще всего кворум является абсолютным большинством более половины узлов (хотя возможны другие виды кворумов). Большинство кворума позволяет системе продолжать работу при отказах индивидуальных узлов (с тремя узлами можно пережить один сбой; с пятью узлами можно пережить два сбоя). Тем не менее это по-прежнему безопасно, потому что в системе может быть только одно большинство — не может быть двух большинств с конфликтующими решениями в одно и то же время. Мы обсудим использование кворумов более подробно, когда перейдём к алгоритмам консенсуса в главе 9.

Часто системе необходимо, чтобы существовал только один экземпляр чего-то. Например:

• Только один узел может быть лидером для раздела базы данных, чтобы избежать «расщеплённого мозга».
• Только одна транзакция или клиент может удерживать блокировку для конкретного ресурса или объекта, чтобы предотвратить одновременную запись и его повреждение.
• Только один пользователь может зарегистрировать определённое имя пользователя, потому что имя пользователя должно уникально идентифицировать пользователя.

Реализация этого в распределённой системе требует внимательности: даже если узел считает себя «избранным» (лидером раздела, владельцем блокировки, обработчиком запросов пользователя, который успешно захватил имя пользователя), это не обязательно значит, что кворум узлов согласен! Узел может ранее быть лидером, но если другие узлы в промежутке времени объявили его мёртвым (например, из-за разрыва сети или паузы сборки мусора), он может быть понижен в звании и другой лидер может уже быть избран.

Если узел продолжает действовать как «избранный», даже если большинство узлов объявили его мёртвым, это может вызвать проблемы в плохо спроектированной системе. Такой узел может отправлять сообщения другим узлам в своем самоутверждающем качестве и если другие узлы ему верят, вся система может совершить что-то неправильное.

Например, на Рисунке 8-4 показана ошибка повреждения данных из-за неправильной реализации блокировки. (Ошибка не теоретическая: у HBase раньше была такая проблема.) Предположим, вы хотите гарантировать, что файл в службе хранения может обрабатываться только одним клиентом за раз, потому что если бы несколько клиентов попытались записать в него, файл был бы поврежден. Вы пытаетесь реализовать это, требуя, чтобы клиент получил аренду от службы блокировки перед доступом к файлу.

Проблема является примером того, о чем мы говорили в разделе «Паузы процесса»: если клиент, удерживающий аренду, находится на паузе слишком долго, его аренда истекает. Другой клиент может получить аренду на тот же файл и начать запись в файл. Когда приостановленный клиент возвращается, он считает (неверно), что у него по-прежнему есть действующая аренда, и продолжает также писать в файл. В результате записи клиентов сталкиваются и портят файл.

При использовании блокировки или аренды для защиты доступа к некоторому ресурсу, такому как хранилище файлов на Рисунке 8-4, нам нужно обеспечить, чтобы узел, ошибочно считающий себя «избранным», не мог нарушить остальную систему. Довольно простой метод, достигающий этой цели, называется ограничивающим (fencing) и иллюстрируется на Рисунке 8-5.

Предположим, что каждый раз, когда служба блокировки предоставляет блокировку или аренду, она также возвращает ограничивающую метку (fencing token), которая представляет собой число, увеличивающееся каждый раз при предоставлении блокировки (например, увеличивается службой блокировки). Мы можем требовать, чтобы каждый раз, когда клиент отправляет запрос на запись в службу хранения, он включал свою текущую ограничивающую метку. На Рисунке 8-5 Клиент 1 получает аренду с меткой 33, но затем вступает в длительную паузу и аренда истекает. Клиент 2 получает аренду с меткой 34 (число всегда увеличивается), а затем отправляет запрос на запись в службу хранения, включая метку 34. Позже Клиент 1 восстанавливает свою активность и отправляет свою запись в службу хранения, включая свою метку 33. Однако служба хранения помнит, что она уже обработала запись с более высоким номером метки (34) и поэтому отклоняет запрос с меткой 33.

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

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

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

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

В этой книге мы предполагаем, что узлы ненадёжны, но честны: они могут быть медленными или вообще не отвечать (из-за сбоя) и их состояние может быть устаревшим (из-за паузы сборки мусора или задержек в сети), но мы предполагаем, что если узел отвечает, он говорит «правду»: по мере своих знаний, он следует правилам протокола.

Проблемы распределённых систем становятся намного сложнее, если существует риск того, что узлы могут «лгать» (посылать произвольные ошибочные или искажённые ответы) — например, если узел может утверждать, что он получил определённое сообщение, когда на самом деле этого не произошло. Такое поведение известно как Византийский сбой (Byzantine fault) и проблема достижения согласия в этой недоверчивой среде известна как Задача византийских генералов (The Byzantine Generals Problem).

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

• В аэрокосмической отрасли данные в памяти компьютера или регистре ЦП могут быть повреждены излучением, что приведёт к непредсказуемым реакциям. Поскольку отказ системы обойдется очень дорого (например, крушение самолета и гибель всех на борту или столкновение ракеты с Международной космической станцией), системы управления полетом должны выдерживать византийские сбои.
• В системе с участием нескольких организаций некоторые участники могут попытаться обмануть других или мошенничать. В таких обстоятельствах узлу небезопасно просто доверять сообщениям другого узла, так как они могут быть отправлены с вредоносным намерением. Например, пиринговые сети, такие как Bitcoin и другие блокчейны, могут рассматриваться как способ добиться согласия между взаимно недоверяющими сторонами относительно того, произошла ли транзакция, без использования центрального органа управления.

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

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

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

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

Хотя мы предполагаем, что узлы в целом честны, иногда стоит добавить в программное обеспечение механизмы, защищающие от слабых форм «лжи», таких как недействительные сообщения из-за проблем с аппаратурой, ошибок в программном обеспечении и неправильной конфигурации. Такие механизмы защиты не являются полноценной византийской устойчивостью, так как они не выдерживают настойчивого противника, но тем не менее, это простые и прагматичные шаги к повышению надёжности. Например:

• Сетевые пакеты иногда могут быть повреждены из-за проблем с аппаратурой или ошибок в операционных системах, драйверах, маршрутизаторах и т. д. Обычно поврежденные пакеты обнаруживаются контрольными суммами, встроенными в TCP и UDP, но иногда они ускользают от обнаружения. Обычно достаточными мерами защиты от таких повреждений являются, например, контрольные суммы в протоколе на уровне приложения.
• Общедоступное приложение должно тщательно проверять все вводы от пользователей, например, проверку того, что значение находится в разумном диапазоне и ограничение размера строк для предотвращения отказа в обслуживании из-за больших выделений памяти. Внутренний сервис за брандмауэром может обойтись менее строгими проверками ввода, но некоторая базовая проверка целостности значений (например, при разборе протокола) — это хорошая идея.
• Клиенты NTP могут быть настроены с несколькими адресами серверов. При синхронизации клиент обращается ко всем из них, оценивает их ошибки и проверяет, что большинство серверов согласны на какой-то временной интервал. Пока большинство серверов в порядке, неправильное настроенный сервер NTP, сообщающий неверное время, обнаруживается как выброс и исключается из синхронизации. Использование нескольких серверов делает NTP более надёжным, чем если бы он использовал только один сервер.

Для решения проблем распределённых систем было разработано множество алгоритмов. Например, мы рассмотрим решения для задачи достижения согласия в Главе 9. Чтобы эти алгоритмы были полезными, они должны выдерживать различные сбои распределённых систем, о которых мы говорили в этой главе.

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

Что касается предположений о времени, в общем использовании три модели систем:

Синхронная модель

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

Модель частичной синхронизации

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

Асинхронная модель

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

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

Сбои с остановкой

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

Сбои с восстановлением

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

Византийские (произвольные) сбои

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

Для моделирования реальных систем частичная синхронная модель со сбоями и восстановлением обычно является наиболее подходящей моделью. Но как распределённые алгоритмы справляются с этой моделью?

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

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

Уникальность

Нет двух запросов на получение ограничивающей метки, возвращающих одно и то же значение.
Монотонная последовательность
Если запрос x вернул метку tx, и запрос y вернул метку ty и x завершился до начала y, то tx < ty.

Доступность

Узел, запрашивающий ограничивающую метку и завершающийся не аварийно, в конечном итоге получает ответ.

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

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

Что отличает эти два вида свойств? Характерным признаком является то, что свойства активности часто включают слово «в конечном итоге» в их определении. (И да, вы угадали — конечная согласованность является свойством активности.)

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

• Если нарушается свойство безопасности, мы можем указать на конкретный момент времени, в который оно было нарушено (например, если свойство уникальности было нарушено, мы можем идентифицировать конкретную операцию, в которой была возвращена дубликатная метка ограждения). После нарушения свойства безопасности нарушение не может быть отменено — ущерб уже нанесен.
• Свойства активности действуют наоборот: они могут не соблюдаться в какой-то момент времени (например, узел может отправить запрос, но ещё не получил ответ), но всегда есть надежда, что они будут выполнены в будущем (а именно, получив ответ).

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

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

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

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

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

Теоретическое описание алгоритма может заявлять, что некоторые вещи просто предполагаются как невозможные и в невизантийских системах нам приходится делать некоторые предположения о том, какие сбои могут и не могут произойти. Однако реальная реализация может по-прежнему включать код для обработки случая, когда происходит что-то, что предполагалось невозможным, даже если эта обработка сводится к printf(«Вам не повезло») и exit(666) — т.е. позволяет человеку-оператору уладить ситуацию. (Это, вероятно, различие между компьютерной наукой и программной инженерией.) Это не говорит о том, что теоретические, абстрактные модели систем бесполезны — наоборот. Они чрезвычайно полезны для упрощения сложности реальных систем до управляемого набора сбоев, о которых мы можем рассуждать, чтобы понять проблему и попытаться решить её систематически. Мы можем доказать корректность алгоритмов, показывая, что их свойства всегда соблюдаются в некоторой модели системы.

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

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

• Потерю и произвольную задержку пакетов при отправке по сети, а также возможную потерю или задержку ответа, создающие неопределённость в доставке сообщения.
• Существенное расхождение часов узла с часами других узлов, возможные скачки времени и опасность полагаться на них из-за отсутствия уверенности.
• Возможность остановки выполнения процесса на значительное время в любой момент (например, из-за сборщика мусора), объявление о его «смерти» от других узлов и последующее воскрешение, без осознания им паузы.

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

Первым шагом к преодолению сбоев является их обнаружение, что само по себе трудно. Большинство систем не имеют четкого механизма обнаружения сбоев узла, поэтому большинство распределённых алгоритмов полагаются на тайм-ауты для определения доступности удалённого узла. Тем не менее тайм-ауты не могут различать сбои сети и узла, и переменная задержка в сети может привести к ложному подозрению в отказе. Более того, узел может находиться в деградированном состоянии: например, сетевой интерфейс Gigabit может внезапно упасть до пропускной способности 1 Кб/с из-за ошибки драйвера. Такой узел, который «хромает», но не мёртв, может быть ещё сложнее обработать, чем точно отказавший узел.

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

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

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

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

Мы также затронули тему суперкомпьютеров, которые предполагают использование надёжных компонентов и поэтому должны полностью останавливаться и перезапускаться при сбое одного из компонентов. В отличие от них распределённые системы могут работать бесконечно, не прерываясь на время обслуживания, потому что все сбои и обслуживание можно обрабатывать на уровне узла — по крайней мере в теории. (На практике, если неправильное изменение конфигурации распространяется на все узлы, это всё равно приведёт к параличу распределённой системы.)

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