Это вторая и последняя часть моей шпаргалки по аббревиатурам, которые стоит знать C++ разработчику. С++ здесь упомянут только потому, что шпаргалку я составил в первую очередь для себя, а я как раз-таки C++ разработчик.
На самом деле в этой части собраны понятия, область применения которых не ограничена C++. Так что подборка может быть интересна более широкой аудитории.
Как и в первой части, аббревиатуры объединены в группы, если это имеет смысл. Если смысла нет — перечислены по алфавиту.
Параллелизм и атомарные операции:
• CAS
• ABA
• FAA
• RCU
Хранение данных:
• ACID
• CAP
• PACELC
• BASE
Принципы разработки ПО:
• DRY
• KISS
• YAGNI
• NIH
• FTSE
• GRASP
• SOLID
Прочее:
• ABI
• COW
• FBC, FBCP
• LRU
Compare And Swap. Сравнение с обменом. Это атомарная инструкция с тремя аргументами: атомарная переменная или адрес в памяти, ожидаемое значение, новое значение. Если и только если значение переменной совпадает с ожидаемым, переменная получает новое значение и инструкция завершается успешно. CAS либо просто возвращает булево значение (и тогда ее можно называть Compare And Set), либо в случае неудачи возвращает еще и текущее значение первого аргумента.
В C++ CAS представлена семействами методов
CAS инструкции используются для реализации примитивов синхронизации (таких, как мьютексы и семафоры) и свободных от блокировок алгоритмов. Часто приводят к проблеме ABA.
Почитать еще: раз (рус.), два (англ.)
A-B-A problem. Проблема A-B-A. Эта проблема возникает в параллельных алгоритмах, основанных на сравнении с обменом (см. CAS), например, в свободных от блокировок алгоримах. Суть в том, что поток читает значение атомарной переменной, делает что-то еще и обновляет эту переменную через сравнение с обменом. Т.е. логика потока такова: если переменная все еще содержит прежнее значение, значит ничего не изменилось, все в порядке. Но это может быть и не так. Более формальное описание проблемы:
Возможные решения проблемы:
Для применения в свободных от блокировок структур данных типа стека, списка, очереди — в общем там, где есть риск остаться с висящим указателем на удаленный узел — есть целое семейство решений проблемы ABA, основанное на отложенном удалении узлов. К нему относятся сборщик мусора, указатели опасности (hazard pointers) и механизм чтение-модификация-запись (см. RCU).
Почитать еще: раз (рус.), два (англ.), три (англ.)
Fetch And Add. Кхм… получить и добавить (кажется, это понятие никогда не переводится на русский). Атомарная операция с двумя аргументами: атомарная переменная или адрес в памяти, и величина, на которую эту переменную надо изменить. Если архитектура позволяет, операция возвращает прежнее значение измененной переменной (x86 позволяет со времен i486). В отличие от CAS, FAA всегда выполняется успешно.
В C++ реализована в виде семейств методов
Как и положено атомарной инструкции, FAA применяется в реализациях примитивов синхронизации и lock-free алгоритмов и структур данных.
Почитать еще: раз (рус.), два (англ.)
Read-Copy-Update. Чтение-модификация-запись. Это механизм неблокирующей синхронизации доступа к структуре данных (lock-free конечно же). Применяется в тех случаях, когда скорость чтения является критической. Является примером компромисса времени и памяти (space-time tradeoff).
Идея RCU в том, что поток-писатель не изменяет данные на месте, а создает копию, вносит в нее нужное изменение и атомарно меняет местами текущие данные и измененную копию. При этом потоки-читатели постоянно имеют доступ к данным — старым или новым, кто как успел. Когда не остается читателей, работающих с устаревшей версией, писатель удаляет уже ненужные данные, освобождая память.
Очень упрощенно RCU работает так:
RCU отлично подходит для данных, которые часто читаются и редко обновляются. Этот механизм активно используется в ядре Linux, где довольно просто определить момент окончания grace-периода.
Недостатки:
Почитать еще: раз (рус.), два (англ.)
Atomicity, Consistency, Isolation, Durability. Атомарность, согласованность, изолированность, долговечность. Это набор требований к транзакциям в СУБД. ACID обеспечивает надежную и предсказуемую работу СУБД даже в случае ошибок.
Все основные реляционные СУБД полностью поддерживают ACID. В мире NoSQL такая полная поддержка скорее исключение.
Почитать еще: раз (англ.), два (англ.)
CAP theorem. Теорема CAP. Теорема гласит, что любая распределенная система может обладать не более, чем двумя свойствами из списка: согласованность данных (Consistency), доступность (Availability), устойчивость к разделению (Partition tolerance).
Т.к. все три свойства недостижимы, с точки зрения CAP теоремы все распределенные системы распадаются на три класса: CA, CP и AP. CA системы очевидно не обладают устойчивостью к разделению. Т.к. в подавляющем большинстве случаев распределенность подразумевает распределенность по реальной сети, а в реальной сети всегда есть ненулевая вероятность потерять пакет, то CA системы малоинтересны.
Остается выбор между CP и AP, т. е. между согласованностью и доступностью. Традиционные реляционные СУБД, следующие принципам ACID, предпочитают согласованность. В то время как многие NoSQL решения выбирают доступность и BASE.
В случае нормальной работы сети, т. е. когда нет сетевого разделения, CAP теорема не накладывает никаких ограничений на согласованность и доступность. Т.е. чем-то жертвовать не обязательно.
Почитать еще: раз (рус.), два (англ.), три (англ.)
PACELC theorem. Теорема PACELC. Это расширение теоремы CAP, которое утверждает, что распределенная система в случае сетевого разделения (Partition) вынуждена выбирать между доступностью (Availability) и согласованностью (Consistency), а случае нормальной работы сети (Else) выбирать приходится между задержками (Latency) и согласованностью (Consistency).
Соответственно, если CAP теорема выделяла 2 класса систем, устойчивых с сетевому разделению, то у PACELC их 4: PA/EL, PA/EC, PC/EL и PC/EC. Некоторые NoSQL БД могут менять свой класс в зависимости от настроек.
Почитать еще: раз (рус.), два (англ.)
Basically Available, Soft state, Eventual consistency. Базовая доступность, неустойчивое состояние, согласованность в конечном счёте. Согласно CAP теореме в распределенных системах от чего-то придется отказаться. Обычно отказываются от строгой согласованности в пользу согласованности в конечном счете. Что означает, что в отсутствие изменений данных система когда-нибудь, в конечном счете придет в согласованное состояние.
Для обозначения такого компромисса стала несколько натянуто использоваться аббревиатура BASE, получилась игра химических терминов (ACID – кислотность, BASE – основность).
Почитать еще: раз (англ.), два (англ.)
Don’t Repeat Yourself. Не повторяйся. Это принцип разработки ПО, основная идея которого — уменьшить количество дублируемой информации в системе, а цель — снизить сложность системы и повысить ее управляемость.
В оригинале (книга The Pragmatic Programmer, авторы Andrew Hunt и David Thomas) этот принцип сформулирован так: «Каждая часть знания должна иметь единственное, непротиворечивое и авторитетное представление в рамках системы». Под знанием в данном случае понимается любая часть предметной области или алгоритма: код, схема БД, некий протокол взаимодействия и т. д. Таким образом, чтобы внести в систему одно изменение, нужно обновить лишь одно «знание» в одном месте.
Тупой пример: клиент и сервер передают друг другу структурированные данные. Т.к. это разные приложения, работающие на разных машинах, то они оба должны иметь свои собственные реализации этих структур. Если что-то меняется, изменения придется вносить в двух местах. Очевидный шаг избежать этого повторения — выделить общий код в отдельную библиотеку. Следующий шаг — генерировать ее по описанию структур (Google Protocol Buffers, например), чтобы не писать однотипный код для доступа к полям структур.
Дублирование кода является лишь частным случаем нарушения DRY. И то не всегда. Если два куска кода выглядят одинаково, но реализуют каждый свою бизнес-логику, DRY не нарушен.
Как и любой другой принцип DRY – инструмент, а не догма. Чем крупнее система, тем легче нарушить этот принцип. Во-первых, идеал недостижим. А во-вторых, если слепое следование DRY приводит к усложнению кода и делает его труднее для понимания, то лучше от него отказаться.
Почитать еще: раз (рус.), два (рус.)
Keep It Simple, Stupid. Делай проще (stupid в данном случае — не обращение). Это принцип проектирования, согласно которому большинство систем работают лучше, если остаются простыми. Принцип зародился в авиастроении и применяется много где, в том числе и в разработке ПО.
В последнем случае KISS полезен и при проектировании, и при непосредственном написании кода. Простые архитектура и код не только доступнее для понимания, их еще и проще правильно использовать, поддерживать и развивать. Не стоит городить MapReduce, если достаточно пары производитель-потребитель. Магия метапрограммирования избыточно сложна, если можно обойтись парой обычных функций и достичь требуемого уровня производительности.
При всем при этом надо не забывать, что простота — не цель, а лишь нефункциональное требование. Главное — достичь цели проектирования/реализации, и желательно сделать это максимально простым способом.
Почитать еще: раз (рус.), два (рус.), три (англ.)
You Ain’t Gonna Need It. Вам это не понадобится. Это принцип разработки ПО, основная идея которого — отказ от избыточной функциональности, а цель — экономия ресурсов, затраченных на разработку.
YAGNI говорит, что не надо ни проектировать, ни реализовывать функции, которые не нужны прямо сейчас. Даже если вы уверены, что они потребуются в будущем. Не надо добавлять лишние абстракции, польза от которых появится когда-нибудь потом.
Проблема в том, что люди плохо предсказывают будущее. Поэтому скорее всего все, сделанное «про запас», просто не пригодится. И получится, что время и деньги, потраченные на такие разработку, тестирование, документацию, — потрачены зря. Плюс ПО стало сложнее, приходится опять тратить дополнительные ресурсы на его поддержку. Еще хуже, когда выясняется, что делать надо было по-другому. Деньги и время будут потрачены еще и на исправление.
Принцип YAGNI несколько радикальнее DRY и KISS. Если те разбивают систему на понятные части и делают решения простыми, то YAGNI просто вырезает ненужные части и решения.
Почитать еще: раз (рус.), два (англ.), три (англ.)
Not Invented Here. Изобретено не здесь. Это синдром неприятия чужих разработок, позиция, практически граничащая с изобретением велосипеда. Часто синдрому сопутствует убежденность, что создать технологию внутри компании будет и быстрее, и дешевле, а сама технология будет лучше соответствовать нуждам компании. Однако в большинстве случаев это не так, а NIH является анти-паттерном.
Вот несколько случаев, оправдывающих NIH:
Почитать еще: раз (рус.), два (англ.), три (англ.)
Fundamental Theorem of Software Engineering. Фундаментальная теорема разработки ПО. На самом деле это не теорема, никакого доказательства у нее нет. Это известное высказывание Эндрю Кёнига (Andrew Koenig):
Почитать еще: раз (англ.), два (англ.)
General Responsibility Assignment Software Patterns. Общие шаблоны распределения ответственностей. Эти девять шаблонов сформулированы в книге Applying UML and Patterns, автор Craig Larman. Каждый шаблон представляет собой типовое решение одной (но довольно общей) проблемы проектирования ПО.
Шаблоны GRASP постоянно пересекаются с шаблонами Банды Четырех и принципами SOLID. Это нормально, т. к. все они решают общую задачу — упростить создание качественного ПО.
Почитать еще: раз (рус.), два (англ.), три (рус.)
Принципы SOLID. Это пять принципов объектно-ориентированных программирования и дизайна (из первых букв их названий и составлена аббревиатура). Получили известность благодаря Роберту Мартину (Robert Martin) в начале 2000-х. Основная цель принципов — создание ПО, которое легко понимать, поддерживать и расширять.
Почитать еще: раз (рус.), два (англ.), три (англ.)
Application Binary Interface. Бинарный интерфейс приложений. Это набор соглашений, определяющий взаимодействие бинарных модулей (исполняемых файлов, библиотек, ОС). Два модуля должны быть созданы с соблюдением одного ABI – это является необходимым условием их бинарной совместимости, в этом случае они могут взаимодействовать без проблем (например, исполняемый файл линковаться с библиотекой и выполняться операционной системой).
Примерами ABI являются форматы исполняемых файлов ELF в Linux и PE в Windows. Каждая ОС ожидает, что нужные данные (ресурсы, точка входа, etc.) расположены в бинарном файле согласно соответствующему формату. Очевидно, ELF и PE различаются, потому линуксовые программы не запускаются напрямую на винде и наоборот.
На уровне библиотек и исполняемых файлов ABI может определять размещение полей внутри класса, базовых классов внутри потомков, механизм реализации виртуальных функций, формат фрейма стека вызовов, правила передачи аргументов в вызываемую функцию, и т. д. и т. п.
У C++ нет единого стандартного ABI, что неудивительно, т. к. он зависит от архитектуры и ОС. Например, компиляторы C++ для многих Unix-подобных ОС (Linux, FreeBSD, MacOS) на x86_64 следуют System V AMD64 ABI, на ARM – ARM C++ ABI. Visual C++ ABI официально не опубликован, но как минимум частично отреверсинженирен. Он сильно отличается от System V ABI, у них совершенно разные правила сокрытия имен (mangling) и передачи аргументов в вызываемую функцию (в Linux используются 6 регистров, в Windows – 4), и куча других отличий.
Даже если API и ABI остаются прежними, а меняются только детали реализации, бинарная совместимость может нарушаться. Например в C++11 появилось требование к строкам хранить символы последовательно (как в векторе). Из-за этого GCC 5 пришлось изменить реализацию строк (раньше там использовался COW), что привело к бинарной несовместимости.
Почитать еще: раз (рус.), два (англ.) и все ссылки из двух предыдущих абзацев.
Copy On Write. Копирование при записи. Это механизм управления ресурсами, так же известный как implicit sharing и lazy copy. Идея в том, что когда требуется копия, ресурс на самом деле не копируется, но создается ссылка на него. И лишь когда поступает запрос на внесение изменений — в оригинал или в «копию» — только тогда происходит создание полноценной копии.
Преимущество COW очевидно: копирование любого объекта происходит мгновенно. Если объекты часто копируются, но редко изменяются, выигрыш в производительности может быть существенным.
Примеры использования COW:
Почитать еще: раз (англ.), два (англ.)
Fragile Base Class (Problem). Проблема хрупкого базового класса. Это фундаментальная проблема ООП, суть ее в том, что корректное изменение базового класса может привести к ошибке в одном из наследников.
Решить проблему FBC можно только отказавшись от наследования в пользу композиции, например, или расширения интерфейсов в терминологии Java (в C++ это будет наследование только абстрактным базовым классам без состояния и реализаций методов). В остальных случаях можно только попытаться минимизировать вероятность FBCP с помощью следующих советов:
Почитать еще: раз (англ.), два (англ.), три (англ.)
Least Recently Used. Вытеснение давно не используемых. Это один из алгоритмов кэширования (они же политики вытеснения). В общем случае можно считать кэш быстрым хранилищем пар «ключ-значение», одна из основных характеристик которого — уровень попаданий (hit ratio). Чем выше этот уровень, тем чаще нужное значение находится в быстром кэше и тем реже его надо искать в медленном хранилище. Но поскольку память никогда не бывает резиновой, размер кэша приходится ограничивать. Задача алгоритмов кэширования — определить, какой элемент выкинуть из заполненного кэша в случае необходимости так, чтобы максимизировать уровень попаданий.
LRU вытесняет их кэша элемент, к которому дольше всех никто не обращался. Это, пожалуй, самый известный алгоритм кэширования. Наверное, в силу сочетания эффективности и простоты. Расход памяти у LRU — O(n), среднее время доступа к значению — O(1), среднее время добавления элемента — так же O(1). Для реализации обычно используется хэш-таблица и двусвязный список.
Очевидным недостатком LRU является большой расход памяти, т. к. он использует две структуры по n элементов. Помимо LRU есть множество других алгоритмов кэширования для самых разных случаев: MRU (Most Recently Used), LFU (Least Frequently Used), Segmented LRU, 2Q и т. д.
Почитать еще: раз (англ.), два (рус.), три (англ.)
Если я что-то упустил или где-то ошибся — пишите в комментариях.
На самом деле в этой части собраны понятия, область применения которых не ограничена C++. Так что подборка может быть интересна более широкой аудитории.
Как и в первой части, аббревиатуры объединены в группы, если это имеет смысл. Если смысла нет — перечислены по алфавиту.
Параллелизм и атомарные операции:
• CAS
• ABA
• FAA
• RCU
Хранение данных:
• ACID
• CAP
• PACELC
• BASE
Принципы разработки ПО:
• DRY
• KISS
• YAGNI
• NIH
• FTSE
• GRASP
• SOLID
Прочее:
• ABI
• COW
• FBC, FBCP
• LRU
Параллелизм и атомарные операции
CAS
Compare And Swap. Сравнение с обменом. Это атомарная инструкция с тремя аргументами: атомарная переменная или адрес в памяти, ожидаемое значение, новое значение. Если и только если значение переменной совпадает с ожидаемым, переменная получает новое значение и инструкция завершается успешно. CAS либо просто возвращает булево значение (и тогда ее можно называть Compare And Set), либо в случае неудачи возвращает еще и текущее значение первого аргумента.
Псевдокод
bool cas(int* addr, int& expected, int new_value)
{
if (*addr != expected)
{
expected = *addr;
return false;
}
*addr = new_value;
return true;
}В C++ CAS представлена семействами методов
std::atomic<T>::compare_exchange_weak, std::atomic<T>::compare_exchange_strong и свободных функций std::atomic_compare_exchange_weak, std::atomic_compare_exchange_strong. Разница между *weak и *strong в том, что первые могут выдавать ложно-отрицательные результаты. Т.е. если значение равно ожидаемому, они вернут false и не заменят его на новое. Причина существования *weak операций в том, что на некоторых архитектурах *strong относительно дороги. В большинстве случаев CAS инструкции крутятся в цикле (т. н. CAS loop), поэтому использование *weak вместо *strong не изменит логику, но может повысить производительность.CAS инструкции используются для реализации примитивов синхронизации (таких, как мьютексы и семафоры) и свободных от блокировок алгоритмов. Часто приводят к проблеме ABA.
Почитать еще: раз (рус.), два (англ.)
ABA
A-B-A problem. Проблема A-B-A. Эта проблема возникает в параллельных алгоритмах, основанных на сравнении с обменом (см. CAS), например, в свободных от блокировок алгоримах. Суть в том, что поток читает значение атомарной переменной, делает что-то еще и обновляет эту переменную через сравнение с обменом. Т.е. логика потока такова: если переменная все еще содержит прежнее значение, значит ничего не изменилось, все в порядке. Но это может быть и не так. Более формальное описание проблемы:
- поток 1 читает значение переменной, оно равно A
- поток 1 вытесняется, начинает работу поток 2
- поток 2 меняет значение переменной с A на B, делает кучу изменений (меняет какое-то значение, ассоциируемое с переменной или просто освобождает память), а потом опять меняет значение — c B на A
- поток 1 возобновляет работу, сравнивает полученное ранее значение с текущим и делает вывод, что ничего не изменилось
Возможные решения проблемы:
- Самое простое и очевидное — использовать блокировки. Получится обычный потоко-безопасный алгоритм с критическими секциями. Но он перестанет быть свободным от блокировок. Но если дело дошло до CAS и ABA, то это скорее всего не вариант.
- Добавить специальные метки в сравниваемые значения. Например, счетчик числа изменений. С одной стороны, этот счетчик может переполниться, но с другой — современные x86_64 процессоры поддерживают 128-битные CAS операции. Т.е. при сравнении указателей под счетчик можно отдать до 64 бит, и кто-то прикинул, что этого хватит на 10 лет непрерывной работы алгоритма.
- Некоторые архитектуры (ARM, например) предоставляют инструкции LL/SC (load linked, store conditional), которые позволяют не только получить текущее значение адреса в памяти, но понять, были ли это значение изменено со времени последнего чтения.
Для применения в свободных от блокировок структур данных типа стека, списка, очереди — в общем там, где есть риск остаться с висящим указателем на удаленный узел — есть целое семейство решений проблемы ABA, основанное на отложенном удалении узлов. К нему относятся сборщик мусора, указатели опасности (hazard pointers) и механизм чтение-модификация-запись (см. RCU).
Почитать еще: раз (рус.), два (англ.), три (англ.)
FAA
Fetch And Add. Кхм… получить и добавить (кажется, это понятие никогда не переводится на русский). Атомарная операция с двумя аргументами: атомарная переменная или адрес в памяти, и величина, на которую эту переменную надо изменить. Если архитектура позволяет, операция возвращает прежнее значение измененной переменной (x86 позволяет со времен i486). В отличие от CAS, FAA всегда выполняется успешно.
Псевдокод
int faa(int* addr, int diff)
{
int value = *addr;
*addr = value + diff;
return value;
}В C++ реализована в виде семейств методов
std::atomic<T>::fetch_add, fetch_sub, fetch_and, fetch_or, fetch_xor и соответствующих свободных функций std::atomic_fetch_add и т. п.Как и положено атомарной инструкции, FAA применяется в реализациях примитивов синхронизации и lock-free алгоритмов и структур данных.
Почитать еще: раз (рус.), два (англ.)
RCU
Read-Copy-Update. Чтение-модификация-запись. Это механизм неблокирующей синхронизации доступа к структуре данных (lock-free конечно же). Применяется в тех случаях, когда скорость чтения является критической. Является примером компромисса времени и памяти (space-time tradeoff).
Идея RCU в том, что поток-писатель не изменяет данные на месте, а создает копию, вносит в нее нужное изменение и атомарно меняет местами текущие данные и измененную копию. При этом потоки-читатели постоянно имеют доступ к данным — старым или новым, кто как успел. Когда не остается читателей, работающих с устаревшей версией, писатель удаляет уже ненужные данные, освобождая память.
Очень упрощенно RCU работает так:
- Много читателей, один писатель.
- Чтение и изменение происходят одновременно.
- Читатели используют очень легковесную синхронизацию. Фактически читатель всего лишь должен известить писателя в момент входа в критическую секцию и в момент выхода из нее. Работа с синхронизируемыми данными происходит только в критической секции.
- Писатель, как только атомарно подменил данные копией, объявляет начала так называемого grace-периода (grace period). Grace-период заканчивается, когда все читатели, находившиеся на момент начала этого периода в критических секциях, покинули свои критические секции. Теперь писатель может безопасно удалить устаревшие данные. Подразумевается, что все критические секции конечны, что гарантирует конечность grace-периода.
RCU отлично подходит для данных, которые часто читаются и редко обновляются. Этот механизм активно используется в ядре Linux, где довольно просто определить момент окончания grace-периода.
Недостатки:
- Плохо подходит для синхронизации доступа к часто изменяемым данным.
- Сложно реализуем в пространстве пользователя.
- Зависит от возможности атомарно изменять указатели на адрес в памяти, но не все архитектуры предоставляют такую возможность.
Почитать еще: раз (рус.), два (англ.)
Хранение данных
ACID
Atomicity, Consistency, Isolation, Durability. Атомарность, согласованность, изолированность, долговечность. Это набор требований к транзакциям в СУБД. ACID обеспечивает надежную и предсказуемую работу СУБД даже в случае ошибок.
- Атомарность гарантирует, что транзакция либо завершится полностью, либо ничего не сделает. Промежуточное состояние невозможно, не будет такого, что одна операция транзакции выполнилась успешно, а другая — нет. Все или ничего.
- Согласованность гарантирует, что все данные в БД удовлетворяют всем заданным правилам и ограничениям как до начала транзакции, так и после ее завершения. В процессе выполнения транзакции согласованность может нарушаться.
- Изолированность гарантирует параллельные транзакции никак не влияют друг на друга. Ни одна транзакция не имеет доступа к несогласованным данным, обрабатываемым другой транзакцией.
- Долговечность означает, что результат успешной транзакции сохраняется в БД и не может быть потерян, что бы ни случилось с БД сразу по завершении транзакции.
Все основные реляционные СУБД полностью поддерживают ACID. В мире NoSQL такая полная поддержка скорее исключение.
Почитать еще: раз (англ.), два (англ.)
CAP
CAP theorem. Теорема CAP. Теорема гласит, что любая распределенная система может обладать не более, чем двумя свойствами из списка: согласованность данных (Consistency), доступность (Availability), устойчивость к разделению (Partition tolerance).
- Согласованность в данном случае означает (упрощенно) последовательную согласованность. Т.е. как только операция обновления данных на одном узле успешно завершилась, все остальные узлы уже имеют у себя эти обновленные данные. Соответственно, все узлы находятся в согласованном состоянии. Это не та согласованность, которая требуется в ACID.
- Доступность означает, что каждый не упавший узел возвращает корректный ответ на каждый запрос (и на чтение, и на запись) за разумное время. Гарантия, что ответы разных узлов совпадают, отсутствует.
- Устойчивость к разделению означает, что система продолжит работать корректно в случае потери произвольного числа сообщений между ее узлами.
Т.к. все три свойства недостижимы, с точки зрения CAP теоремы все распределенные системы распадаются на три класса: CA, CP и AP. CA системы очевидно не обладают устойчивостью к разделению. Т.к. в подавляющем большинстве случаев распределенность подразумевает распределенность по реальной сети, а в реальной сети всегда есть ненулевая вероятность потерять пакет, то CA системы малоинтересны.
Остается выбор между CP и AP, т. е. между согласованностью и доступностью. Традиционные реляционные СУБД, следующие принципам ACID, предпочитают согласованность. В то время как многие NoSQL решения выбирают доступность и BASE.
В случае нормальной работы сети, т. е. когда нет сетевого разделения, CAP теорема не накладывает никаких ограничений на согласованность и доступность. Т.е. чем-то жертвовать не обязательно.
Почитать еще: раз (рус.), два (англ.), три (англ.)
PACELC
PACELC theorem. Теорема PACELC. Это расширение теоремы CAP, которое утверждает, что распределенная система в случае сетевого разделения (Partition) вынуждена выбирать между доступностью (Availability) и согласованностью (Consistency), а случае нормальной работы сети (Else) выбирать приходится между задержками (Latency) и согласованностью (Consistency).
Соответственно, если CAP теорема выделяла 2 класса систем, устойчивых с сетевому разделению, то у PACELC их 4: PA/EL, PA/EC, PC/EL и PC/EC. Некоторые NoSQL БД могут менять свой класс в зависимости от настроек.
Почитать еще: раз (рус.), два (англ.)
BASE
Basically Available, Soft state, Eventual consistency. Базовая доступность, неустойчивое состояние, согласованность в конечном счёте. Согласно CAP теореме в распределенных системах от чего-то придется отказаться. Обычно отказываются от строгой согласованности в пользу согласованности в конечном счете. Что означает, что в отсутствие изменений данных система когда-нибудь, в конечном счете придет в согласованное состояние.
Для обозначения такого компромисса стала несколько натянуто использоваться аббревиатура BASE, получилась игра химических терминов (ACID – кислотность, BASE – основность).
- Basically Available означает, что система гарантирует доступность данных, она отвечает на каждый запрос. Но ответом могут быть устаревшие или несогласованные данные (или их отсутствие)
- Soft state означает, что состояние системы может меняться со временем даже в отсутствие запросов на изменение данных. Потому что в любой момент времени данные могут приводиться в согласованное состояние.
- Eventual consistency означает, что если данные перестанут изменяться, они в конечно счете придут в согласованное состояние. Т.е. один и тот же запрос к разным узлам будет приводить к одинаковым ответам.
Почитать еще: раз (англ.), два (англ.)
Принципы разработки ПО
DRY
Don’t Repeat Yourself. Не повторяйся. Это принцип разработки ПО, основная идея которого — уменьшить количество дублируемой информации в системе, а цель — снизить сложность системы и повысить ее управляемость.
В оригинале (книга The Pragmatic Programmer, авторы Andrew Hunt и David Thomas) этот принцип сформулирован так: «Каждая часть знания должна иметь единственное, непротиворечивое и авторитетное представление в рамках системы». Под знанием в данном случае понимается любая часть предметной области или алгоритма: код, схема БД, некий протокол взаимодействия и т. д. Таким образом, чтобы внести в систему одно изменение, нужно обновить лишь одно «знание» в одном месте.
Тупой пример: клиент и сервер передают друг другу структурированные данные. Т.к. это разные приложения, работающие на разных машинах, то они оба должны иметь свои собственные реализации этих структур. Если что-то меняется, изменения придется вносить в двух местах. Очевидный шаг избежать этого повторения — выделить общий код в отдельную библиотеку. Следующий шаг — генерировать ее по описанию структур (Google Protocol Buffers, например), чтобы не писать однотипный код для доступа к полям структур.
Дублирование кода является лишь частным случаем нарушения DRY. И то не всегда. Если два куска кода выглядят одинаково, но реализуют каждый свою бизнес-логику, DRY не нарушен.
Как и любой другой принцип DRY – инструмент, а не догма. Чем крупнее система, тем легче нарушить этот принцип. Во-первых, идеал недостижим. А во-вторых, если слепое следование DRY приводит к усложнению кода и делает его труднее для понимания, то лучше от него отказаться.
Почитать еще: раз (рус.), два (рус.)
KISS
Keep It Simple, Stupid. Делай проще (stupid в данном случае — не обращение). Это принцип проектирования, согласно которому большинство систем работают лучше, если остаются простыми. Принцип зародился в авиастроении и применяется много где, в том числе и в разработке ПО.
В последнем случае KISS полезен и при проектировании, и при непосредственном написании кода. Простые архитектура и код не только доступнее для понимания, их еще и проще правильно использовать, поддерживать и развивать. Не стоит городить MapReduce, если достаточно пары производитель-потребитель. Магия метапрограммирования избыточно сложна, если можно обойтись парой обычных функций и достичь требуемого уровня производительности.
При всем при этом надо не забывать, что простота — не цель, а лишь нефункциональное требование. Главное — достичь цели проектирования/реализации, и желательно сделать это максимально простым способом.
Почитать еще: раз (рус.), два (рус.), три (англ.)
YAGNI
You Ain’t Gonna Need It. Вам это не понадобится. Это принцип разработки ПО, основная идея которого — отказ от избыточной функциональности, а цель — экономия ресурсов, затраченных на разработку.
YAGNI говорит, что не надо ни проектировать, ни реализовывать функции, которые не нужны прямо сейчас. Даже если вы уверены, что они потребуются в будущем. Не надо добавлять лишние абстракции, польза от которых появится когда-нибудь потом.
Проблема в том, что люди плохо предсказывают будущее. Поэтому скорее всего все, сделанное «про запас», просто не пригодится. И получится, что время и деньги, потраченные на такие разработку, тестирование, документацию, — потрачены зря. Плюс ПО стало сложнее, приходится опять тратить дополнительные ресурсы на его поддержку. Еще хуже, когда выясняется, что делать надо было по-другому. Деньги и время будут потрачены еще и на исправление.
Принцип YAGNI несколько радикальнее DRY и KISS. Если те разбивают систему на понятные части и делают решения простыми, то YAGNI просто вырезает ненужные части и решения.
Почитать еще: раз (рус.), два (англ.), три (англ.)
NIH
Not Invented Here. Изобретено не здесь. Это синдром неприятия чужих разработок, позиция, практически граничащая с изобретением велосипеда. Часто синдрому сопутствует убежденность, что создать технологию внутри компании будет и быстрее, и дешевле, а сама технология будет лучше соответствовать нуждам компании. Однако в большинстве случаев это не так, а NIH является анти-паттерном.
Вот несколько случаев, оправдывающих NIH:
- Качество стороннего решения недостаточно высоко, или цена недостаточно низка.
- Стороннее решение имеет лицензионные ограничения.
- Использование стороннего решения создает зависимость от его поставщика и таким образом угрожает бизнесу.
Почитать еще: раз (рус.), два (англ.), три (англ.)
FTSE
Fundamental Theorem of Software Engineering. Фундаментальная теорема разработки ПО. На самом деле это не теорема, никакого доказательства у нее нет. Это известное высказывание Эндрю Кёнига (Andrew Koenig):
Любую проблему можно решить добавлением еще одного слоя абстракции.Иногда к этой фразе добавляют «… кроме проблемы слишком большого количества слоев абстракции». В общем, «теорема» — штука несерьезная, но знать о ней стоит.
Почитать еще: раз (англ.), два (англ.)
GRASP
General Responsibility Assignment Software Patterns. Общие шаблоны распределения ответственностей. Эти девять шаблонов сформулированы в книге Applying UML and Patterns, автор Craig Larman. Каждый шаблон представляет собой типовое решение одной (но довольно общей) проблемы проектирования ПО.
- Информационный эксперт (Information Expert). Проблема: каков общий принцип распределения обязанностей между объектами? Решение: назначить обязанность тому, у кого есть информация, требуемая для выполнения этой обязанности.
- Создатель (Creator). Проблема: кто должен отвечать за создание нового объекта? Решение: класс B должен создавать экземпляры класса А, если выполняется одно или несколько из условий:
— класс B агрегирует или содержит экземпляры A
— B записывает A
— B активно использует A
— B обладает данными инициализации A - Низкая связность (Low Coupling). Проблема: как снизить влияние изменений? Как повысить возможность повторного использования? Решение: распределить обязанности так, чтобы связанность была низкой. Связанность (coupling) — мера того, насколько жестко соединены элементы, насколько сильно зависят один от другого. Т.е. рекомендуется связывать объекты так, чтобы они знали друг о друге лишь необходимый минимум.
- Высокое зацепление (High Cohesion). Проблема: как обеспечить возможность управления сложностью? Решение: распределять обязанности так, чтобы сохранялось высокое зацепление. Высокое зацепление означает, что обязанности одного элемента сфокусированы на одной области.
- Контроллер (Controller). Проблема: кто должен отвечать за обработку входных событий? Решение: назначить ответственным класс, который либо представляет всю системы или подсистему в целом (внешний контроллер), либо один конкретный сценарий (контроллер сценария или сессии). При этом контроллер не реализует реакцию на события, он делегирует это соответствующим исполнителям.
- Полиморфизм (Polymorphism). Проблема: как обрабатывать различные варианты поведения на основе типа? Решение: если поведение зависит от типа, назначить ответственным тип, реализующий то или иное поведение, доступ к типам осуществлять через обобщенный интерфейс.
- Чистая выдумка (Pure Fabrication). Проблема: какой класс должен обеспечить соблюдение принципов проектирования, если существующие не справляются? Решение: создать класс, не имеющий прототипа в предметной области и назначить ему сильно сцепленный набор нужных обязанностей.
- Перенаправление (Indirection). Проблема: как распределить обязанности, чтобы избежать прямого связывания в соответствии с Low Coupling? Решение: присвоить обязанности посреднику и заставить другие объекты общаться через него.
- Устойчивость к изменениям (Protected Variations). Проблема: как спроектировать объекты и подсистемы так, чтобы изменения в них не оказывали нежелательного влияния на другие элементы? Решение: найти возможные точки неустойчивости и создать вокруг них стабильный интерфейс, общение осуществлять только через такой интерфейс.
Шаблоны GRASP постоянно пересекаются с шаблонами Банды Четырех и принципами SOLID. Это нормально, т. к. все они решают общую задачу — упростить создание качественного ПО.
Почитать еще: раз (рус.), два (англ.), три (рус.)
SOLID
Принципы SOLID. Это пять принципов объектно-ориентированных программирования и дизайна (из первых букв их названий и составлена аббревиатура). Получили известность благодаря Роберту Мартину (Robert Martin) в начале 2000-х. Основная цель принципов — создание ПО, которое легко понимать, поддерживать и расширять.
- Принцип единственной ответственности (Single Responsibility Principle, SRP). Класс или модуль должен иметь только одну обязанность. «Делай лишь одну вещь, но делай ее хорошо».
- Принцип открытости/закрытости (Open Closed Principle, OCP). Программные сущности (классы, модули, функции) должны быть открыты для расширения, но закрыты для модификации. Классический пример: если надо получить другое поведение класса, то вместо изменения самого класса стоит создать его нового наследника и там реализовать поведение.
- Принцип подстановки Барбары Лисков (Liskov Substitution Principle, LSP). Объекты в программе должны быть заменяемыми на экземпляры их подтипов, и программа при этом должна оставаться корректной. Т.е. поведение классов-наследников не должно нарушать инварианты и контракты базового класса.
- Принцип разделения интерфейса (Interface Segregation Principle, ISP). Много специализированных интерфейсов лучше, чем один универсальный. Клиенты не должны зависеть от интерфейсов, которые они не используют. В частности, это означает, что не надо добавлять новую функциональность к уже существующему интерфейсу. Вместо этого надо создать новый интерфейс и пусть конкретные классы реализуют несколько интерфейсов, если надо.
- Принцип инверсии зависимостей (Dependency Inversion Principle, DIP). Модули верхних уровней не должны зависеть от модулей нижних уровней. Все модули должны зависеть от абстракций. Абстракции не должны зависеть от деталей. Детали должны зависеть от абстракций. Например, ни интерфейсы, ни конкретные классы не должны ни содержать, ни принимать в качестве аргументов своих методов другие конкретные классы, а только интерфейсы (в смысле Java и C#).
Почитать еще: раз (рус.), два (англ.), три (англ.)
Прочее
ABI
Application Binary Interface. Бинарный интерфейс приложений. Это набор соглашений, определяющий взаимодействие бинарных модулей (исполняемых файлов, библиотек, ОС). Два модуля должны быть созданы с соблюдением одного ABI – это является необходимым условием их бинарной совместимости, в этом случае они могут взаимодействовать без проблем (например, исполняемый файл линковаться с библиотекой и выполняться операционной системой).
Примерами ABI являются форматы исполняемых файлов ELF в Linux и PE в Windows. Каждая ОС ожидает, что нужные данные (ресурсы, точка входа, etc.) расположены в бинарном файле согласно соответствующему формату. Очевидно, ELF и PE различаются, потому линуксовые программы не запускаются напрямую на винде и наоборот.
На уровне библиотек и исполняемых файлов ABI может определять размещение полей внутри класса, базовых классов внутри потомков, механизм реализации виртуальных функций, формат фрейма стека вызовов, правила передачи аргументов в вызываемую функцию, и т. д. и т. п.
У C++ нет единого стандартного ABI, что неудивительно, т. к. он зависит от архитектуры и ОС. Например, компиляторы C++ для многих Unix-подобных ОС (Linux, FreeBSD, MacOS) на x86_64 следуют System V AMD64 ABI, на ARM – ARM C++ ABI. Visual C++ ABI официально не опубликован, но как минимум частично отреверсинженирен. Он сильно отличается от System V ABI, у них совершенно разные правила сокрытия имен (mangling) и передачи аргументов в вызываемую функцию (в Linux используются 6 регистров, в Windows – 4), и куча других отличий.
Даже если API и ABI остаются прежними, а меняются только детали реализации, бинарная совместимость может нарушаться. Например в C++11 появилось требование к строкам хранить символы последовательно (как в векторе). Из-за этого GCC 5 пришлось изменить реализацию строк (раньше там использовался COW), что привело к бинарной несовместимости.
Почитать еще: раз (рус.), два (англ.) и все ссылки из двух предыдущих абзацев.
COW
Copy On Write. Копирование при записи. Это механизм управления ресурсами, так же известный как implicit sharing и lazy copy. Идея в том, что когда требуется копия, ресурс на самом деле не копируется, но создается ссылка на него. И лишь когда поступает запрос на внесение изменений — в оригинал или в «копию» — только тогда происходит создание полноценной копии.
Преимущество COW очевидно: копирование любого объекта происходит мгновенно. Если объекты часто копируются, но редко изменяются, выигрыш в производительности может быть существенным.
Примеры использования COW:
- Управление виртуальной памятью процессов в Linux. При вызове
fork()страницы памяти процесса не копируются, а лишь помечаются как совместно используемые. - Создание снимков (snapshots) в некоторых файловых системах (Btrfs, ZFS) и базах данных (MS SQL Server).
- До С++11 некоторые реализации
std::stringиспользовали COW. В C++11 требования кstd::stringизменились (см. ABI). - Многие типы в Qt используют COW.
Почитать еще: раз (англ.), два (англ.)
FBC, FBCP
Fragile Base Class (Problem). Проблема хрупкого базового класса. Это фундаментальная проблема ООП, суть ее в том, что корректное изменение базового класса может привести к ошибке в одном из наследников.
Например, к бесконечной рекурсии
struct Base
{
virtual void method1()
{
// ...
}
virtual void method2()
{
// ...
method1(); // <-- вот эта строка была добавлена
}
};
struct Derived : Base
{
void method1() override
{
method2();
}
};Решить проблему FBC можно только отказавшись от наследования в пользу композиции, например, или расширения интерфейсов в терминологии Java (в C++ это будет наследование только абстрактным базовым классам без состояния и реализаций методов). В остальных случаях можно только попытаться минимизировать вероятность FBCP с помощью следующих советов:
- Запретить наследование или переопределение там, где они не нужны (ключевое слово
finalв C++ и Java). - Наследник не должен иметь доступа к внутренностям базового класса, общение может идти только через публичный интерфейс.
- Метод наследника может вызывать только те виртуальные методы, которые вызываются в переопределенном методе базового класса, и сам переопределенный метод.
Почитать еще: раз (англ.), два (англ.), три (англ.)
LRU
Least Recently Used. Вытеснение давно не используемых. Это один из алгоритмов кэширования (они же политики вытеснения). В общем случае можно считать кэш быстрым хранилищем пар «ключ-значение», одна из основных характеристик которого — уровень попаданий (hit ratio). Чем выше этот уровень, тем чаще нужное значение находится в быстром кэше и тем реже его надо искать в медленном хранилище. Но поскольку память никогда не бывает резиновой, размер кэша приходится ограничивать. Задача алгоритмов кэширования — определить, какой элемент выкинуть из заполненного кэша в случае необходимости так, чтобы максимизировать уровень попаданий.
LRU вытесняет их кэша элемент, к которому дольше всех никто не обращался. Это, пожалуй, самый известный алгоритм кэширования. Наверное, в силу сочетания эффективности и простоты. Расход памяти у LRU — O(n), среднее время доступа к значению — O(1), среднее время добавления элемента — так же O(1). Для реализации обычно используется хэш-таблица и двусвязный список.
Например, так
template <class K, class V>
class LRU
{
private:
using Queue = std::list<std::pair<K, V>>;
using Iterator = typename Queue::iterator;
using Hash = std::unordered_map<K, Iterator>;
Queue queue_;
Hash hash_;
const size_t limit_;
public:
LRU(size_t limit)
: limit_(limit)
{
}
std::optional<V> get(const K& key)
{
const auto it = hash_.find(key);
if (it == hash_.end())
{
return {};
}
it->second = reorder(it->second);
return { it->second->second };
}
void add(K&& key, V&& value)
{
if (hash_.size() >= limit_)
{
pop();
}
queue_.emplace_front(std::move(key), std::move(value));
const auto it = queue_.begin();
hash_[it->first] = it;
}
private:
Iterator reorder(Iterator it)
{
queue_.emplace_front(std::move(it->first), std::move(it->second));
queue_.erase(it);
return queue_.begin();
}
void pop()
{
hash_.erase(queue_.back().first);
queue_.pop_back();
}
};Очевидным недостатком LRU является большой расход памяти, т. к. он использует две структуры по n элементов. Помимо LRU есть множество других алгоритмов кэширования для самых разных случаев: MRU (Most Recently Used), LFU (Least Frequently Used), Segmented LRU, 2Q и т. д.
Почитать еще: раз (англ.), два (рус.), три (англ.)
P. S.
Если я что-то упустил или где-то ошибся — пишите в комментариях.
Комментарии (2)
PyerK
09.10.2019 16:54Я бы добавил в список аббревиатур для C++ ника ещё околожелезячное, всё таки многим приходится с этим работать:
RAM, SRAM, DRAM, CAS, RAS, RAID, CPU, DMA, VM, NUMA, SIMD (SISD), L1-L3, TLB, RFO
kdmitrii
Тут нужно явно сказать, что для работы такой чтуки все переменные должны быть выравнены на кеш-линию (т.е даже какойнить char будет занимать ~64 байта). В противном случае могут быть оооооооочень неочевидные ошибки. LL/CC понимает что переменная бала «изменена» если с последнего обращения кто-то тронул кеш линию, но это вполне могло быть изменение не вашей переменной, а просто какой-то случайной лежащей в той-же кеш линии.