451 Unavailable For Legal Reasons


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




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().


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


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.


関数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 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.


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.