Код
#статьи

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

Участник проекта Papers We Love делится подборкой статей-любимок.

Polina Vari для Skillbox Media

Педру Тавареш

(Pedro Tavareλ)


об авторе

Программист из Порту (Португалия). Любит читать научные статьи. Открыл филиал проекта Papers We Love в Порту.


Ссылки


Перевод твита:

«Иногда меня спрашивают, какие статьи из области компьютерных наук стоит прочесть. Понятия не имею. Но могу назвать публикации, которые сам с удовольствием прочёл в последние годы».

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

Примечание переводчика:

Педру — участник проекта Papers We Love, глава филиала в Порту. Подробнее об этом проекте мы рассказывали здесь. И сам проект, и эта подборка статей отлично отвечают на вопрос, зачем программисту английский язык :)

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

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

Скриншот: M. Rosenblum et al. / University of California Berkeley, 1991 / Pedro Tavareλ

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

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

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

Скриншот: D. Comer / Purdue University, 1979 / Pedro Tavareλ

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

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

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

Скриншот: P. O’Neil et al. / Acta Informatica, 1996 / Pedro Tavareλ

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

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

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

Скриншот: J. Kreps et al. / LinkedIn Corp., 2011 / Pedro Tavareλ

💡 Вы узнаете об обработке журналов, принципах проектирования, архитектуре и компонентах 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)

Скриншот: P. Hunt et al. / Association for Computing Machinery, 2011 / Pedro Tavareλ

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

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

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

Скриншот: R. C. Merkle / BNR Inc., 1979 / Pedro Tavareλ

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

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

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

Скриншот: L. Lamport / Massachusetts Computer Associates, Inc., 1978 / Pedro Tavareλ

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

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

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

Скриншот: A. Fox et al. / Stanford University, 1999 / Pedro Tavareλ

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

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

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

Скриншот: L. Lamport et al. / SRI International, 1982 / Pedro Tavareλ

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

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

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

Скриншот: M. P. Herlihy et al. / Carnegie Mellon University, 1987 / Pedro Tavareλ

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

Примечание переводчика:

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

Источник

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

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

Скриншот: N. Preguiça et al. / Springer International Publishing, 2018 / Pedro Tavareλ

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

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

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

Скриншот: P. S. Almeida et al. / Journal of Parallel and Distributed Computing, 2018 / Pedro Tavareλ

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

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

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

Скриншот: J. Armstrong / Printed by Universitetsservice, 2003 / Pedro Tavareλ

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

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

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

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



Научитесь: Профессия Data Engineer Узнать больше
Понравилась статья?
Да

Пользуясь нашим сайтом, вы соглашаетесь с тем, что мы используем cookies 🍪

Ссылка скопирована