上の記事の続きです。
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() メソッドのラッパーユーティリティです。
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によって参照される時計は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は不確実性の間、処理を待機することができるため、εの変化によって正確性は影響を受けませんが、εが増えすぎるとパフォーマンスが低下する可能性があります。
