Лучшее из любимого: 13 отличных статей о Computer Science

1. Проектирование и реализация журнально-структурированной файловой системы
(The Design and Implementation
of a Log-Structured File System)

Мендель Розенблюм, Джон К. Оустерхаут (Mendel Rosenblum, John K. Ousterhout)

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

2. Вездесущее B-дерево
(The Ubiquitous B-Tree)

Дуглас Комер (Douglas Comer)

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

3. Журнально-структурированное дерево со слиянием (The Log-Structured Merge-Tree)

Патрик О’Нил, Эдвард Ченг, Дитер Голик, Элизабет О’Нил (Patrick O’Neil, Edward Cheng, Dieter Gawlick, Elizabeth O’Neil)

💡 Продолжаем изучать эффективную и малозатратную индексацию. Теперь речь пойдёт о файле, в который долгое время активно вставляют новые записи. В статье также хорошо сравниваются затраты на ввод-вывод данных для LSM-деревьев и B-деревьев.

4. Kafka: распределённая система обмена сообщениями для обработки журналов (Kafka: a Distributed Messaging System for Log Processing)

Джей Крепс, Неха Нархеде, Джун Рао (Jay Kreps, Neha Narkhede, Jun Rao)

💡 Вы узнаете об обработке журналов, принципах проектирования, архитектуре и компонентах Kafka, включая производителей (producers), брокеров (brokers) и потребителей (consumers).

5. ZooKeeper: wait-free-координация для систем интернет-масштаба
(ZooKeeper: Wait-free coordination for Internet-scale systems)

Патрик Хант, Махадев Конар, Флавио П. Жункейра, Бенджамин Рид (Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, Benjamin Reed)

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

6. Квалифицированная электронная подпись (A Certified Digital Signature)

Ральф Ч. Меркл (Ralph C. Merkle)

💡 Вы узнаете об односторонних функциях, одноразовой подписи Лэмпорта — Диффи (Lamport-Diffie) и новой «древообразной подписи» (tree-signature), которую ещё называют деревом Меркла (Merkle tree).

7. Время, часы и порядок событий в распределённой системе
(Time, Clocks and the Ordering of Events in a Distributed System)

Лесли Лэмпорт (Leslie Lamport)

💡 Это самая цитируемая статья Лесли Лэмпорта (Leslie Lamport). Вы узнаете о логических часах и синхронизации в режиме реального времени. А также о таких концепциях, как «полное упорядочивание» (total ordering) и отношение happened-before aka happens-before («произошло раньше», «выполняется прежде»).

8. Урожай, урожайность и масштабируемые устойчивые системы
(Harvest, Yield, and Scalable Tolerant Systems)

Армандо Фокс, Эрик А. Брюэр (Armando Fox, Eric A. Brewer)

💡 Эта статья рассказывает о стратегиях повышения доступности систем, допускающих постепенную деградацию (graceful degradation).

9. Задача византийских генералов
(The Byzantine Generals Problem)

Лесли Лэмпорт, Роберт Шостак, Маршалл Пиз (Leslie Lamport, Robert Shostak, Marshall Pease)

💡 Вы узнаете о надёжности компьютерных систем в ситуациях, когда им приходится справляться с отказом одного или нескольких компонентов («предательством среди генералов». — Пер).

10. Линеаризуемость: условие правильности для параллельных объектов
(Linearizability: A Correctness Condition for Concurrent Objects)

Морис П. Херлихи, Жаннет М. Винг (Maurice P. Herlihy, Jeannette M. Wing)

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

11. Бесконфликтные реплицируемые типы данных (Conflict-free Replicated Data Types)

Нуну Прегиса, Карлос Бакеро, Марк Шапиро (Nuno Preguiça, Carlos Baquero, Marc Shapiro)

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

12. Реплицируемые типы данных с дельта-состоянием (Delta State Replicated Data Types)

Паулу Сержиу Алмейда, Али Шокер, Карлос Бакеро (Paulo Sérgio Almeida, Ali Shoker, Carlos Baquero)

💡 Вы узнаете о бесконфликтных реплицируемых типах данных на основе состояний (state-based CRDTs). И об их развитии — δ-CRDTs (CRDT c дельта-состояниями). Инкрементальные состояния (дельты) уменьшают объём данных, пересылаемых для поддержания согласованности распределённого объекта. То есть вместо всех (возможно, объёмных) данных состояния в δ-CRDTs при периодической синхронизации рассылаются только недавно внесённые изменения.

13. Создание надёжных распределённых систем при наличии программных ошибок (Making reliable distributed systems in the presence of software errors)

Джо Армстронг (Joe Armstrong)

💡 Вы узнаете об Erlang, параллельном программировании, передаче сообщений, отказоустойчивости и концепции «let it crash» («сломалось и ладно». — Пер.).

Хотите больше статей?

Мои любимки вы теперь знаете. Даже из них я наверняка вспомнил не все.

Вы всегда можете найти множество тщательно отобранных материалов на @papers_we_love, @intensivedata и @therealdatabass.