読者です 読者をやめる 読者になる 読者になる

451 Unavailable For Legal Reasons

とあるゲームエンジニアのブログです

C#縛りでLT大会 & Meetup#2 でLTしてきた

イベントページ

forkwell.connpass.com

BTC FX 自動トレードのススメ

doc.co

参照戻り値とUnsafeクラス C#7.0とパフォーマンス

doc.co

bitFlyer萬藤氏の資料は見つかり次第

総括

LT後の質問がたくさん出てきたのでソフトウェアトレードに興味は持って頂けたかなと(興味持ってもらっても特に得はしない)。

Visual Studio 2017 リリース記念勉強会に行ってきた

csugjp.connpass.com

C# 7

docs.com


ASP‌.NET Core 概要

docs.com


C# でブロックチェーン実装

www.slideshare.net


AWS Loves .NET: または私は如何に心配するのをやめて Mac を愛するようになったか

docs.com


Developing and Deploying .NET Core on Linux

docs.com


Visual Studio 2017 の新機能

docs.com

感想

ライブデモが多い、濃い内容でした。

GoogleのSpannerに関する論文の和訳 3/6

blog.game-programmer.jp

上の記事の続きです。

3.TRUETIME

This section describes the TrueTime API and sketches its implementation. We leave most of the details for another article: our goal is to demonstrate the power of having such an API. Table I lists the methods of the API. TrueTime explicitly represents time as a TTinterval, which is an interval with bounded time uncertainty (unlike standard time interfaces that give clients no notion of uncertainty). The endpoints of a TTinterval are of type TTstamp. The TT.now() method returns a TTinterval that is guaranteed to contain the absolute time during which TT.now() was invoked. The time epoch is analogous to UNIX time with leap-second smearing. Define the instantaneous error bound as ε, which is half of the interval’s width, and the average error bound as Ɛ̄. The TT.after() and TT.before() methods are convenience wrappers around TT.now().

3. TRUETIME

このセクションでは、TrueTimeAPIについて、その実装の概略を説明します。この論文での目標は、このAPIがどれほど大きな影響力を持つかを示すことに注力し、詳細の説明は別の論文へ残しておきます。表Iに、APIのメソッドを示します。TrueTimeは時刻をTTintervalで表します。TTintervalは不確実性を伴う時刻の区間です(クライアントに不確実性の概念を与えない時刻を返す従来のインタフェースとは異なります)。TTintervalの区間の両端は、TTstampという型です。TT.now()メソッドは、TT.now()が呼び出された絶対時刻を含むことが保証されたTTintervalを返します。この時刻は、Leap Smearを有効にしたUNIXタイムに似ています。瞬間的なエラー範囲をεと定義(TTintervalの半分)し、平均エラー範囲をƐ̄と定義します。TT.after() と TT.before() メソッドは TT.now() メソッドのラッパーユーティリティです。

f:id:master-0717:20170303155940p:plain

Denote the absolute time of an event e by the function tabs(e). In more formal terms,TrueTime guarantees that for an invocation tt = TT.now(), tt.earliest ≤ tabs(enow) ≤tt.latest, where enow is the invocation event.

f:id:master-0717:20170303162922p:plain

関数t-abs(e)によってイベントeの絶対時刻を示します。 より正式な言い方をすれば、TrueTimeはtt = TT.now(), tt.earliest ≤ t-abs(e-now) ≤ tt.latest,を保証します。ここで、e-nowは呼び出しイベントです。

The underlying time references used by TrueTime are GPS and atomic clocks. True-Time uses two forms of time reference because they have different failure modes. GPS reference-source vulnerabilities include antenna and receiver failures, local radio interference, correlated failures (e.g., design faults such as incorrect leap-second handling and spoofing), and GPS system outages. Atomic clocks can fail in ways uncorrelated to GPS and each other, and over long periods of time can drift significantly due to frequency error.

TrueTimeによって参照される時計はGPS時計と原子時計です。それぞれ異なる脆弱性を持つため、2つの形式の時計を参照します。GPS時計の脆弱性は、アンテナと受信機障害、ローカル無線干渉、相関障害(不適切なうるう秒のハンドリングやスプーフィングなどの設計上の障害)、そしてGPSシステムの停止です。原子時計は、GPS時計と無相関な原因で障害が発生する可能性があり、周波数エラーにより長い時間をかけて著しく時刻がずれる可能性があります。

TrueTime is implemented by a set of time master machines per datacenter and a timeslave daemon per machine. The majority of masters have GPS receivers with dedicated antennas; these masters are separated physically to reduce the effects of antenna failures, radio interference, and spoofing. The remaining masters (which we refer to as Armageddon masters) are equipped with atomic clocks. An atomic clock is not that expensive: the cost of an Armageddon master is of the same order as that of a GPS master. All masters’ time references are regularly compared against each other. Each master also cross-checks the rate at which its reference advances time against its own local clock, and evicts itself if there is substantial divergence. Between synchronizations, Armageddon masters advertise a slowly increasing time uncertainty that is derived from conservatively applied worst-case clock drift. GPS masters advertise uncertainty that is typically close to zero.

TrueTimeは、データセンターごとに1組のタイム・マスターマシンのセットと、マシンごとに1つのタイム・スレイブ・デーモンによって実装されています。大部分のマスターは、専用アンテナを備えたGPS受信機を持っています。これらのマスターは、アンテナ障害、電波干渉、およびスプーフィングの影響を軽減するために物理的に分離されています。残りのマスター(我々はそれをアルマゲドン・マスターと呼んでいます)には原子時計が装備されています。原子時計はそれほど高価ではなく、アルマゲドン・マスターのコストは、GPSマスターのコストと同じオーダーです。すべてのマスターが参照する時計は、互いに定期的に比較されます。また、各マスターは、ローカル時計を基準に時刻の進む速度をクロスチェックし、明らかなずれがあった場合は自身で離脱します。同期している間に、アルマゲドン・マスターは不確実性(保守的に見積もられた最大の時刻のずれ幅)の緩やかな増加を示します。GPSマスタは、通常ゼロに近い不確定性を示します。

Every daemon polls a variety of masters [Mills 1981] to reduce vulnerability to errors from any one master. Some are GPS masters chosen from nearby datacenters; the rest are GPS masters from farther datacenters, as well as some Armageddon masters. Daemons apply a variant of Marzullo’s algorithm [Marzullo and Owicki 1983] to detect and reject liars, and synchronize the local machine clocks to the non-liars. To protect against broken local clocks, machines that exhibit frequency excursions larger than the worst-case bound derived from component specifications and operating environment are evicted. Correctness depends on ensuring that the worst-case bound is enforced.

すべてのデーモンは、個々のマスターのエラーによる影響を軽減するために、さまざまなマスターをポーリングします[Mills 1981]。いくつかは近くのデータセンターから選ばれたGPSマスター、残りは遠方のデータセンタから選ばれたGPSマスターと、いくつかのアルマゲドン・マスターです。デーモンは、Marzulloアルゴリズム[Marzullo and Owicki 1983]の改変を使用して、嘘つきを検出・除去し、ローカルマシンの時計を嘘つき以外に同期させます。故障したローカル時計から保護するために、コンポーネント仕様および動作環境から導出された最悪の場合のしきい値よりも大きなずれの頻度を検出したマシンは除去されます。最悪の場合のしきい値が強制されることを保証することで、正確さを維持しています。

Between synchronizations, a daemon advertises a slowly increasing time uncertainty. ε is derived from conservatively applied worst-case local clock drift. ε also depends on time-master uncertainty and communication delay to the time masters. In our production environment, ε is typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval. Ɛ̄ is therefore 4 ms most of the time. The daemon’s poll interval is currently 30 seconds, and the current applied drift rate is set at 200 microseconds/second, which together account for the sawtooth bounds from 0 to 6 ms. The remaining 1 ms comes from the communication delay to the time masters. Excursions from this sawtooth are possible in the presence of failures. For example, occasional time-master unavailability can cause datacenter-wide increases in error. Similarly, overloaded machines and network links can result in occasional localized error spikes. Correctness is not affected by ε variance because Spanner can wait out the uncertainty, but performance can degrade if ε increases too much.

同期している間に、デーモンはゆっくりと時刻の不確定性の増加を示します。εは、保守的に見積もった最悪の場合のローカル時計のずれから導き出されます。εは、時間マスターの不確実性および時間マスターに対する通信遅延にも依存します。我々のプロダクション環境では、εは通常、時刻の鋸歯状波関数であり、各ポーリング間隔にわたって約1~7ミリ秒の間で変化します。したがって、Ɛ̄はほとんどの場合4msです。デーモンのポーリング間隔は現在30秒であり、現在ずれ率は200マイクロ秒/秒に設定されており、それは0〜6ミリ秒の鋸歯境界の要因です。残りの1msは、時間マスターへの通信遅延に由来します。障害の存在下でのみ、この鋸歯境界から逸脱する可能性があります。たとえば、タイムマスターが使用できないことがあると、データセンター全体でエラーが増加する可能性があります。同様に、オーバーロードされたマシンやネットワークリンクは、局所的にエラーを引き起こす可能性があります。Spannerは不確実性の間、処理を待機することができるため、εの変化によって正確性は影響を受けませんが、εが増えすぎるとパフォーマンスが低下する可能性があります。

GoogleのSpannerに関する論文の和訳 2/6

blog.game-programmer.jp

上の記事の続きです。

2.IMPLEMENTATION

This section describes the structure of and rationale underlying Spanner’s implementation. It then describes the directory abstraction, which is used to manage replication and locality, and is the unit of data movement. Finally, it describes our data model, why Spanner looks like a relational database instead of a key-value store, and how applications can control data locality.

2. 実装

このセクションでは、Spannerの実装と設計の根拠について説明します。 次に、レプリケーションとロケーション管理に使用され、データ移動の単位でもあるディレクトリ抽象化について説明します。 最後に、データモデル、なぜSpannerがキーバリューストアではなくリレーショナルデータベースのように見えるのか、そしてアプリケーションがデータのロケーションをどのように制御できるのかについて説明します。

A Spanner deployment is called a universe. Given that Spanner manages data globally, there will be only a handful of running universes. We currently run a test/playground universe, a development/production universe, and a production-only universe.

Spannerのデプロイメントはユニバースと呼ばれます。 Spannerがデータをグローバル規模で管理していることを考えると、実行中のユニバース数はごく少ないものになります。 我々は現在、test/playground、development/production、production-onlyの3つのユニバースを運用しています。

Spanner is organized as a set of zones, where each zone is the rough analog of a deployment of Bigtable servers [Chang et al. 2008]. Zones are the unit of administrative deployment. The set of zones is also the set of locations across which data can be replicated. Zones can be added to or removed from a running system as new datacenters are brought into service and old ones are turned off, respectively. Zones are also the unit of physical isolation: there may be one or more zones in a datacenter, for example, if different applications’ data must be partitioned across different sets of servers in the same datacenter.

Spannerはゾーンのセットとして編成されています。各ゾーンはBigtableに似ています[Chang et al. 2008]。 ゾーンはデプロイメントの管理単位です。 ゾーンのセットは、データをレプリケーションできるロケーションのセットでもあります。 データセンターの新規稼働や停止に応じて、実行中のシステムにゾーンを追加したり削除したりすることができます。 ゾーンは物理的な分離単位でもあります。例えば、異なるアプリケーションのデータを同じデータセンターの異なるサーバー群に格納する必要がある場合は、データセンターには複数のゾーンが存在することがあります。

Figure 1 illustrates the servers in a Spanner universe. A zone has one zonemaster and between one hundred and several thousand spanservers. The former assigns data to spanservers; the latter serve data to clients. The per-zone location proxies are used by clients to locate the spanservers assigned to serve their data. The universe master and the placement driver are currently singletons. The universe master is primarily a console that displays status information about all the zones for interactive debugging. The placement driver handles automated movement of data across zones on the timescale of minutes. The placement driver periodically communicates with the spanservers to find data that needs to be moved, either to meet updated replication constraints or to balance load. For space reasons, we will only describe the spanserver in any detail.

図1は、ユニバース内のサーバーを示しています。 ゾーンには1つのゾーンマスターと百から数千のスパンサーバーがあります。 ゾーンマスターはデータをスパンサーバーに割り当てます。 スパンサーバーはクライアントにデータを提供します。 ゾーンごとのロケーションプロキシは、クライアントが割り当てられたスパンサーバーを見つけるために使用されます。 ユニバースマスターとプレイスメントドライバは現在シングルトンです。 ユニバースマスターは、主にゾーンに関するインタラクティブなデバッグ用途のステータス情報を表示するコンソールです。 プレイスメントドライバは、数分の時間規模でのゾーン間データ移動を処理します。 プレイスメントドライバはスパンサーバーと定期的に通信して、更新時のレプリケーション制約を満たすために、または負荷のバランスをとるために、移動する必要のあるデータを検索します。 スペース上の理由から、スパンサーバーについてのみ詳細に説明します。

f:id:master-0717:20170301123928p:plain

2.1. Spanserver Software Stack

This section focuses on the spanserver implementation to illustrate how replication and distributed transactions have been layered onto our Bigtable-based implementation. The software stack is shown in Figure 2. At the bottom, each spanserver is responsible for between 100 and 1000 instances of a data structure called a tablet. A tablet is similar to Bigtable’s tablet abstraction, in that it implements a bag of the following mappings.

(key:string, timestamp:int64) → string

Unlike Bigtable, Spanner assigns timestamps to data, which is an important way in which Spanner is more like a multiversion database than a key-value store. A tablet’s state is stored in a set of B-tree-like files and a write-ahead log, all on a distributed file system called Colossus (the successor to the Google File System [Ghemawat et al. 2003]).

2.1 スパンサーバーのソフトウェアスタック

このセクションでは、スパンサーバーのレプリケーションと分散トランザクションの実装が、Bigtableベースの実装上にどのように階層化されているのかを説明します。 図2にソフトウェアスタックが示されています。各スパンサーバーは、タブレットと呼ばれるデータ構造のインスタンス100〜1000個の処理を担当します。タブレットは、Bigtableのタブレット抽象化と似ており、次のマッピングデータを保持しています。

(key:string, timestamp:int64) → string

Bigtableと異なり、Spannerはタイムスタンプをデータに割り当てます。これは、Spannerがキーバリューストアよりもむしろマルチバージョンデータベースに近い重要な要素です。 タブレットの状態は、Bツリーライクな形式のファイルセットと先行書き込みログに格納されています。これらはすべて、Colossus(Google File System[Ghemawat et al. 2003]の後継プロダクト)という分散ファイルシステム上にあります。

f:id:master-0717:20170301133249p:plain

To support replication, each spanserver implements a single Paxos state machine on top of each tablet. (An early Spanner incarnation supported multiple Paxos state machines per tablet, which allowed for more flexible replication configurations. The complexity of that design led us to abandon it.) Each state machine stores its metadata and log in its corresponding tablet. Our Paxos implementation supports long-lived leaders with time-based leader leases, whose length defaults to 10 seconds. The current Spanner implementation logs every Paxos write twice: once in the tablet’s log, and once in the Paxos log. This choice was made out of expediency, and we are likely to remedy this eventually. Our implementation of Paxos is pipelined, so as to improve Spanner’s throughput in the presence of WAN latencies. By “pipelined,” we mean Lamport’s “multi-decree parliament” [Lamport 1998], which both amortizes the cost of electing a leader across multiple decrees and allows for concurrent voting on different decrees. It is important to note that although decrees may be approved out of order, the decrees are applied in order (a fact on which we will depend in Section 4).

レプリケーションをサポートするため、各スパンサーバーは各タブレット上に単一のPaxosステートマシンを実装します。(設計が複雑過ぎるので後に廃止しましたが、初期のSpannerはタブレットごとに複数のPaxosステートマシンをサポートしていたため、より柔軟なレプリケーション構成が可能でした。)ステートマシンはメタデータを保持し、対応するタブレットにログインします。私たちのPaxosの実装では、規定で10秒という長い生存期間のリーダーをサポートしています。現在のSpannerの実装では、Paxosのすべてのログ書き込みにおいて、タブレットのログに1回、Paxosのログに1回の計2回の書き込みが行われます。この実装は暫定的なもので、いずれ改善する可能性があります。我々のPaxosの実装はパイプライン化されているため、WANレイテンシ存在下でSpannerのスループットを向上させることができます。 パイプライン化(“multi-decree parliament” [Lamport 1998])によって複数の命令にまたがってリーダーを選ぶコストを減らし、異なる命令に同時に投票することが可能になります。命令の承認は順不同で処理されるかもしれませんが、命令の適用は順番に処理されます(同時実行制御に関しては第4章で詳細を説明します)。

The Paxos state machines are used to implement a consistently replicated bag of mappings. The key-value mapping state of each replica is stored in its corresponding tablet.Writes must initiate the Paxos protocol at the leader; reads access state directly from the underlying tablet at any replica that is sufficiently up-to-date. The set of replicas is collectively a Paxos group.

Paxosステートマシンは、マッピングデータの一貫性と冗長化を実装するために使用されます。 各レプリカのキーバリューのマッピング状態は対応するタブレットに保存されます。書き込みは、リーダーによってPaxosプロトコルを用いて実行されます。読み取りは、最新のレプリカのタブレットに対して直接実行されます。レプリカのセットは、まとめてPaxosグループと呼称します。

At every replica that is a leader, a spanserver implements a lock table to implement concurrency control. The lock table contains the state for two-phase locking: it maps ranges of keys to lock states. (Note that having a long-lived Paxos leader is critical to efficiently managing the lock table.) In both Bigtable and Spanner, we designed for long-lived transactions (for example, for report generation, which might take on the order of minutes), which perform poorly under optimistic concurrency control in the presence of conflicts. Operations that require synchronization, such as transactional reads, acquire locks in the lock table; other operations bypass the lock table. The state of the lock table is mostly volatile (i.e., not replicated via Paxos): we explain the details further in Section 4.2.1.

リーダーであるすべてのレプリカで、スパンサーバーにはロックテーブルを用いた同時実行制御が実装されています。ロックテーブルは、2フェーズロックの状態を持っており、キーの範囲をロックの状態にマッピングします。(ロックテーブルを効率的に管理するためには、生存期間の長いPaxosリーダーが存在することが必須です。)BigtableとSpannerの両方で、競合発生状況の楽観的同時実行制御下でパフォーマンスが低下する実行時間の長いトランザクション(たとえば、レポート生成のためには数分かかるかもしれない)のために、トランザクション内の読み取りなど同期が必要な操作のみロック・テーブルのロックを取得し、その他の操作はロックテーブルをバイパスするように設計されています。 ロックテーブルの状態は、基本的に揮発性です(Paxosによってレプリケーションされない)(4.2.1で詳細を説明します)。

At every replica that is a leader, each spanserver also implements a transaction manager to support distributed transactions. The transaction manager is used to implement a participant leader; the other replicas in the group will be referred to as participant slaves. If a transaction involves only one Paxos group (as is the case for most transactions), it can bypass the transaction manager, since the lock table and Paxos together provide transactionality. If a transaction involves more than one Paxos group, those groups’ leaders coordinate to perform two-phase commit. One of the participant groups is chosen as the coordinator: the participant leader of that group will be referred to as the coordinator leader, and the slaves of that group as coordinator slaves. The state of each transaction manager is stored in the underlying Paxos group (and therefore is replicated).

リーダーであるすべてのレプリカで、スパンサーバーには分散トランザクションをサポートするトランザクションマネージャーも実装されています。 トランザクションマネージャーは、パーティシパント・リーダー(グループ内の他のレプリカをパーティシパント・スレーブと呼びます)を実装するために使用されます。トランザクションが1つのPaxosグループのみを含む場合(ほとんどのトランザクションが該当すると思われる)、ロック・テーブルとPaxosがトランザクション性を提供するため、トランザクション・マネージャをバイパスすることができます。 トランザクションに複数のPaxosグループが関与する場合、それらのグループのリーダーは、2フェーズコミットを実行するように調整します。 パーティシパント・グループの1つがコーディネーターとして選ばれます。そのグループのパーティシパント・リーダーはコーディネーターリーダーと呼ばれ、そのグループのスレーブはコーディネータースレーブになります。 各トランザクションマネージャーの状態は、Paxosグループに格納されます。(したがって、レプリケーションされます)

2.2. Directories and Placement

On top of the bag of key-value mappings, the Spanner implementation supports a bucketing abstraction called a directory, which is a set of contiguous keys that share a common prefix. (The choice of the term directory is a historical accident; a better term might be bucket.) We will explain the source of that prefix in Section 2.3. Supporting directories allows applications to control the locality of their data by choosing keys carefully.

Spannerの実装では、キーバリューマッピングデータ上に、ディレクトリと呼ばれるバケット抽象化をサポートしています。これは、共通のプレフィックスを共有する一連の連続したキーのセットです。 (directoryという命名は歴史的な災難で、より良い命名はbucketかもしれません。)そのプレフィックスについては2.3で説明します。ディレクトリのサポートによってアプリケーションは、キーを慎重に選択することで、データのロケーションを制御できます。

A directory is the unit of data placement. All data in a directory has the same replication configuration. When data is moved between Paxos groups, it is moved directory by directory, as shown in Figure 3. Spanner might move a directory to shed load from a Paxos group; to put directories that are frequently accessed together into the same group; or to move a directory into a group that is closer to its accessors. Directories can be moved while client operations are ongoing. One would expect that a 50MB directory could be moved in a few seconds.

ディレクトリは、データのロケーションの単位です。ディレクトリ内のすべてのデータは、同じレプリケーション構成を持ちます。Paxosグループ間でデータを移動すると、図3に示すように、ディレクトリごとに移動します。Spannerは、不要なロードを削減するためにPaxosグループからディレクトリを移動することがあります。例えば、頻繁に同時アクセスされるディレクトリを同じグループに入れたり、ディレクトリをアクセサに近いグループに移動したりします。クライアント操作が進行中の間でも、ディレクトリを移動することができます。ディレクトリのサイズが50MBの場合、数秒で移動させることが予想されます。

f:id:master-0717:20170302133626p:plain

The fact that a Paxos group may contain multiple directories implies that a Spanner tablet is different from a Bigtable tablet: the former is not necessarily a single lexicographically contiguous partition of the row space. Instead, a Spanner tablet is a container that may encapsulate multiple partitions of the row space. We made this decision so that it would be possible to colocate multiple directories that are frequently accessed together.

Paxosグループに複数のディレクトリが含まれている可能性があるということは、SpannerのタブレットがBigtableのタブレットとは異なることを意味します。Spannerのタブレットは、辞書的連続性のある1つのパーティションである必要がありません。代わりに、Spannerのタブレットは、複数のパーティションをカプセル化できるコンテナです。私たちは、頻繁に同時アクセスされる複数のディレクトリを同一ロケーションに配置することができるように、この決定を下しました。

Movedir is the background task used to move directories between Paxos groups [Douceur and Howell 2006]. Movedir is also used to add to or remove replicas from Paxos groups [Lorch et al. 2006] by moving all of a group’s data to a new group with the desired configuration, because Spanner does not yet support in-Paxos configuration changes. Movedir is not implemented as a single transaction, so as to avoid blocking ongoing reads and writes on a bulky data move. Instead, movedir registers the fact that it is starting to move data and moves the data in the background. When it has moved all but a nominal amount of the data, it uses a transaction to atomically move that nominal amount and update the metadata for the two Paxos groups.

Movedirは、Paxosグループ間でディレクトリを移動するためのバックグラウンドタスクです[Douceur and Howell 2006]。SpannerがPaxosの構成変更をまだサポートしていないため、Movedirは、グループの全てのデータを新たに構成したPaxosグループに移動することにより、Paxosグループのレプリカを追加・削除するためにも使用されます[Lorch et al. 2006]。Movedirは、単一のトランザクションとして実装されていないため、大量のデータ移動にもかかわらず進行中の読み取りと書き込みをブロックしません。Movedirはデータの移動を開始しバックグラウンドでデータを移動しているという状態を登録し、ほとんどのデータを移動した後に、トランザクションを使用して残ったあと少しのデータをアトミックに移動し、2つのPaxosグループのメタデータを更新します。

A directory is also the smallest unit whose geographic-replication properties (or placement, for short) can be specified by an application. The design of our placementspecification language separates responsibilities for managing replication configurations. Administrators control two dimensions: the number and types of replicas, and the geographic placement of those replicas. They create a menu of named options in these two dimensions (e.g., North America, replicated 5 ways with 1 witness). An application controls how data is replicated, by tagging each database and/or individual directories with a combination of those options. For example, an application might store each end-user’s data in its own directory, which would enable user A’s data to have three replicas in Europe, and user B’s data to have five replicas in North America.

ディレクトリは、地理的冗長化のプロパティ(またはロケーション)をアプリケーションが指定できる最小単位です。ロケーション記述言語の設計は、レプリケーションの構成管理における責務を分離しています。管理者は2つの構成オプションを制御します。レプリカの数とタイプ、およびレプリカのロケーションです。これらの2つの構成オプションでメニューを作成します(例えば北米で、1つの監視サーバーと5つのレプリカサーバーなど)。アプリケーションは、各データベースまたはディレクトリに、これらの構成オプションの組み合わせを設定することによって、データのレプリケーション方法を制御します。たとえば、各エンドユーザーのデータを独自のディレクトリに格納するよう設定すれば、ユーザーAのデータはヨーロッパに3つのレプリカがあり、ユーザーBのデータは北米に5つのレプリカが存在する等の構成が行えます。

For expository clarity we have oversimplified. In fact, Spanner will shard a directory into multiple fragments if it grows too large. Fragments may be served from different Paxos groups (and therefore different servers). Movedir actually moves fragments, and not whole directories, between groups.

簡潔に説明するために、単純化し過ぎました。実際、Spannerは、ディレクトリが大きくなりすぎると、ディレクトリを複数のフラグメントに分割します。フラグメントは、異なるPaxosグループ(したがって異なるサーバー)から提供されることがあります。Movedirは実際にはグループ間でディレクトリ全体ではなくフラグメントを移動します。

2.3. Data Model

Spanner exposes the following set of data features to applications: a data model based on schematized semirelational tables, a query language, and general-purpose transactions. The move towards supporting these features was driven by many factors. The need to support schematized semirelational tables and synchronous replication is supported by the popularity of Megastore [Baker et al. 2011]. At least 300 applications within Google use Megastore (despite its relatively low performance) because its data model is simpler to manage than Bigtable’s, and because of its support for synchronous replication across datacenters. (Bigtable only supports eventuallyconsistent replication across datacenters.) Examples of well-known Google applications that use Megastore are Gmail, Picasa, Calendar, Android Market, and AppEngine. The need to support an SQL-like query language in Spanner was also clear, given the popularity of Dremel [Melnik et al. 2010] as an interactive dataanalysis tool. Finally, the lack of cross-row transactions in Bigtable led to frequent complaints; Percolator [Peng and Dabek 2010] was in part built to address this failing. Some authors have claimed that general two-phase commit is too expensive to support, because of the performance or availability problems that it brings [Chang et al. 2008; Cooper et al. 2008; Helland 2007]. We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions. Running two-phase commit over Paxos mitigates the availability problems.

2.3. データモデル

Spannerは、スキーマ定義されたセミリレーショナルテーブル、クエリ言語、および汎用トランザクションをアプリケーションに提供します。これらの機能をサポートしようという動機は、多くの要因によってもたらされました。スキーマ定義されたセミリレーションテーブルと同期レプリケーションをサポートする必要性は、Megastore[Baker et al. 2011]の人気によって支えられています。Googleの中で少なくとも300のアプリケーションは、そのデータモデルがBigtableよりも管理が簡単で、データセンター間の同期レプリケーションをサポートしているため、(パフォーマンスは比較的低いにもかかわらず)Megastoreを使用しています。Megastoreを使用するよく知られているGoogleアプリケーションの例としては、Gmail、Picasa、Calendar、Android Market、AppEngineなどがあります(Bigtableはデータセンター間で結果整合性を保つレプリケーションしかサポートしていません)。インタラクティブなデータ分析ツールであるDremel[Melnik et al. 2010]の人気を考えると、SpannerでSQLライクなクエリ言語をサポートする必要性も明らかでした。最後に、Bigtableには行間トランザクションのサポートが無かったため、頻繁に苦情が寄せられました。Percolator[Peng and Dabek 2010]は、この問題に対処するために組み込まれました。一般的な2フェーズコミットは、それがもたらす性能または可用性の低下と比べて、恩恵が少なすぎると主張する著者もいます[Chang et al. 2008; Cooper et al. 2008; Helland 2007]。我々は、アプリケーションプログラマーにとって、トランザクションの過剰利用が原因でボトルネックが発生しパフォーマンス問題に取り組む事になる方が、トランザクションのサポートが無いせいでコーディング量が増える事よりも良いと信じています。また、Paxos上の2フェーズコミットは可用性の問題を緩和します。

The application data model is layered on top of the directory-bucketed key-value mappings supported by the implementation. An application creates one or more databases in a universe. Each database can contain an unlimited number of schematized tables. Tables look like relational-database tables, with rows, columns, and versioned values. We will not go into detail about the query language for Spanner. It looks like SQL with some extensions to support protocol-buffer-valued [Google 2008] fields.

このデータモデルは、ディレクトリバケット内のキーバリューデータ上に実装されています。アプリケーションは、ユニバース内に1つ以上のデータベースを作成します。各データベースには、無制限のスキーマ定義されたテーブルを含めることができます。テーブルは、行、列、およびバージョニングされた値を持つリレーショナルデータベーステーブルのように見えます。Spannerのクエリ言語について詳しくは触れません。Spannerのクエリ言語は、Protocol Buffers[Google 2008]をサポートする拡張機能を備えたSQLのようなものです。

Spanner’s data model is not purely relational, in that rows must have names. More precisely, every table is required to have an ordered set of one or more primary-key columns. This requirement is where Spanner still looks like a key-value store: the primary keys form the name for a row, and each table defines a mapping from the primary-key columns to the non-primary-key columns. A row has existence only if some value (even if it is NULL) is defined for the row’s keys. Imposing this structure is useful because it lets applications control data locality through their choices of keys.

Spannerのデータモデルは、行が名前を持たなければならないという点で、純粋にリレーショナルではありません。より正確には、すべてのテーブルには、ソート済み主キー列セットが必要です。この要件は、Spannerがキーバリューストアのように見える面です。主キーは行の名前を表し、各テーブルは主キー列から非主キー列へのマッピングを定義します。行は、その行のキーに何らかの値(NULLであっても)が定義されている場合にのみ存在します。この実装は、アプリケーションがキーの選択によってデータのロケーションを制御できるという利便性をもたらします。

Figure 4 contains an example Spanner schema for storing photo metadata on a per-user, per-album basis. The schema language is similar to Megastore’s, with the additional requirement that every Spanner database must be partitioned by clients into one or more hierarchies of tables. Client applications declare the hierarchies in database schemas via the INTERLEAVE IN declarations. The table at the top of a hierarchy is a directory table. Each row in a directory table with key K, together with all of the rows in descendant tables that start with K in lexicographic order, forms a directory. ON DELETE CASCADE says that deleting a row in the directory table deletes any associated child rows. The figure also illustrates the interleaved layout for the example database: for example, Albums(2,1) represents the row from the Albums table for user id 2, album id 1. This interleaving of tables to form directories is significant because it allows clients to describe the locality relationships that exist between multiple tables, which is necessary for good performance in a sharded, distributed database. Without it, Spanner would not know the most important locality relationships.

図4に、ユーザーごと、アルバムごとに写真のメタデータを保存するSpannerスキーマの例を示します。スキーマ言語はMegastoreに似ていますが、すべてのSpannerデータベースはクライアントによって1つ以上のテーブル階層構造に分割される必要があります。クライアントアプリケーションは、INTERLEAVE IN宣言によってデータベーススキーマの階層を宣言します。階層の最上位にあるテーブルはディレクトリテーブルです。キーKを持つディレクトリテーブルの各行は、辞書順にKで始まる子テーブルのすべての行と共に、ディレクトリを形成します。 ON DELETE CASCADEでディレクトリテーブル内の行を削除すると、関連する子の行が削除されます。この図は、サンプルデータベースのインターリーブ(追記:別々のディレクトリに配置)されたレイアウトも示しています。たとえば、Albums(2,1)は、ユーザーID 2、アルバムID 1のAlbumsテーブルの行を表します。ディレクトリを形成するためのこのテーブルのインターリーブは、クライアントが複数のテーブル間に存在するロケーションの関係性を指定することを可能にするために重要で、分割・分散されたデータベースにおいて良好な性能を得るためにも重要です。それがなければ、Spannerは最も重要なロケーションの関係性を管理できません。

f:id:master-0717:20170303155722p:plain

blog.game-programmer.jp

GoogleのSpannerに関する論文の和訳 1/6

Googleが2013年に発表したSpannerに関する論文の和訳です。長いので全6回ぐらいに分けて訳していこうと思います。

Spanner: Google’s Globally Distributed Database

http://dl.acm.org/citation.cfm?id=2491245

Spanner is Google’s scalable, multiversion, globally distributed, and synchronously replicated database. It is the first system to distribute data at global scale and support externally-consistent distributed transactions. This article describes how Spanner is structured, its feature set, the rationale underlying various design decisions, and a novel time API that exposes clock uncertainty. This API and its implementation are critical to supporting external consistency and a variety of powerful features: nonblocking reads in the past, lockfree snapshot transactions, and atomic schema changes, across all of Spanner.

Spannerは、Googleのスケーラブルで、マルチバージョン(追記:更新前の過去の行も保持している)で、グローバルに分散された、同期的レプリケーションされているデータベースです。 これは、グローバル規模でデータを分散し、かつ一貫した分散トランザクションを提供する最初のシステムです。 この論文では、Spannerの構造、その機能セット、さまざまな設計上の決定の根拠、時刻の不確実性を提供する新しいTime API(追記:時刻を返すのではなく確実に現在時刻が含まれる帯域を返す)について説明します。 このTime APIは、一貫性と様々な強力な機能(過去のデータのノンブロッキング読み取り、ロックフリースナップショットトランザクション、およびアトミックなスキーマ変更)をSpannerでサポートするために重要なAPIです。

1.INTRODUCTION

Spanner is a scalable, globally distributed database designed, built, and deployed at Google. At the highest level of abstraction, it is a database that shards data across many sets of Paxos [Lamport 1998] state machines in datacenters spread all over the world. Replication is used for global availability and geographic locality; clients automatically failover between replicas. Spanner automatically reshards data across machines as the amount of data or the number of servers changes, and it automatically migrates data across machines (even across datacenters) to balance load and in response to failures. Spanner is designed to scale up to millions of machines across hundreds of datacenters and trillions of database rows.

1. 序論

Spannerは、Googleで設計、構築、展開されたスケーラブルでグローバルに分散したデータベースです。 最も抽象度の高いレベルは世界中に広がるデータセンター上で動作するPaxosステートマシンのセットで、グローバルな可用性と地理的冗長化のためにレプリケーションされます。 クライアントはレプリカ間で自動的にフェールオーバーします。 Spannerは、データ量やサーバー数が変化すると自動的にデータを再共有し、負荷を分散し、障害に対応してマシン間でデータを自動的に移行します。 Spannerは、数百万台のマシン、何百のデータセンター、何兆のデータベース行にまでスケールアップできるように設計されています。

Applications can use Spanner for high availability, even in the face of wide-area natural disasters, by replicating their data within or even across continents. Our initial customer was F1 [Shute et al. 2012], a rewrite of Google’s advertising backend. F1 uses five replicas spread across the United States. Most other applications will probably replicate their data across 3 to 5 datacenters in one geographic region, but with relatively independent failure modes. That is, most applications will choose lower latency over higher availability, as long as they can survive 1 or 2 datacenter failures.

広域自然災害においてもSpannerがデータを大陸内または大陸間で複製することによって、アプリケーションは可用性を維持することができます。 最初の事例はF1[Shute et al. 2012](GoogleでAdWordsビジネスをサポートするために構築された分散リレーショナルデータベースシステム)です。 F1は、米国全土に広がる5つのレプリカを使用しています。 他のほとんどのアプリケーションでは、おそらく1つの地域の3~5のデータセンターにデータを複製しますが、比較的に独立して障害が発生します。ほとんどのアプリケーションでは、1~2つのデータセンターの障害に耐えられる限り、高可用性よりも低レイテンシを選択します。

Spanner’s main focus is managing cross-datacenter replicated data, but we have also spent a great deal of time in designing and implementing important database features on top of our distributed-systems infrastructure. Even though many projects happily use Bigtable [Chang et al. 2008], we have also consistently received complaints from users that Bigtable can be difficult to use for some kinds of applications: those that have complex, evolving schemas, or those that want strong consistency in the presence of wide-area replication. (Similar claims have been made by other authors [Stonebraker 2010b].) Many applications at Google have chosen to use Megastore [Baker et al. 2011] because of its semirelational data model and support for synchronous replication, despite its relatively poor write throughput. As a consequence, Spanner has evolved from a Bigtable-like versioned key-value store into a temporal multiversion database. Data is stored in schematized semirelational tables; data is versioned, and each version is automatically timestamped with its commit time; old versions of data are subject to configurable garbage-collection policies; and applications can read data at old timestamps. Spanner supports general-purpose transactions, and provides an SQL-based query language.

Spannerが注力するのはデータセンター間での複製データを管理することですが、我々は分散インフラ上にデータベース機能を設計・実装するのにも多大な時間を費やしました。多くのプロジェクトは喜んでBigtable [Chang et al. 2008]を利用していましたが、複雑なスキーマを持つアプリケーション、スキーマを変更し続けていくアプリケーション、グローバル規模でレプリケーションしつつ強力な一貫性を必要とするアプリケーションにおいてはBigtableを使用することが困難であるという報告をユーザーから受けていました。 (同様の主張は、他の著者[Stonebraker 2010b]も行っています)。Googleの多くのアプリケーションは、セミリレーショナルデータモデルと同期レプリケーションのサポートのために、書き込みスループットが比較的低いにもかかわらずMegastore [Baker et al. 2011]を使用することを選択しました。結果として、Spannerは、Bigtableのようなバージョン管理されたキーバリューストアからテンポラルマルチバージョンデータベースに進化しました。データは、スキーマ定義されたセミリレーショナルテーブルに格納されます。データのバージョン管理が行われ、各バージョンのコミット時間が自動的にタイムスタンプされます。古いバージョンのデータはポリシー設定可能なガベージコレクションの対象です。アプリケーションは古いタイムスタンプでデータを読み取ることができます。 Spannerは汎用トランザクションをサポートし、SQLベースのクエリ言語を提供します。

As a globally distributed database, Spanner provides several interesting features. First, the replication configurations for data can be dynamically controlled at a fine grain by applications. Applications can specify constraints to control which datacenters contain which data, how far data is from its users (to control read latency), how far replicas are from each other (to control write latency), and how many replicas are maintained (to control durability, availability, and read performance). Data can also be dynamically and transparently moved between datacenters by the system to balance resource usage across datacenters. Second, Spanner has two features that are difficult to implement in a distributed database: it provides externally consistent [Gifford 1982] reads and writes, and globally consistent reads across the database at a timestamp. These features enable Spanner to support consistent backups, consistent MapReduce executions [Dean and Ghemawat 2010], and atomic schema updates, all at global scale, and even in the presence of ongoing transactions.

グローバルに分散しているデータベースとして、Spannerにはいくつかの興味深い機能があります。第1に、データのレプリケーション構成は、アプリケーションごとに細かく動的に制御できます。アプリケーションでは、どのデータセンターにどのデータを保持するか、ユーザーからのデータの距離(読み取りレイテンシの制御)、レプリカ間の距離(書き込み待ち時間の制御)、保持されるレプリカの数(耐久性 、可用性、および読み取りパフォーマンスの制御)を制御できます。システムによってデータセンター間でデータを動的かつ透過的に移動して、データセンター間のリソース使用状況のバランスをとることもできます。第2に、Spannerには分散データベースで同時に実現するのが難しい2つの機能があります。一貫した読み書きトランザクションの提供[Gifford 1982]と、(タイムスタンプを利用した)データベース全体における一貫した読み取りの提供です。これらの機能により、Spannerは一貫性のあるバックアップ、一貫性のあるMapReduceの実行[Dean and Ghemawat 2010]、およびアトミックなスキーマ更新をすべてグローバル規模で、また進行中のトランザクションが存在する場合でもサポートできます。

These features are enabled by the fact that Spanner assigns globally meaningful commit timestamps to transactions, even though transactions may be distributed. The timestamps reflect serialization order. In addition, the serialization order satisfies external consistency (or equivalently, linearizability [Herlihy and Wing 1990]): if a transaction T1 commits before another transaction T2 starts, then T1’s commit timestamp is smaller than T2’s. Spanner is the first system to provide such guarantees at global scale.

これらの機能は、トランザクションが分散されていても、Spannerがトランザクションにグローバルに正確なコミットタイムスタンプを割り当てることで実現可能となります。 タイムスタンプはシリアル化順序を反映します。 さらに、シリアル化順序は外部整合性(または等価的に線形性[Herlihy and Wing 1990])を満たします。トランザクションT1が別のトランザクションT2が開始する前にコミットすると、T1のコミットタイムスタンプはT2よりも小さくなります。 Spannerは、世界規模でそのような保証を提供する最初のシステムです。(追記:一般的にリレーショナルデータベースはトランザクションにIDを割り当てて処理順の整合性を取るがSpannerではIDの代わりに正確なタイムスタンプを利用している。)

The key enabler of these properties is a new TrueTime API and its implementation. The API directly exposes clock uncertainty, and the guarantees on Spanner’s timestamps depend on the bounds that the implementation provides. If the uncertainty is large, Spanner slows down to wait out that uncertainty. Google’s cluster-management software provides an implementation of the TrueTime API. This implementation keeps uncertainty small (generally less than 10ms) by using multiple modern clock references (GPS and atomic clocks). Conservatively reporting uncertainty is necessary for correctness; keeping the bound on uncertainty small is necessary for performance.

これらの機能を実現可能とするのは、新しいTrueTime APIとその実装です。 APIは時刻の不確実性(追記:現在時刻が確実に含まれる時刻帯域)を返し、Spannerで保証できることは、そのTrueTime APIの限界に依存します。 不確実性が大きい場合、Spannerはその不確実性を待つために減速します。 Googleのクラスタ管理ソフトウェアがTrueTime APIの実装を提供します。 この実装は、複数の最新の時計(GPSおよび原子時計)を参照することで、不確実性を小さく抑えます(一般に10ms未満)。 正確さのために不確実性の帯域を大きめに返却する必要がありますが、パフォーマンスのためには不確実性の帯域を小さくすることが必要です。

Section 2 describes the structure of Spanner’s implementation, its feature set, and the engineering decisions that went into their design. Section 3 describes our new TrueTime API and sketches its implementation. Section 4 describes how Spanner uses TrueTime to implement externally-consistent distributed transactions, lock-free snapshot transactions, and atomic schema updates. Section 5 provides some benchmarks on Spanner’s performance and TrueTime behavior, and discusses the experiences of F1. Sections 6, 7, and 8 describe related and future work, and summarize our conclusions.

セクション2では、Spannerの実装構造、機能セット、および現在の設計に至るまでの意思決定について説明します。 セクション3では、新しいTrueTime APIと、その実装について説明します。 セクション4では、SpannerがTrueTime APIを使用して一貫性のある分散トランザクションの提供、ロックフリーのスナップショットトランザクション、およびアトミックなスキーマ更新を実装する方法について説明します。 セクション5では、SpannerのパフォーマンスとTrueTime APIの動作に関するベンチマークを提供し、F1の経験について説明します。 6章、7章、8章では、関連する作業と今後の作業について説明し、結論をまとめます。

blog.game-programmer.jp