TSP: The Time Synchronization Protocol for UNIX 4.3BSD - インターネット時刻同期の歴史(その2)

まずは時代背景

令和の感覚だと BSD 如きが for UNIX ってずいぶんと大きく出たなとなるが、当時は USL(Unix System Laboratories) vs BSDi(Berkeley Software Design, Inc.) の 忌まわしき訴訟 もまだ発生してないので BSD 「我 UNIX ぞ？」は驕り高ぶり言語道断どころかごく普通の感覚なので許してほしい。

元始、UNIX は 1 台の高価なコンピューターを複数人で共有するタイムシェアリングシステムだった。 そしてネットワークというのはダム端末からメインフレームに接続するための回線(電話線など)の事だった。

しかし価格がこなれたこと、そして ARPANET を経て TCP/IP が実装されたことでハッカーｶﾀｶﾀｶﾀｯﾀｰﾝ!の興味は複数台のコンピューターがリソースを共有し並列して計算を実行する分散コンピューティングへと向かう、Distributed System 略して DS オーケーいい子だ全て繋がった、やはりディープステートは DARPA 軍産複合体の陰謀！

なんせ当時はマルチプロセッシングは限定的かつ高価で、ナウくてイマい用語を使うとスケールアップの限界が低くスケールアウトが至上命題だったのだ。

分散コンピューティング環境でそれぞれのホストが勝手な時刻で動いていたら大問題である。 リソース共有で最も成功した分野といえば現代のクラウドストレージにも通じる分散ファイルシステムだ。 しかしホストがファイルのタイムスタンプをオレオレ時刻で更新したら混乱そして破壊の元である。

別のホストによってタイムスタンプが巻き戻されようもんなら、dump(8) あるいは tar(1) によるインクリメンタルバックアップすら失敗するわけでな。

TSP と timed(8) の誕生

(♪～「パリは燃えているか」が流れる)

4.3BSD において inetd(8) が実装され RFC868 Time Protocol によるインターネット時刻同期システムが使えるようになったものの、当時でさえ実用性無いよね…ってのが共通認識だったのは 前回 説明した通りである。現実的にはありゃネットワークプログラミングの Hello, World. でしかない。

そこで CSRG(Computer Systems Research Group) の R.Gusella と S.Zatti は新たに TSP という時刻同期プロトコルを提唱した。

• The Berkeley UNIX Time Synchronization Protocol

同時に 4.3BSD に timed(8) という TSP の最初にして最後の実装が搭載された。

ちなみに macOS High Sierra で ntpd(8) を置き換えた timed は全くの別物であって仮にも *BSD の系譜なら名前被りやめろや！

というか timed 自体命名が安直過ぎて time + daemon なのか time の過去形なのか grep friendly ではないので命名センスってホントだいじ。

この timed(8) 当時としては巨大といっていい規模のソフトウェアなのだが、なぜか扱いは非常に小さい。

UNIX 4.3BSD の設計と実装 だと

13.3 カーネルの初期化

で timed(8) の存在についてほんの一行

そして 4.4BSD の設計と実装 で

3.6.2 時刻の調整

で TSP のために追加されたシステムコール adjtime(2) についてこちらも一行程度触れられてるだけである。

つまりはあのカーク・魔球ジック先生でも投げられなかった変化球を今私は投げてるわけで、ウィキペディアンにアンサイクロペディアンが勝ったかのような高揚感があるわけです(アヘ顔)。

なぜ流行らなかったムジーナのか

ペーパーがお出しされたのは 1985 年で 4.3BSD のリリースが 1986 年。

しかしこの頃にはとっくにインターネット時刻同期に関してはプロやな────な御仁がいたのだ。 先月亡くなられた NTP のゴッドすなわち神 David L. Mills 教授である。

すでに理論と実装を DCNET(Distributed Computer Network) 上のホストで成功させ IEN173 Time Synchronization in DCNET Hosts および RFC778 DCNET Internet Clock Service をお出したのが 1981 年のこと。

そしてその実績を引っ提げ NTPv0 こと 今現在まで40年以上時刻同期のファーストチョイスであり続ける NTP のビッグバンとなった RFC958 Network Time Protocol をお出ししたのも同じ 1985 年なのだ。

つまりこの頃にはとっくに NTP こそが本命で将来のデファクトスタンダードの座は約束されていたのだ。

なんてこったい RFC868 Time Protocol にはネットワークプログラミングの Hello, World. としての価値がまだ残っている。 しかし TSP は実装あったにも関わらずチャンスはゼロどころか マイナスワンワンワンあくしろよ(20ミリ機関砲)じゃねえか！

プロトコルを読み解く

TSP のデータグラムを定義したヘッダがあるのでそれを参照すれば一目瞭然。

• 4.3BSD/usr/src/include/protocols/timed.h#9

 9 /*
10  * Time Synchronization Protocol
11  */
12 
13 #define	TSPVERSION	1
...
16 struct tsp {
17 	u_char	tsp_type;
18 	u_char	tsp_vers;
19 	u_short	tsp_seq;
20 	union {
21 		struct timeval tspu_time;
22 		char tspu_hopcnt;
23 	} tsp_u;
24 	char tsp_name[MAXHOSTNAMELEN];
25 };
...
30 /*
31  * Command types.
32  */
33 #define	TSP_ANY			0	/* match any types */
34 #define	TSP_ADJTIME		1	/* send adjtime */
35 #define	TSP_ACK			2	/* generic acknowledgement */
36 #define	TSP_MASTERREQ		3	/* ask for master's name */ 
37 #define	TSP_MASTERACK		4	/* acknowledge master request */
38 #define	TSP_SETTIME		5	/* send network time */
39 #define	TSP_MASTERUP		6	/* inform slaves that master is up */
40 #define	TSP_SLAVEUP		7	/* slave is up but not polled */
41 #define	TSP_ELECTION		8	/* advance candidature for master */
42 #define	TSP_ACCEPT		9	/* support candidature of master */
43 #define	TSP_REFUSE		10	/* reject candidature of master */
44 #define	TSP_CONFLICT		11	/* two or more masters present */
45 #define	TSP_RESOLVE		12	/* masters' conflict resolution */
46 #define	TSP_QUIT		13	/* reject candidature if master is up */
47 #define	TSP_DATE		14	/* reset the time (date command) */
48 #define	TSP_DATEREQ		15	/* remote request to reset the time */
49 #define	TSP_DATEACK		16	/* acknowledge time setting  */
50 #define	TSP_TRACEON		17	/* turn tracing on */
51 #define	TSP_TRACEOFF		18	/* turn tracing off */
52 #define	TSP_MSITE		19	/* find out master's site */
53 #define	TSP_MSITEREQ		20	/* remote master's site request */
54 #define	TSP_TEST		21	/* for testing election algo */
55 #define	TSP_SETDATE		22	/* New from date command */
56 #define	TSP_SETDATEREQ		23	/* New remote for above */
57 #define	TSP_LOOP		24	/* loop detection packet */
...

RFC868 Time Protocol よりはぐっと複雑ではあるけど、しょせんコマンドと時刻情報(あるいはホップ数)を投げ合うだけだからクソみてえなJSONを日常的に投げ合う現代人にとっては単純明快ですね。

通信内容を実際に確認するのもいいけどUDPでブロードキャストだからパケットキャプチャ必要になるのでパス。

そんでお気づきになられただろうか、 tspu_time フィールドはまんま timeval(3) なんだけど当時は time_t tv_sec フィールドが 32bit だからプロトコルとして 2038 年問題抱えてるんだよな。

まぁ tsp_vers としてバージョン持ってるから 64bit 対応して TSPVERSION を 2 にするだけではある。しかしいまさらやる意味があるかというと疑問だなぁ。

拡張性スケーラビリティに欠けるが耐障害性フォールトトレラントに優れる

timed(8) はマスタースレーブの完全中央集権モデルなのでスケーラビリティには欠け LAN(Local Area Network) 内のごく小規模な世界での時刻同期がせいぜいである。 つーか当初はスレーブをリストでなく固定長の配列で管理しており最大 100 台までしか参加できなかった。

しかしマスターが消失した場合であってもスレーブの中から新しいマスターが選ばれるので単一障害点シングルポイントオブフェイラーとはならない。 立派にフォールトトレラントな分散ディストリビューテッドコンピューティングシステムといっていいだろう。 分散バージョン管理とドヤりながら GitHubが落ちたサボりの口実 だけで仕事放り出して SNS でお茶挽いてる不思議な人給料泥棒たちよりマシである。

そもそも NTP で組織化された階層的なマスタースレーブ構造が提案されるのは 1988 年の RFC1059 Network Time Protocol (Version 1) Specification and Implementation となるのでこの時点では理論でも実装でも先行していたと評価してあげてもいいんじゃねえかな当時の空気知らんけど。

まぁ TSP と NTP はそもそも目指す先が違って一歩先にいようがそこは崖の先だったんだがそれは後述する。

ちなみに分散コンピューティングのリーダー選挙問題には

• Chang and Roberts Algorithm(a.k.a Ring Algorithm) … ヤーヤーヤー叫びながら殴りに行きそうだが、要は輪番でバトンが渡る (でもお前んち電話無いから連絡網回ってこないじゃん)
• Bully Algorithm … Bully (=いじめ)という物騒な名前だが、要は一番立場弱いのが押しつけられる損な役割パターン (君らのトラウマこと学級委員決めるときのアレ)

といった解があるが、timed(8) は前者を採用している。

プロトコルで定義されたコマンドのうち

• TSP_MASTERREQ
• TSP_MASTERACK
• TSP_MASTERUP
• TSP_SLAVEUP
• TSP_ELECTION
• TSP_ACCEPT
• TSP_REFUSE
• TSP_CONFLICT
• TSP_RESOLVE

とかなりの部分がリーダー選挙のものである、別に俺は分散コンピューティング講座をしたいわけではないしする能力も持ち合わせていないのでソースは各自勝手に読んでいただきたい。

参考書は同じ著者がリーダー選挙問題についてペーパー書いてるのでどうぞ。

• An Election Algorithm for a Distributed Clock Synchronization Program

TEMPO(a.k.a Berkeley Algorithm) による時刻調整

俺が書きたい話はこっちなのである。

プロトコルで定義されたコマンドのうち

• TSP_ADJTIME
• TSP_SETTIME
• TSP_DATEACK
• TSP_SETDATE
• TSP_SETDATEREQ

が時刻関連のものだが、このうち TSP_ADJTIME による時刻調整が TSP の最も重要な世界遺産といえる。 JR日光駅前からバス乗って1日かけてソースコード探索するに値する発明といえよう。 なお東武バス日光フリーパスはみどりの窓口での取り扱いは終了しました。

この時刻調整機能について TSP の筆者らは TEMPO (チテンポ) と名づけ実装の前(1983 年)と後(1987 年)にそれぞれペーパーを書いている。

• TEMPO: A Network Time Controller for a Distributed Berkeley UNIX System
• The accuracy of the clock synchronization achieved by TEMPO in Berkeley UNIX 4.3BSD

これは今も広く読まれているはずである、なんせ WikiPedia にも 記事 あるし(暴論)。

なお TEMPO という名前では呼ばれず Berkeley Algorithm が一般的みたいね、まぁ一般名詞と被せるとどうしてもそうなる。 CITRUS とかいわれても甘くて美味しいですよねとしかならんからな、つーか「特筆性の基準を満たしていないおそれのある記事」テンプレ貼ってもいいっすか自分。

今北産業で理解する TEMPO

ペーパーで図解されてる 3 ステップを理解するだけ、文章化すると三行より増えるがそれは俺のせい。

• マスターは自身とスレーブの時間差 clockdiff を収集する(コマンドは使わずICMP timestampを使う)
• clockdiff がプラマイ 20 秒を超えるスレーブは異常値とし TSP_SETTIME による強制時刻同期の対象とする
• clockwork orange の異常者はルドヴィコ療法の対象とする
• マスターはプラマイ 20 秒に収まってる正常なスレーブの clockdiff 平均値を計算する
• マスターの時刻を clockdiff 平均値で補正した時刻を以後「正しい時刻」とする
• マスターは自身とスレーブに TSP_ADJUST コマンドで「正しい時刻」からのズレを通知して時刻調整を行わせる
• 時刻調整は新しいシステムコール adjtime(2) を使って行う
• 時刻同期完了！
• マスターオブパペットってメタリカだっけ、マスター！マスター！！

ということ。

RFC868 Time Protocol ではマスターの時刻にスレーブが強制同期したのだけど TSP においてマスターは絶対的な存在どころか単なるコーディネーターで、自らもまた時刻調整の対象なのだ。

はい、そろそろお気づきになられたと思いますが TSP は時刻の調停をするけれど その調停による「正しい時刻」ってのは協定世界時 (UTC) とはまったく無関係なんだよね。

つまり異常値が多数派になってしまったら正常値も強制的に異常値に同化させられてしまうディストピアなわけ。 民主主義の悪しき側面を煮詰めたようなシステムですね(今年はロシアとアメリカの大統領選挙の年であることに目を逸らしながら)。 つまりバカのエコーチェンバー極まれば現在時刻が西暦 1145148101919 年にもなりうるシステムなのだ(2038 年問題さえ修正すれば)。

それと統計学知らずによくプログラマやってんなおじさん「統計学知らずによくプログラマやってんな」が平均値使わずここは中央値だろって発作起こしそうである、いや使ってもダメだろ！？

一方で NTP はあらゆるマシンが協定世界時とミリ秒レベルで同期する世界を目指してたわけで、最初から勝負はついていたのだ。

adjtime(2) システムコールの発明と普及

前述の TSP_ADJTIME の実装のために、4.3BSD では新たに adjtime(2) システムコールがカーネルに追加された。

settimeofday(2) では時刻は強制的に書き換えられるので、時刻は後ろ向きに戻る可能性がある。

だが adjtime(2) は違う(ｷﾞｭｯ)、「正しい時刻」とのズレを指定すると一定時間の間クロックスピードを上げたり下げたりして時刻が同期するまで待つのである。

つまり現在時刻ちゃんに追いつくため早足になったり、追いつくのを待つべくわざと遅く歩いたりする理解ある彼ﾋﾟモードを kernel に実装したわけ。

これは BSD のみならず他のオペレーティングシステムにも波及していくこととなる。

そして NTP においても

• RFC1059 Network Time Protocol (Version 1) Specification and Implementation

で TEMPO 論文が参考文献に上がり

• RFC1305 Network Time Protocol (Version 3) Specification, Implementation and Analysis

では adjtime(2) を使っての時刻調整が言及され

• RFC5905 Network Time Protocol Version 4: Protocol and Algorithms Specification

で実際に adjtime(2) を使った時刻調整のコード例も提示され、ついに一矢報いることに成功したのだ。 そうまるでアンサイクロペディアンがウィキペディアンに勝ちおおせたかのようだ(二度目)！

よし、TSP と timed(8) には adjtime(2) を産んだだけ生きた意味はあった、俺には無いけどな！

TSP の現状

386BSD 0.0 がリリースされた 1992 年には NTPv3 の実装 xntpd も登場している。 その頃にはもう誰も timed(8) 使ってなかったんじゃないですかね。

• 各ホストの時刻の平均値で同期が行われるので協定世界時とはズレが発生する
• さすがに最大 100 台は修正されたがマスターがすべてのスレーブをコーディネートするのでスケールしない
• UDPブロードキャストオンリーなので今の時代だとルーターも超えられない
• 現状 2038 年問題があり改修が必要となる

これで使いたいやつおるか────？

よって O では 2011 年に削除 し F も 2018 年に削除 しており、まだ残ってるのは N だけである。 きっとあれだ macOS の例をみるに無知な若者が名前被りやらかさんよう残しておくべきなんだ(ガンギマリ)。

余談だが O のテオ閣下の差分だけど date(1) から nflag 消すのはいいけど -n 自体を消すのは後方互換的にアレよね。 シェルスクリプトで呼んでたりすると誤作動するから普通は -n を受けつけるけど何もしないって実装にするのだ。

なお F でもワナ氏が やらかして 後で 直してる 、まぁ -h/–help やマニュアルからは -n 消してもいいと思うんだが。

それと前述の /usr/include/protocol/timed.h ももう要らないと思う。

あと adjtime(2) の SEE ALSO から timed(8) と timedc(8) は消して構わんけど TSP のペーパーへの言及は消しちゃダメ、これも TSP の成果物なんだし。

ということでオレオレ N6 でも 消した 。

次回

長くなり過ぎたのでソースコード散策は回を分ける。 timed(8) の実装と adjtime(2) の実装を読むよたぶん。