Как компьютерный инженер, который пять лет занимался проблемами кэша в Intel и Sun, я немного разбираюсь в когерентности кэша. Это одна из самых трудных концепций, которые пришлось изучить ещё в колледже. Но как только вы действительно её освоили, то приходит гораздо лучшее понимание принципов проектирования систем.
Вы можете удивиться: зачем же разработчику ПО думать о механизме кэширования в CPU? Отвечу. С одной стороны, многие понятия из концепции когерентности кэша непосредственно применимы в распределённых системах и на уровнях изоляции СУБД. Например, представление реализации когерентности в аппаратных кэшах помогает лучше понять разницу в моделях согласованности(консистентности) — отличие строгой согласованности (strong consistency) от согласованности в конечном счёте (eventual consistency). У вас могут появиться новые идеи, как лучше обеспечить согласованность в распределённых системах, используя исследования и принципы из аппаратного обеспечения.
С другой стороны, неправильные представления о кэшах часто приводят к ложным утверждениям, особенно когда речь идёт о параллелизме и состоянии гонки. Например, часто говорят о трудности параллельного программирования, потому что «у разных ядер в кэшах могут быть разные/устаревшие значения». Или что квалификатор volatile в языках вроде Java нужен, чтобы «предотвратить локальное кэширование общих данных» и принудительно «читать/записывать только в основную память».
Такие заблуждения в основном безвредны (и могут быть даже полезны), но также ведут к плохим решениям при проектировании. Например, разработчики могут подумать, что они избавлены от вышеупомянутых ошибок параллелизма при работе с одноядерными системами. В действительности даже одноядерные системы подвержены риску ошибок параллелизма, если не используются соответствующие конструкции параллелизма.
Или ещё пример. Если переменные volatile действительно каждый раз пишутся/считываются из основной памяти, то они будут чудовищно медленными — ссылки в основной памяти в 200 раз медленнее, чем в кэше L1. На самом деле volatile-reads (в Java) часто настолько же производительны, как из кэша L1, и это развенчивает миф, будто volatile принуждает читает/записывать только в основную память. Если вы избегали volatile из-за проблем с производительностью, возможно, вы стали жертвой вышеуказанных заблуждений.
Важность согласованности
Но если у разных ядер собственный кэш, хранящий копии одних и тех же данных, не приведёт ли это к несоответствию записей? Ответ: аппаратные кэши в современных процессорах x86, как у Intel, всегда синхронизируются. Эти кэши не просто тупые блоки памяти, как многие разработчики, похоже, думают. Наоборот, очень сложные протоколы и встроенная логика взаимодействия между кэшами обеспечивает согласованность во всех потоках. И всё это происходит на аппаратном уровне, то есть нам, разработчикам программного обеспечения/компиляторов/систем, не нужно об этом думать.
Кратко объясню, что имеется в виду под «синхронизированными» кэшами. Здесь много нюансов, но в максимальном упрощении: если два разных потока в любом месте системы читают с одного и того же адреса памяти, то они никогда не должны одновременно считывать разные значения.
В качестве простого примера, как непротиворечивые кэши могут нарушить вышеупомянутое правило, просто обратитесь к первому разделу этого учебника. Ни один современный процессор x86 не ведёт себя так, как описано в учебнике, но глючный процессор, безусловно, может. Наша статья посвящена одной простой цели: предотвращению таких несоответствий.
Наиболее распространённый протокол для обеспечения согласованности между кэшами известен как протокол MESI. У каждого процессора своя реализация MESI, и у разных вариантов есть свои преимущества, компромиссы и возможности для уникальных багов. Однако у всех них есть общий принцип: каждая строка данных в кэше помечена одним из следующих состояний:
- Модифицированное состояние (M).
- Эти данные модифицированы и отличаются от основной памяти.
- Эти данные являются источником истины, а все остальные источники устарели.
- Эксклюзивное (E).
- Эти данные не модифицированы и синхронизированы с основной памятью.
- Ни в одном другом кэше того же уровня нет этих данных.
- Общее (S).
- Эти данные не модифицированы и синхронизированы.
- В других кэшах того же уровня тоже (возможно) есть те же данные.
- Недействительное (I).
- Эти данные устарели и не должны использоваться.
Если мы применяем и обновляем вышеуказанные состояния, то можно добиться согласованности кэша. Рассмотрим несколько примеров для процессора с четырьмя ядрами, у каждого из которых собственный кэш L1, а также глобальный кэш L2 на кристалле.
Запись в память
Предположим, что поток на core-1 хочет записать в память по адресу 0xabcd. Ниже приведены некоторые возможные последовательности событий.
Попадание в кэш
- В L1-1 есть данные в состоянии E или M.
- L1-1 производит запись. Всё готово.
- Ни в одном другом кэше нет данных, так что немедленная запись будет безопасной.
- Состояние строки кэша изменяется на M, поскольку она теперь изменена.
Промах локального кэша, попадание одноуровневого кэша
- В L1-1 есть данные в состоянии S.
- Это значит, что в другом одноуровневом кэше могут быть эти данные.
- Та же последовательность применяется, если в L1-1 вообще нет этих данных.
- L1-1 отправляет Request-For-Ownership в кэш L2.
- L2 смотрит по своему каталогу и видит, что в L1-2 сейчас есть эти данные в состоянии S.
- L2 отправляет snoop-invalidate в L1-2.
- L1-2 помечает данные как недействительные (I).
- L1-2 отправляет запрос Ack в L2.
- L2 отправляет Ack вместе с последними данными в L1-1.
- L2 проверяет, что в L1-1 эти данные хранятся в состоянии E.
- В L1-1 теперь последние данные, а также разрешение войти в состояние E.
- L1-1 осуществляет запись и изменяет состояние этих данных на M.
Чтение памяти
Теперь предположим, что поток на core-2 хочет считать с адреса 0xabcd. Ниже приведены некоторые возможные последовательности событий.
Попадание кэша
- L1-2 имеет данные в состоянии S, E или M.
- L1-2 считывает данные и возвращает в поток. Готово.
Промах локального кэша, промах кэша верхнего уровня
- L1-2 имеет данные в состоянии I (недействительное), то есть не может их использовать.
- L1-2 отправляет запрос Request-for-Share в кэш L2.
- В L2 тоже нет данных. Он считывает данные из памяти.
- L2 возвращает данные из памяти.
- L2 отправляет данные в L1-2 с разрешением войти в состояние S.
- L2 проверяет, что в L1-2 эти данные хранятся в состоянии S.
- L1-2 получает данные, сохраняет их в кэше и отправляет в поток.
Промах локального кэша, попадание кэша верхнего уровня
- В L1-2 есть данные в состоянии I.
- L1-2 отправляет запрос Request-for-S в кэш L2.
- L2 видит, что в L1-1 данные в состоянии S.
- L2 отправляет Ack в L1-2, вместе с данными и разрешением войти в состояние S.
- L1-2 получает данные, сохраняет их в кэше и отправляет в поток.
Промах локального кэша, попадание одноуровневого кэша
- В L1-2 есть данные в состоянии I.
- L1-2 отправляет запрос Request-for-S в кэш L2.
- L2 видит, что в L1-1 данные в состоянии E (или M).
- L2 отправляет snoop-share в L1-1
- L1-1 понижает состояние до S.
- L1-1 отправляет Ack в L2 вместе с модифицированными данными, если это применимо.
- L2 отправляет Ack в L1-2 вместе с данными и разрешением войти в состояние S.
- L1-2 получает данные, сохраняет их в кэше и отправляет в поток.
Вариации
Выше приведены лишь некоторые из возможных сценариев. На самом деле существует много вариаций и нет двух одинаковых реализаций протокола. Например, в некоторых конструкциях используется состояние O/F. В некоторых есть кэши обратной записи, а другие используют сквозную запись. Некоторые используют snoop-трансляции, а другие — snoop-фильтр. В некоторых инклюзивные кэши, а в других — эксклюзивные. Вариации бесконечны, а мы даже не затронули буферы хранения(store-buffers)!
Кроме того, в приведённом примере рассматривается простой процессор всего с двумя уровнями кэширования. Но обратите внимание, что этот же протокол можно применить рекурсивно. Легко добавляется кэш L3, который, в свою очередь, координирует несколько кэшей L2, используя тот же протокол, что приведён выше. У вас может быть многопроцессорная система с «домашними агентами», которые координируют работу нескольких кэшей L3 на совершенно разных чипах.
В каждом сценарии каждому кэшу нужно взаимодействовать только с кэшем верхнего уровня (для получения данных/разрешений) и его потомками (для предоставления/отмены данных/разрешений). Всё это происходит невидимо для программного потока. С точки зрения софта подсистема памяти выглядит как единый, консистентный монолит… с очень переменными задержками.
Почему синхронизация по-прежнему важна
Мы обсудили удивительную мощность и согласованность системы памяти компьютера. Остался один вопрос: если кэши настолько последовательны, то зачем вообще нужны volatile в языках вроде Java?
Это очень сложный вопрос, на который лучше ответить в другом месте. Позвольте только немного намекнуть. Данные в регистрах CPU не синхронизируются с данными в кэше/памяти. Программный компилятор выполняет всевозможные оптимизации, когда дело доходит до загрузки данных в регистры, записи их обратно в кэш и даже переупорядочивания инструкций. Всё это делается при условии, что код будет выполняться в одном потоке. Поэтому любые данные, подверженные риску состояния гонки, следует защищать вручную с помощью параллельных алгоритмов и языковых конструкций вроде atomic и volatile.
В случае квалификатора volatile в Java решение отчасти состоит в том, чтобы заставить все операции чтения/записи идти в обход локальных регистров, а вместо этого немедленно обращаться к кэшу для чтения/записи. Как только данные считаны/записаны в кэш L1, вступает в силу протокол аппаратного согласования. Он обеспечивает гарантированную согласованность во всех глобальных потоках. Таким образом, если несколько потоков читают/записывают в одну переменную, все они синхронизированы друг с другом. Вот как достигается координация между потоками всего за 1 наносекунду.
