Хранение нажитого непосильным трудом — задача нетривиальная. Мало найти подходящее по объему место и загрузить его по самую маковку. Необходимо уметь отыскивать в накопленных данных нужное, причём чем быстрее, тем лучше.

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

Но как быть, если предметная область состоит из данных, которые нельзя структурировать традиционными способами? Поиск в интернете — одна из таких областей. Взрывной рост веба породил мириады байтов разнородной информации: веб-страницы, ссылки на них и фрагменты текста, которые они содержат, изображения, видео, музыка, записи в блогах, посты в социальных сетях и тонны комментариев к ним и к другим комментариям. Человечество с упоением бросилось заполнять хранилище под вывеской «Интернет».

Когда мы обращаемся к любому из многочисленных сервисов Google, чтобы найти или, наоборот, разместить в нем информацию, мы на самом деле делаем запрос к системам управления базами данных Google, которые называются Megastore и Spanner. Эти распределенные системы хранения, в отличие от традиционных реляционных СУБД, ориентированы на работу с полуструктурированными или же вовсе не структурированными данными.

Впрочем, эти распределенные базы данных появились не в одночасье. В основе мироздания хранилищ Google, как и полагается, лежало слово. И слово это — Bigtable.

Модель данных Bigtable

Создавая свой первый кластер, сотрудники Google задумывались над выбором подходящей СУБД. Являясь хоть и гигантской, но все же информационной системой, которая обслуживает запросы миллионов пользователей, система хранения данных Google должна была удовлетворять определённым требованиям к согласованности и доступности данных, будучи при этом способной к беспрецедентному масштабированию на сотни тысяч серверов.

Коммерческие распределённые СУБД заведомо превышали финансовые возможности Google. Одно дело приобрести лицензию для сотни–другой серверов в корпоративной сети, и совсем другое — для сотен тысяч, необходимых для индексирования всего интернета. При таких масштабах даже самая доступная цена вырастает до пугающей величины.

На первых порах в Google пытались обойтись MySQL — популярной СУБД с открытыми исходниками, которую можно устанавливать бесплатно. Эта идея быстро потерпела крах. Во-первых, MySQL не годилась для масштабирования с тем размахом, который требовался поисковику. Во-вторых, стало ясно, что традиционная реляционная модель данных плохо сочетается с полуструктурированным контентом.

Именно тогда инженеры Google и задали себе два вопроса. Первый: так ли нужен SQL? И второй: обязательно ли использовать готовое решение?

Всё свидетельствовало о том, что ответ на оба вопроса отрицательный. СУБД, которая была бы, с одной стороны, распределённой, масштабируемой и устойчивой к отказам серверов и сетевого оборудования, а с другой — имела бы модель данных, максимально удовлетворяющую потребностям Google, — такой СУБД не существовало. Её предстояло разработать с нуля.

В представленной в 2006 году коллективом разработчиков под руководством Джеффри Дина (Jeffrey Dean) распределенной системе хранения Bigtable было использовано смелое решение — методология NoSQL. Не отрицая достоинств реляционной модели данных, разработчики Bigtable посчитали, что в данном конкретном случае отказ от неё будет оправдан.

Но если не организация хранилища на основе отношения «сущность — связь», тогда что же? Как насчёт распределенной многомерной разреженной карты (distributed multi-dimensional sparse map)? Именно ею, в сущности, и является Bigtable.

Выбор подобной модели данных неслучаен. Предварительные исследования показали, что это оптимальная архитектура хранилища для большинства сервисов Google.

Основа модели данных Bigtable проста: строки (rows), столбцы (columns) и временные метки (timestamps). В базе поисковика именами строк могут служить адреса документов в интернете, а именами столбцов — особенности этих документов (например, содержание документа может храниться в столбце «content:», а ссылки на дочерние страницы — в столбцах «anchor:»). Другой пример — карты Google, состоящие из миллиардов изображений, каждое из которых детализирует тот или иной географический участок планеты. В Bigtable карты Google структурируются следующим образом: каждой строке соответствует один географический сегмент, а столбцами являются изображения, из которых этот сегмент состоит, прич`м в разных столбцах хранятся изображения с разной детализацией.

Пример модели хранения данных Bigtable для предметной области «Содержимое сайта»
Пример модели хранения данных Bigtable для предметной области «Содержимое сайта».

Если в нескольких столбцах хранятся данные одного типа, такие столбцы, согласно модели Bigtable, образуют семейство (column family). Использовать семейство столбцов удобно хотя бы для того, чтобы сжать однородные данные, тем самым уменьшив хранимый объём. Именно семейства столбцов являются единицей доступа к данным.

Строки Bigtable (их максимальная длина может достигать 64 килобайта) тоже важны. Операция обращения к строке является атомарной (это значит, что, пока одна программа обращается к строке, ни одна другая не имеет права изменять данные в семействах столбцов этой строки). А ещё строки удобно сортировать. В примере с URL документа, сделав его запись реверсивной, легко отсортировать все строки по имени домена третьего уровня.

Содержимое страниц в интернете постоянно меняется. Чтобы учесть эти изменения, каждой копии данных, хранящихся в столбце, присваивается временная метка (timestamp). В Bigtable временной меткой служит 64-разрядное число, которое может кодировать время и дату так, как это требуется клиентским программам. Например, timestamp для копий веб-страницы в столбце «contents:» является датой и временем создания этих копий. Используя временные метки, приложения могут задать в Bigtable поиск, например, только самых последних копий данных, информации, созданной за прошедшую неделю, или же данных, появившихся в момент с определённой датой и временем.

Итак, для предметной области любого сервиса Google можно создать собственную карту данных Bigtable, содержащую произвольное число строк и уникальный для этой предметной области набор семейств столбцов. Неизбежные повторы данных в столбцах упорядочиваются по временным меткам. Как видите, реляционной моделью здесь и не пахнет. Она и не нужна, если клиентским программам вручить набор API-функций, способных оперировать со строками, семействами столбцов и timestamps Bigtable.

Но главный плюс такого подхода состоит в том, что подобную базу не трудно порезать на независимые кусочки и распределить по множеству серверов. Отсортированные по алфавиту строки делятся на диапазоны, которые именуются «таблетами» (tablet) — несамостоятельными таблицами. Поскольку строки в каждом таблете отсортированы по ключевому имени, клиентским приложениям очень просто найти нужный таблет, а в нём – нужную строку.

Какой бы большой ни была исходная таблица Bigtable, ее всегда можно разделить на отдельные таблеты и раздать множеству обрабатывающих узлов.
Какой бы большой ни была исходная таблица Bigtable, её всегда можно разделить на отдельные таблеты и раздать множеству обрабатывающих узлов.

Процесс, обслуживающий таблеты, называется таблет-сервером. Для него не выделяют специальный компьютер. Таблет-сервер делит компьютерные ресурсы с исполнителями заданий системы MapReduce и драйвером файловой системы GFS. Страшного в этом ничего нет. На один таблет-сервер приходится не более тысячи таблетов величиной по 100–200 мегабайтов. Такие небольшие объёмы оправданы с точки зрения отказоустойчивости. В случае выхода из строя сервера системе управления Bigtable несложно найти таблет-серверы, которым можно перепоручить обработку таблетов «погибшего товарища».

Добиться консенсуса

Дирижирование согласованной работой множества таблет-серверов в архитектуре Bigtable берёт на себя Bigtable Master — процесс, выполняющийся на одном из серверов Google. Он отвечает за размещение таблетов на таблет-серверах, обнаружение, добавление или удаление таблет-серверов в уже существующей их инфраструктуре и балансировку их загрузки. Кроме того, Bigtable Master поддерживает схему изменений общей таблицы Bigtable — например, редактирование состава семейства столбцов или форматов timestamps.

Управление синхронизацией операций чтения/записи одних и тех же данных множеством клиентов не входит в задачу мастера Bigtable. Как же в таком случае быть с блокировкой доступа к строкам таблетов в том случае, если один из клиентов решит изменить в её семействах столбцов данные или же записать новые?

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

Bigtable — это чересчур большая и распределённая система для таких синхронизирующих объектов, поэтому вместо них применяется распределённый сервис блокировок (distributed lock service), который в Google именуют Chubby. Его роль в Bigtable можно сравнить с ролью транзакций в обычных СУБД.

 В кластере Bigtable два дирижёра - Bigtable Master и сервис блокировок Chubby. Первый отвечает за масштабируемость и отказоустойчивость, а второй за синхронизацию и учет данных.

В кластере Bigtable два дирижёра — Bigtable Master и сервис блокировок Chubby. Первый отвечает за масштабируемость и отказоустойчивость, а второй — за синхронизацию и учёт данных.

Для каждого таблет-сервера Chubby создает специальный chubby-файл. Благодаря этому файлу Bigtable Master всегда в курсе того, какие из серверов работоспособны. Ещё один chubby-файл содержит ссылку на расположение корневого таблета (Root-tablet) с данными о расположении всех остальных таблетов. Этот файл сообщает мастеру, какой из серверов какими таблетами управляет.

Безусловно, использование сервиса Chubby в Bigtable в какой-то мере решает задачу поддержания непротиворечивости данных в распределённой среде с множеством реплик. Но непротиворечивость бывает разной. Bigtable стала первой попыткой достичь баланса между производительностью системы, её масштабируемостью и непротиворечивостью хранящихся в ней данных. Результатом стала поддержка так называемой слабой непротиворечивости, которая, в принципе, удовлетворяла требованиям большинства работающих с Bigtable сервисов.

 Процесс взаимодействия всех компонентов Bigtable и используемые для этого информационные структуры.

Процесс взаимодействия всех компонентов Bigtable и используемые для этого информационные структуры.

Увы, слабая непротиворечивость подходит не всегда. Именно поэтому инженеры Google не покладая рук трудились над эволюционным развитием Bigtable. В результате их работы в 2011 году появилось распределённое хранилище Spanner — практически бескомпромиссное решение, вплотную приблизившееся к возможностям распределённых реляционных баз данных. Но рассказ о нём — совершенно отдельная история.