Публикации на Google Research

Последние пару дней я активно готовился к своему докладу про RnD и изучал страничку research.google/pubs/, чтобы посмотреть какие white papers появлялись у Google и когда.
В итоге, я составил список ключевых документов с фокусом на сервисы и инфраструктур (исключая ML), которым решил поделиться

- 2003 год - The Google File System - про распределенную файловую систему от Google
- 2004 года - MapReduce: Simplified Data Processing on Large Clusters - про концепцию параллельной обработки в формате MapReduce (по мотивам появился Hadoop)
- 2006 год - Bigtable: A Distributed Storage System for Structured Data - про распределенную NoSQL базу (по мотивам BigTable и Amazon DynamoDB появилась Cassandra)
- 2006 - The Chubby lock service for loosely-coupled distributed systems - про сервис распределенных локов, которые можно использовать вместо встраивания консесуса в сами сервисы
- 2007 - Engineering Reliability into Web Sites: Google SRE - про роль SRE в обеспечении надежности
- 2010 - Dapper, a Large-Scale Distributed Systems Tracing Infrastructure - про трассировку в распределенных системах (open source последователи Zipkin, Jaeger, OpenTelemetry)
- 2012 - Spanner: Google's Globally-Distributed Database - про NewSQL базу данных с масштабированием как у NoSQL и ACID транзакциями, под капотом TrueTime для точного определения времени, что нужно для определения порядка транзакций (open source последователи Cockroach DB)
- 2013 - Omega: flexible, scalable schedulers for large compute clusters - про окрестратор рабочих нагрузок (наследник Borg, но менее удачный)
- 2015 - Large-scale cluster management at Google with Borg - про оркестратор рабочих нагрузок, что предшествовал Omega и в итоге оказался более удачным и пережил ее
- 2015 - TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems - про фреймворк для машинного обучения, который сразу был выпущен в open source
- 2016 - Borg, Omega, and Kubernetes - про сравнение двух внутренних и одного публичного (K8s) оркестратора нагрузок (Kubernetes изначально тоже сделал Google)
- 2016 - Ubiq: A Scalable and Fault-tolerant Log Processing Infrastructure - про обработку логов на масштабе
- 2017 - Spanner, TrueTime and the CAP Theorem - про CAP теорему и Spanner от создателя CAP-теоремы, Eric Brewer, что к этому моменту уже давно работал в Google
- 2018 - Advantages and disadvantages of a monolithic repository: a case study at google - про монорепозиторий Google и как он помогает им в разработке
- 2019 - Zanzibar: Google’s Consistent, Global Authorization System - про ReBAC систему авторизации, что завязана на отношения между сущностями (мы этот white paper как-то уже обсуждали в Code of Architecture)
- 2020 - Monarch: Google's Planet-Scale In-Memory Time Series Database - про time-series базу данных
- 2020 - Scaling PageRank to 100 Billion Pages - про масштабирование ключевого алгоритма на графах (Page Rank) на супер масштабы
- 2020 - Autopilot: Workload Autoscaling at Google Scale - про автомасштабирование рабочих нагрузок в облаках
- 2022 - Deployment Archetypes for Cloud Applications - интересное исследование про виды deployments
- 2023 - A Model-based, Quality Attribute-guided Architecture Re-Design Process at Google - интересный документ про архитектурные процессы в Google на примере репроектирования системы Monarch, про которую был white paper от 2020 года

Если суммировать мои мысли про Google и создание ими статей, то видно, что они первыми писали про многие сложные штуки, но вот open source решений поначалу они не создавали, и у них появлялись open source аналоги. И эти аналоги были несовместимы с внутренними инструментами Google, что мешало получать помощь от коммьюнити. Значимыми исключениями с точки зрения открытости являются: Android, Chrome, Kubernetes, TensorFlow.

#RnD #WhitePaper #Software #SoftwareDevelopment #Architecture #SoftwareArchitecture #DistributedSystems #SystemDesign #SystemEngineering

CAP Theorem

Знаменитой CAP теореме исполнилось 25 лет, поэтому хотелось что это такое, зачем она и как появилась. Про это есть отличная статья от Eric Brewer, автора теоремы, который написал ее больше 10 лет назад, которую хотелось вспомнить, так как она хороша:)
Начнем с самого утверждения теоремы (цитата из статьи выше)

The CAP theorem states that any networked shared-data system can have at most two of three desirable properties:
- consistency (C) equivalent to having a single up-to-date copy of the data;
- high availability (A) of that data (for updates); and
- tolerance to network partitions (P).

Дальше надо вспомнить про ее появление
- 25 лет назад, осенью 1998 года была сформулирована CAP теорема
- в 1999 году она была опубликована в статье "Harvest, Yield, and Scalable Tolerant Systems" в ACM
- в 2000 представлена на Симпоузиуме "Symposium on Principles of Distributed Computing" (презентация здесь)
- в 2002 доказана формально (где консистентность из теоремы превратилась в линеаризуемость)
Потом теорема пошла в массы и превратилась в условные "выберите 2 свойства из трех: C, A, P", что является сильным упрощением по трем причинам, что указывает Эрик в уже упоминавшейся статье:
1. Из-за редкости partition нет смысла выбирать между C и A (про это подробнее в следующий раз при обсуждении PACELC Theorem)
2. Решение о C или A принимается не единоразово для всех компонентов и всех данных, а на другом уровне гранулярности и может зависеть от типа операции или данных
3. C, A, P - это не бинарные свойства, а скорее непрерывные - availability от 0 до 100%, уровни консистентности тоже бывают разные и даже partitions имеют нюансы:)

В итоге, Эрик говорит о том, что в отсутствии разделения системы мы можем выбирать A или C, а во время проблем у нас должен быть понятный алгоритм
- определения, что случился partition
- перехода в явный partition режим, в котором часть операций может быть лимитирована
- запуска процесса восстановления консистентности и компенсации ошибок, что возможно были в рамках partition

Потом Эрик рассказывает про связь акронимов ACID, BASE и CAP
- BASE расшифровывается как Basic Availability, Soft state и Eventually consistency. Первые два из свойств помогают достигать доступности при разделении системы на части
- ACID расшифровывается как Atomicity, Consistency, Isolation, Durability. Этот акроним знают многие, кто работал с реляционными базами данных, но как я писал выше Consistency из CAP и из ACID - это про разное и это добавляет сложности в понимании:)

Следом идет часть про latency, которая отсутствует в классической формулировке, но неявно присутствует. Ведь выполняя операцию в разделенной системе, мы в какой-то момент должны принять решение
- отменить операцию и уменьшить доступность
- продолжить операцию, но принять риск неконсистентности данных

Конечно можно попробовать повторно выполнить операцию (retries), но это просто откладывает принятие решение на некоторое время. Таким образом, с прагматической точки зрения разделение — это ограничение по времени (таймаут), который мы закладываем в свое общение. А из этого следует несколько последствий
1. Не существует глобального понятия partition, поскольку некоторые узлы могут обнаружить partition, а другие — нет.
2. Те узлы, что обнаружили partition входят в режим partition-mode, собственно ту часть, где нам надо выбирать между C и A
В итоге, проектировщики системы выставляют time bounds так, чтобы соответствовать целевым скоростям ответа системы на запросы, а чем жестче эти time bounds, тем выше вероятность попадания в partition mode, причем даже просто при медленной сети, но без реального ее разделения.

В приведенной выше статье есть еще много интересных мыслей про scope консистентности и как это соотносится с датацентрами, как явно управлять процессами перехода в partition mode и восстанавливаться после partition. Очень рекомендую ее к прочтению.

#Software #Architecture #DistributedSystems #SystemDesign

What Goes Around Comes Around... And Around... Part I (Рубрика #Data)

Интересная обзорная статья 2024 года от Michael Stonebraker и Andrew Pavlo про развитие баз данных за последние 20 лет. Оба автора являются корефееями в области баз данных: Michael создал Postgres и еще кучу других баз, а Andrew - исследователь в области баз данных, профессор и преподаватель, лекции которого доступны на Youtube.

Сама статья продолжает статью 2005 года "What Goes Around Comes Around", которую написали Michael Stonebraker и Joseph M. Hellerstein. Они проанализировали историю развития баз данных за 35 лет и предсказали что модные тогда объектные и xml базы данных не смогут обойти по реляционную модель.

С тех пор прошло порядка 20 лет и пришло время сделать новый обзор мира баз данных. Для этого авторы решили посмотреть на это с двух сторон:
- Модели данных и языки запросов
- Архитектура баз данных

Начнем с разбора существующих data models и query languages:

1. MapReduce-системы
Изначально они были разработаны в Google для обработки больших объемов данных (веб-краулер). MapReduce не использует фиксированную модель данных или язык запросов, они выполняют пользовательские операции map и reduce. Открытой версией MapReduce стал Hadoop, который сейчас не очень популярен из-за низкой производительности и заменяется более современными платформами аля Apache Spark или просто СУБД.

2. Key-Value хранилища
У них максимально простая модель данных: пары "ключ-значение". Они используются для задач кэширования (Memcached, Redis) или хранения сессий. Возможности в модели ограничены - нет индексов или операций join, что усложняет применение для сложных приложений. Многие KV-хранилища (например, DynamoDB, Aerospike) эволюционировали в более функциональные системы с поддержкой частичной структуры (JSON). Среди популярных встроенных k/v решений популярны LevelDB и RocksDB.

3. Документные базы данных
Они хранят данные в виде документов (например, в формате JSON). Изначально получили популярность благодаря простоте интеграции с веб-приложениями (например, MongoDB), предлагая подход schema on read. Интресно, что к 2020-м годам большинство документных СУБД добавили SQL-подобные интерфейсы и поддержку ACID-транзакций, а иногда и schema on write.

4. Column-Family базы данных (wide columns)
По-факту, это упрощенная версия документной модели с ограниченной вложенностью. Начиналось все с Google BigTable, а в миру есть open source реализация в виде Apache Cassandra. Изначально в Cassandra не было вторичных индексов и транзакций. Но по мере развития они появились (но там все очень интересно)

5. Поисковые движки
Они нужны для полнотекстового поиска (Elasticsearch, Apache Solr). Поддерживают индексацию текста, но ограничены в транзакционных возможностях. Реляционные СУБД также предлагают встроенный полнотекстовый поиск, но с менее удобным API.

6. Базы данных для массивов
Они предназначены для работы с многомерными массивами, например, научные данные (SciDB, Rasdaman). Ниша ограничена специфическими областями применения: геоданные, изучение генома.

7. Векторные базы данных
Используются для хранения эмбеддингов из машинного обучения (Pinecone, Milvus). Основное применение — поиск ближайших соседей в высокоразмерных пространствах. Реляционные СУБД уже начали добавлять поддержку векторных индексов.

8. Графовые базы данных
Моделируют данные как графы (узлы и связи). Примеры: Neo4j для OLTP-графов, TigerGraph для аналитики. Большинство графовых задач можно реализовать на реляционных СУБД с помощью SQL/PGQ (новый стандарт SQL:2023).

Общие выводы
- Большинство нереляционных систем либо занимают нишевые рынки, либо постепенно сближаются с реляционными СУБД.
- SQL остается основным языком запросов благодаря своей гибкости и поддержке современных приложений.
- Реляционные СУБД продолжают развиваться и интегрировать новые возможности (например, JSON, векторные индексы), что делает специализированные системы менее конкурентоспособными.

В продолжении поста будет про архитектуру баз данных.

#Data #Architecture #Software #DistributedSystems