Spanner. NewSQL хранилище от Google

    Spannerгеографически распределенная высокомасштабируемая мультиверсионная база данных с поддержкой распределенных транзакций. Хранилище было разработана инженерами Google для внутренних сервисов корпорации. Research paper [8], описывающий базовые принципы и архитектуру Spanner, был представлен на научной конференции 10th USENIX Symposium on Operating Systems Design and Implementation в 2012 году.

    Spanner является эволюционным развитием NoSQL-предшественника – Google Bigtable. Сам же c Spanner относят к семейству NewSQL-решений. В research paper [8] заявляется, что дизайн Spanner позволяет системе масштабироваться на миллионы вычислительных узлов через сотни дата-центров и работать с триллионами строк данных.



    Spanner использует Colossus (GFS нового поколения) как слой хранения (storage) и алгоритм разрешения коллизий Paxos. В свою очередь на основе (on top) Spanner построена распределенная СУБД Google F1.

    Spanner используется в социальной сети Google+, в почтовом сервисе GMail. Построенная на основе Spanner СУБД Google F1 использовалась на момент публикации [8] в сервисе Google Ad Service.

    Базовые принципы


    Данные в Spanner хранятся в полуреляционных таблицах, имеющих схему. Все данные имеют версию – временную метку (timestamp) подтверждения записи этих данных (commit). Spanner имеет SQL-подобный язык запросов, возможность конфигурировать количество реплик и политики Garbage Collector, ответственного за удаление записей со «старыми» временными метками.

    Кроме уже «привычных» для NoSQL-мира возможностей, Spanner обладает и рядом сложно реализуемых в распределенных системах свойств. Таких как:
    • поддержка распределенных транзакций;
    • глобальная согласованность операций чтения между географически распределенными ДЦ, т.о. данные, которые возвращают операции чтения из разных ДЦ, всегда согласованны и непротиворечивы.

    Кроме того Spanner обладает возможностями, больше свойственными для СУБД, такими как:
    • неблокирующее чтение данных «из прошлого» (in past);
    • отсутствие блокировок для read-only транзакций;
    • атомарное изменение схемы таблиц данных;
    • синхронная репликация;
    • автоматическая обработка отказов как вычислительных узлов, так и ДЦ;
    • автоматическая миграция данных как между вычислительными узлами, так и между ДЦ.

    Архитектура


    Каждый развернутый экземпляр (deployment) Spanner именуется Universe и содержит в себе:
    • Universe master – мастер-процесс, координирующий работу множества зон (в терминологии Spanner — Zone);
    • Множество Zone – географически распределенные (в общем случае) зоны Spanner. Zone – это единица как логической изоляции, так и физической.

    Каждый из Zone, в свою очередь, содержит в себе:
    • ZoneMaster – мастер-процесс зоны (синглтон);
    • Множество — от сотни до нескольких тысяч — Spanservers;
    • Location proxy – раскрывают клиентам расположение Spanservers, ответственных за необходимые данные;
    • Placement driver – процесс (также, как и Zonemaster, синглтон), управляющий перемещением данных между различными Zone.

    Spanner Arhitecture

    В research paper [8] подробно описаны функции и внутренне устройство только Spanserver.

    Каждый Spanserver содержит в себе от 100 до 1000 структур данных называемых tablet.

    (key: string, timestamp: int64) -> string


    В отличии от Bigtable, Spanner добавляет к структуре хранимых данных метку времени добавления этих данных, что является важным введением для реализации поддержки мульти-версионности данных.

    Модель данных в Spanner – полуреляционные таблицы с поддержкой схем данных (schematized), SQL-подобного языка запросов и распределенных транзакций.

    Реализация последних (транзакций) стала возможна благодаря одному из наиболее инновационных нововведений для такого рода программных систем – программного интерфейса TrueTime API.

    TrueTime


    Обычная задача для систем предоставления глобального времени (в частности атомных часов) – это предоставление максимально точного времени. TrueTime API же предоставляет клиентам глобальное время + некоторую неопределенность – TTinterval.

    Это нужно потому, что для распределенных систем очень сложно гарантировать мгновенность отклика узлов, что важно для обеспечения согласованности данных в распределенном хранилище.

    При подходе, когда вместо точного времени, возвращается некоторых временной интервал выполнение 2-ух конкурентных транзакций сводится (упрощенно) к сравнению TTinterval этих транзакций. Если TTinterval транзакций не пересекается, то можно однозначно узнать, какая из транзакций должна быть выполнена раньше. Если TTinterval – пересекается, то сказать можно только с определенной степенью вероятности. (Подробнее о аппаратной части сервиса TrueTime.)

    В самом же Spanner согласованность данных при проведении транзакций обеспечивается протоколом двухфазной фиксации транзакции (2-Phase Commit Protocol), реализованным с помощью алгоритма Paxos.

    Ограничения и CAP


    На момент публикации research paper [8] Spanner не поддерживал вторичные индексы и автоматический resharding для целей балансировки нагрузки. Кроме того, авторы [8] отмечают, что Spanner не способен эффективно исполнять сложные SQL-запросы.

    Spanner также не является «опровержением» CAP-теоремы. Spanner не является AP-системой, несмотря на свою NoSQL-природу; как и не является CA-системой, несмотря на поддержку стремление поддержки принципов ACID. Spanner «жертвует» доступностью (availability) для поддержания целостности данных (consistency) и поэтому является CP-системой.

    Итоги


    Spanner взял лучшие идеи двух миров — реляционных СУБД и NoSQL – и представляет из себя СУБД поколения NewSQL.

    Поддержка распределенных транзакций между дата-центрами на объеме данных, идущим на петабайты, с такой способностью к масштабированию – безусловно крайне впечатляющее свойство для любой системы хранения структурированных и полуструктурированных данных. Данная возможность во многом стала следствием симбиоза двух подходов: подхода к хранению данных – данные иммутабельны и содержат метку времени коммита – и инновационной концепции получения глобального времени – TrueTime.

    Список источников*


    [8] James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman, et al. Spanner: Google’s Globally-Distributed Database. Proceedings of OSDI, 2012.
    * Полный список источников, используемый для подготовки цикла.


    Дмитрий Петухов,
    MCP, PhD Student, IT-зомби,
    человек с кофеином вместо эритроцитов.
    Метки:
    Поделиться публикацией
    Комментарии 11
    • +1
      Было бы интересно что-то услышать о F1, который построен поверх Spanner (http://www.systemswemake.com/paper/f1)
      • 0
        Вот две официальные публикации о F1 от Google: раз и два
      • +1
        Т.е. получается, что не успели люди начать пользоваться NoSQL, уже появилась новая тенденция — попытка совместить быстроту и масштабируемость NoSQL и привычный всем SQL. Мне кажется такими темпами скоро программисты будут ходить к отдельному человеку, который разбирается во всех этих типах баз данных, API, встроенных языках и т.п. Раньше вот как хорошо было: MySQL, PostgreSQL, MSSQL, Firebird, Oracle, SQLite более менее знаешь и этого достаточно, чтобы написать любое приложение. А теперь кроме этих наиболее известных SQL движков еще штук 30 новых. ДУмаю лет через 10 две трети умрет и будет нам опять нирвана.
        • +1
          <кэп модэ>
          Если «тогда» «программист» было более-менее определенное понятие и должность, то сейчас всё уходит в узкую специализацию по зоопаркам технологий и подходов
          </кэп модэ>
          Это как совсем давно. Мужик? — Вот тебе дубина, вон там стоИт мамонт. Пойди убей его и съешь.
          Ну, понятно, надеюсь.
          • +1
            Дык, каждой задаче — свое решение. Polyglot Persistence и все такое. У нас уже есть люди, которые специализируются либо только на реляционных базах, либо только на NoSql. Дяди разные нужны, дяди разные важны :) Вот, кстати, дяденька Фаулер еще давно завещал www.martinfowler.com/bliki/PolyglotPersistence.html
          • 0
            автоматическая обработка отказов как вычислительных узлов, так и ДЦ;
            автоматическая миграция данных как между вычислительными узлами, так и между ДЦ.

            Мне казалось это как раз таки чаще свойства NoSQL, чем традиционных СУБД.

            В самом же Spanner согласованность данных при проведении транзакций обеспечивается протоколом двухфазной фиксации транзакции (2-Phase Commit Protocol), реализованным с помощью алгоритма Paxos.

            Это неверно. Paxos и 2PC используются независимо и для разного. Вообще вопрос организации tablets в группы вы как-то опустили. Paxos используется для репликации внутри группы (реплицируются одни и те же данные, в том числе между ДЦ), двухфазный коммит и двухфазные блокировки используются для организации транзакций, оперирующих с данными из нескольких tablet. Кроме этого рискну предположить, что всевозможные мастера используют Chubby и, как следствие, тоже Paxos.

            Ещё хотел бы добавить, что ваш цикл совсем обходит стороной Megastore и Chubby, хотя второй послужил прототипом Zookeeper.
            • 0
              Рискуя комментарием на грани фола, замечу что Megastore это немного тупиковая другая ветвь эволюции, и в инфраструктуре CFS/Spanner/F1 он вообще не участвует. Chubby здесь конечно же используется, в том же ключе как он используется и в любом другом продукте Google — distributed lock service.
              • 0
                Да, про chubby интересно было бы почитать.
                • 0
                  www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf

                  К сожалению на самом интересном месте:

                  While group membership with the core Paxos algorithm is straightforward, the exact details are non-trivial when we introduce Multi-Paxos, disk corruptions, etc. Unfortunately the literature does not spell this out, nor does it contain a proof of correctness for algorithms related to group membership changes using Paxos. We had to fill in these gaps to make group membership work in our system. The details – though relatively minor – are subtle and beyond the scope of this paper.
                  So trololo :(
              • –1
                Кольцо Всевластия :)
                • 0
                  В отличии от Bigtable, Spanner добавляет к структуре хранимых данных метку времени добавления этих данных, что является важным введением для реализации поддержки мульти-версионности данных.
                  Эмнэээ… Но ведь Bigtable тоже поддерживает метку времени. Bigtable
                  A NoSQL massively parallel table
                  .
                  Each column family cell can contain multiple versions of content. For example, in the earlier example, we may have several timestamped versions of page contents associated with a URL. Each version is identified by a 64-bit timestamp that either represents real time or is a value assigned by the client. Reading column data retrieves the most recent version if no timestamp is specified or the latest version that is earlier than a specified timestamp. timestamp.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.