分散アルゴリズム:タイミングとは : 超入門

1.  この記事で書くことは何?


 この投稿では、2021 年のアドベントカレンダー用に書くので、前後の投稿とは関係なく前後のコンテキストがわからなくても読めるように書こうかと思っています。もしかしたら、この投稿がこのBlog の初投稿になっているかもしれません。
 本投稿では、分散システムはそんなに詳しくないけど、ちょっと興味があるって人が、分散システムに入門できればと思って書いています。分散アルゴリズムの基本は案外簡単でもある事を知ってもらい、その応用アルゴリズムの理解に役立てばと思います。入門にあたり、重要となる考えに時間の概念があります。この記事内では、特に分散システムの時間に関して書いていこうかと思います。分散アルゴリズムの基本的な概念はとてもシンプルですので、分散アルゴリズムを難しそうに思わなくなる人が増えればと思います。

2.  背景

 分散システムは、我々の社会で至って普通に利用されているシステムの一つです。
 分散システムという分野は、コンピュータの歴史では比較的歴史の古いものひとつです。コンピュータは、単一の巨大な大型でパワフルな計算機に集中的に計算する時代を経験したり、それらを低価格で実現できるように等の理由により並行処理ができるようにしてみる様な時代を経験してみたりを繰り返しながら進化を続けています。計算機を複数利用することで、システムを機能単位でモジュールを分割することができたり、大きい計算量のある処理を分割・並行処理を行い計算時間の短縮が得られるメリットがあります。
 一方で、複数の機能群や計算機群の中で一つでも故障する事で、全てが利用できない様な状態は困ります。分散システム内の一部が故障しないようにする・故障してもシステム全体としてはサービス可能な構造を作る方法も様々なアプローチがあります。故障を管理するための計算機を用意するのもひとつの方法です。しかし、故障を管理するためのシステムが故障すると故障が管理できないなどのSinglePointOfFailure があります。自律分散システムでは、この様に単一の故障管理機構を利用することなく、システムが自律的に故障とうまく共存ししながら、目的とするサービスを提供し続けることを目的とします。もちろん、システム内の一部が故障した場合には、パフォーマンスの低下や一部の機能が利用できなくなるなどのちょっとうれしくない点はあるかもしれません。
 この様に、分散システムでは、複数のサブシステムであったり、計算機群が存在します。この様なシステム内では、時間を管理することは重要な要素のひとつになります。この記事では、次のような内容を書いていきます。

    • 分散システムってどんなもの?
    • 分散アルゴリズムにおける時間とは?
      • 物理時間
      • 論理時間: 特にLamportClock

 3.  分散システム・自律分散システムとは

 この章では、本記事で利用する分散システムとはどの様なものなのかを定義します。まずは、簡単に分散システムとはどのような物なのかを簡単にイメージしてみて、詳しい定義をしてみましょう。

3.1.  分散システムってどんなものがある?  
 現在、一般的に利用されているシステムの多くが何らかの分散システムの一部であると言えます。

 シンプルな例の一つとしては、電波時計やGPS を用いた時計の同期があります。電波時計の電波塔であったり、GPS システム側では、常に正確な時を刻み続け、定期的に時報を電波に載せて配信します。電波時計の受信機である電波時計そのものは、時報の電波を受信し、受信情報を基に自身の時計を調整し、ユーザに時を提供します。しかし、電波塔に障害があった場合には、分散システムとして機能することができないため、自律分散システムとは言えません。
 IoT 機器を使ったシステムの分野にも分散システムは多いです。IoT システムでは、IoT デバイスを用意し、IoT デバイス同士の通信や通信インフラを使って通信させればいいので、準備が非常に楽になります。IoT デバイスがない場合には、センサなどのデバイスだけではなく、電源や通信などの配線等までも用意する必要があります。場合によっては配線することがとても現実的ではない場合も考えられます。IoT システムの例として、農業などで利用するセンサと、センサデータを収集してデータを利用するようなシステムも、クラウドサービスの一部になるかもしれませんが、分散システムと言えます。
 群ロボットシステムは、複数の小型のロボットを利用して、ひとつのタスクを処理しようとするシステムです。複数のロボットなどを利用して一つの処理をこの様なシステムも分散システムといえます。従来は、一つ以上の大規模で高価なロボットシステムを導入してひとつの処理をしていましたが、単体のロボットに複数のタスクを実行させるためには、ロボットシステムそのものが複雑になり高価なものになります。群ロボットシステムでは、そのような問題点を解決するために、前述のような大規模なロボットよりもシンプルな作りのロボットを複数用いることで代用します。近年では、ドローンなどを複数用いて様々なことを行うシーンもありますが、複数のドローンを用いる場合も場合によっては群ロボットシステムと同様に扱うことができます。
 IoT 機器や群ロボットシステムにおいて、群を制御する方法として、特定のサーバを用意してデバイスのみを分散させる方法も考えられます。システムの構造はシンプルになりますが、成業するためのサーバが故障するとシステム全体が利用できなくなります。一方で、IoT 機器やロボットが独自のメカニズムにより各々が制御することでシステムの提供を行うような手法も考えられます。メカニズムは複雑になりますが、特定のサーバなどが故障することでシステム全体が故障することは有りません。このように、システムを構成するサブシステムが独自のメカニズムで制御するシステムを自律分散システムとよびます。

 以上のように、分散システムは様々なシーンで利用されています。上記以外にも、様々な分野で幅広く利用されており、これって分散システムかな?って感じるものは大概分散システムと言って問題ないくらい幅広いものです。

3.2  ざっくりと、分散システムってどんなもの?
 前節では、分散システムにはどのようなものがあるかを考えてみました。本節では、前述のような分散システムがどの様な要素で構成されているかをもう少し掘り下げて考えてみようかと思います。とはいえ、表面を触る程度で、深いところまでは考えません。

 時計の同期システムでは、正確な時間を発信するGPS や原子時計を有する設備と受信する機器及で構成され、設備と機器の間では電波やインターネット等の通信を用いて時間の同期を行います。
 IoT システムでも、IoT デバイスがセンサ等を用いて情報を収集します。収集されたデータは、通信を用いてサーバや他のIoT デバイスに収集されます。収集されたデータは、加工や解析をされ、収集してきたセンサや他のセンサの制御に用いられたり、他のサービスに用いられます。IoT サービスで用いられるサーバは、単に単一のサーバを示すことも多いですが、クラウドシステムに繋がり高度な解析や制御を行うこともあります。本投稿では触れていませんが、IoT システムも、クラウドシステムのサブセットと呼んで良いのではないかと思います。
 群ロボットシステムも基本的にはIoT デバイスと同じと考えられます。ここでは、群ロボットシステムは、IoT システムにおけるIoT デバイスがより高性能かつ高機能なものに置き換わり、かつ、IoT デバイスが物理的な移動を行うようなモバイルロボットで構成されるシステムであると考えます。群ロボットシステムを構成する各ロボットは、サーバに制御されることもありますし、データを独自に処理自律的に制御するような場合もあります。

 以上のように、分散システムは様々なシーンで利用されています。各サービスにおいて、一つのサブサービスが故障することで、サービス全体が利用できないのではユーザはみんな困ります。分散システムでは、一部のサービスやサーバが故障したとしても、何らかのパフォーマンスが劣化したとしても、全体としてサービスは提供され続ける事ができる状態が重要になります。分散アルゴリズムを考える上で、部分的な故障がシステム全体に影響しないように気をつけることが重要です。
 
 
3.3 分散システムを簡単に定義
 前述では、分散システムの例を上げました。実際に、分散システムがどのようなものであるかを、本設ではもう少し詳しく定義しておきます。

 本投稿で記述する分散システムを構成する要素は、アプリケーション、アプリケーションを処理するためのノード群、ノード間でメッセージを交換するためのネットワークがある。
 アプリケーションとは、前述の時間同期であったり、IoT システムの使いみちであったり、群ロボットシステムを用いて達成しようとするタスクなどを示します。アプリケーションを処理するためのノード群には、時間同期システムを構成する発信側・受信側の両方を構成するノードを示します。IoT デバイスでは、IoT デバイスそのものもありますし、サーバ側にあるサーバであったりクラウドシステムを構成するサーバ群を示します。群ロボットシステムでは、システムを構成するモバイルロボットやサーバが存在する場合には、IoT システム同様にサーバも含めます。以上のことから、ノードとは、CPU などの計算機能・メモリやストレージなどのデータを管理する機構・他のノードと通信するための通信機器は最低限含まれます。最後に通信は、お互いにメッセージ交換が可能となるネットワーク及びプロトコルを意味します。通信は、ノード内での処理に対して十分に大きいタイムラグが有ることが考えられます。また、誰が誰にメッセージを送ったのかが分かるように、お互いが識別できる機構も持ち合わせています。ID などかもしれませんし、IP などのアプリケーションよりも深いレイヤのものを指すかもしれません。

4.  分散アルゴリズムとは
 分散アルゴリズムとは、分散システムを構築する上で、ノード間の強調を実現するための手順の事を意味します。(とてもシンプルに書いてしまいましたが・・・)

章にするほどでもなかったwwww


5.  分散アルゴリズムにおける時間とは
 分散システム内において、ノード間の協調は、通信を用いたメッセージ交換で行われる事は前章で記述しました。

 通信によるメッセージ交換にかかる時間は、ノード内で行われる諸処理に対して十分に大きい物になります。分散システムにおいて、各ノードはシステム全体を意識する必要はなく、外部からモニタすることでのみ分散システムの状態を把握することができる前提とします。分散システム内では、頻繁にメッセージの送受信が発生するので、メッセージの送受信などのイベントの管理は非常に複雑になることが多いです。分散システム内において、イベントの発生順序をトレースすることは、システム内の状態を把握するためにも重要な要素のひとつになります。単一のノード内で逐次的に処理される様なシステムの場合には、イベントの発生順序が決定的なものとして扱うことができます。一方で、分散システムや並行システムの場合には、イベント発生の順序を決定することは、逐次処理の様には行かないことが多いです。(並行システム・並列システムとは、単一のノードで処理をすると計算時間やメモリなどの制約により、処理が困難な場合やパフォーマンスを向上させたい場合に、処理対象の問題そのものや入力などを小さい単位に分割し、同じようなロジックを利用して並行で処理をし、結果を収集し最終結果とするようなシステムを指すことが多いです。)

 イベント発生の順序を決定する一つの方法に、イベント発生時間を利用する方法が考えられます。分散システムにおける時間とはどのようなものでしょうか?時間を刻む最も身近な物に、時計が挙げられます。前述のような時間同期サービスなどが利用する時計を用いた時間の事を、物理時間と呼びます。

5. 1. 物理時間
 物理時間は、前述の原子時計の例に挙げられるように、我々が日常で利用している時間概念を利用します。分散システムを構築するノードすべてが全く同じ様に時計が進むとは限りません。IoT デバイスなのでは、各ノード上のプロセッサの処理速度に微妙な誤差がある場合もあり、長時間の運用を行っていると、微妙な誤差の積み重なりで大きな差を生み出す場合もあるため、時間の同期が重要となります。
 大きなコンクリート構造の建物内や地下などでは、電波時計の同期電波や、GPS の電波は利用できない場合もあるため、別途インフラを用意する必要が発生する場合もあります。また、NTP などのネットワークを介した時間同期の場合にも、時間のゆらぎが若干発生することもあります。



 図は、インフラを利用した時間同期を利用しているある分散システムのイベントの発生をトレースした図です。一番上から時間軸、ある分散システムを構成するノード (node1, node2, node3 ) 、時間同期サービスを示します。横方向への時間軸とします。各ノード上の時間軸上に黒丸のイベントがあり、それぞれe1_1, e2_1, e1_2, e2_2, e1_3, e2_3 があります。各イベントは、何らかの計算処理かもしれませんし、ディスクI/O、NetworkI/O などの場合もあります。時間同期サービス (time synchronization service ) は、時間T0 で、各ノードに対して時間同期シグナルを送り、各ノードはT0_1, T0_2, T0_3 でT0 として同期します。
 イベントの発生順序は、イベントをex_n, ey_m とした時に、 ex_n <  ey_m と表記し、ex_n が先に発生し、ey_m が後で発生したことを意味します。
 前述の通り、各ノードでの時間T0_1,  T0_2, T0_3 の時間にはネットワークや電波の伝搬などのゆらぎがることにより、若干のゆらぎが存在します(T0_1 ≠ T0_2  ≠  T0_3)。分散システムの特性上、各ノード上でのT0 の大小関係を各ノードで判定することはできません。この様な前提の下、各イベントの発生タイミングの前後関係を表現できるでしょうか?
 各ノード上のイベントに関してはe1_1 < e2_1, e1_2 < e2_2, e1_3 < e2_3 であることは同一ノード上で発生しているので理解することができる。では、e1_1 とe1_2 や、e1_1 とe2_3 はどちらが先に発生しているのでしょうか?時間同期システムの同期精度が強固である場合には、e1_1 <  e1_2, e1_1 < e2_3 であると言えます。しかし、時間同期システムの同期精度のゆらぎが大きい場合には、e1_1 < e2_3 はおろか、e1_1 < e1_2 も保証できない場合があります。

 もちろん、とても高額にはなりますが、各ノードに原子時計を設置するなんてことも可能は可能です。原子時計を利用する場合には、時計の同期精度がとても高いため、イベントの発生タイミングは完全に保証することができます。

6.  LogicalClock (Lamport Clock )
 LogicalClock とは、分散システム内におけるイベントの発生の因果関係に関する順序を明確にするための手法の一つです。物理時間では、原子時計の時間の進み方を基本とした時間を意味しました。LogicalClock では、分散システム内で離散的に発生するイベントの因果関係を扱うことでシステム内の振る舞いを刻みます。前提として、各々のノードは、他のノードの内部状態を確認することはできないものとした時に、各ノード間でのコミュニケーションはネットワークを介したメッセージのやり取りのみで行うことでできます。LogicalClock では、TimeStamp の概念を上手に利用することにより、分散システム内で発生するイベントの因果関係を扱います。TimeStamp を利用するLogicalClock にも複数の方法がありますが、最もシンプルな物にLamportClock があります。

6.1.  LamportClock
 LamportClock とは、L.Lamport が最初に提唱したLogicalClock の一種です。下記の図は、ある分散システムも外部からモニタリングしたとして、発生イベントを記録したものとします。

 図の一番上は、時間軸を示しています。node1, node2, node3 は、分散システムを構成するノード群とします。イベントa, b, c, d, e, f は、node1 上で発生するイベントを示します。同様にイベントg, h ,i, j, k は、node2 上で発生したイベントを示し、イベント l, m, n , o, p, q は、node3 上で発生したイベントを示します。また、イベントa, h, n は、メッセージの送信イベントを、イベントg, c,  j, p は、メッセージの受信イベントを意味します。その他のイベントは、メッセージの送受信は関係ないイベントを意味します。
 イベント(a, b) は、同一ノード上で発生しているイベント同士なのでイベントの発生順序が a < b であることは解ります。また、イベント(a, g ) は、同一メッセージの送受信の組であるため、イベントの発生順序が a < g であることも解ります。では、イベント(b, m) や、イベント(b, k ) は、どちらが先に発生しているのであろうか?
 イベントの順序を決定する前に、イベントの種類を分類します。LamportClock では、次のようなイベントを、send, receive, event の3 種類に分類されます。send では、ノードがメッセージを送信した事を意味するイベントです。receive は、ノードが他のノードからメッセージを受信したことを意味するイベントです。最後のevent は、send でもreceive でもない、ノード内で発生したメッセージの送受信に影響しないイベントを意味します。
 それでは、イベントの順序を決定する方法を考えます。図は、前の図にLamportClock の振る舞いを図示したものです。


 ルールは、とても簡単です。

各ノードは、timestamp ts を持ち、初期値は 0 である
イベント x が、event の場合: ts += 1
イベント y が、send の場合  : ts += 1 を行い、send メッセージにts を付けて送信する
イベントz が、receive の場合:ts と受信メッセージに付けられたts を比較しを用いてts += 1 する

 各ノードは、timestamp ts が存在し、初期状態ではすべて0 とします。
 node3 上のイベント l は、evnet であるため、node3 上のts += 1 をおこない、ts = 1 となります。m も同様に event なので、ts += 1 とし、ts =2 となります。
 node1 のイベントa は、node2 に対してのsend イベントです。node1 は、 local のts = 0 に対してts += 1 をしたts = 1 がlocal の値になります。そして、ts = 1 をnode2 へのメッセージ内に入れて送信します。
 node2 のイベントg は、receive イベントです。node2 は、local nおts = 0 とメッセージに含められた送信側のts = 1 と比べ大きい方である ts = 1 に ts+= 1 をして、node2 のts = 2 とします。
 以上のようにtimestamp ts を繰り返すことで、LamportClock を形成して行きます。では、LamportClock をどの様に利用するのかを考えていきましょう。最初に書きましたが、LamportClock は、分散システム内のイベントの発生順序を扱うための仕組みです。
 まずは、同一ノード上で発生するイベントを見ていきます。node1 上で発生したイベントとtimestamp の組は、[(a, ts = 1),(b, ts = 2),(c, ts = 4),(d, ts = 5),(e, ts = 6),(f, ts = 7)] となります。LogicalClock では、timesamp ts が大きいほうが基本的には新しいイベントとしますので、(a, ts = 1) が最も古いイベントであり、(f, ts = 7) が最新のイベントとなります。ts = 3 がnode1 上には存在していないことが解りますが、(b, ts = 2),(c, ts = 4) の間には、少なくても一つの何らかのイベントがどこかで存在するという事がわかります。
 では、次に、ノード間でのイベントの順序を観ていきます。node1 の(a, ts = 1) とnode2 の(g, ts = 2) は、分散システム外部から観測した場合には、同一の送受信のメッセージで有ることから a < g となることがわかります。node1 の(a, ts = 1), (b, ts = 2) と、node3 の(l, ts = 1) , (m, ts = 2) は、どうでしょうか?LogicalClock では、物理時間は関係ありませんので、a < l, a < m かもしれませんし、l < a, m <a かもしれません。一方で、(d, ts = 5) , (p, ts = 6) を観てみます。前述の通り、node1 からnode3 へのメッセージの送信があるので、node1 とnode3 のLogicalClock の比較をすることができます。
 実は、LamportClock では、全てのイベントの発生因果関係を示しているわけではなく、送受信イベントのように因果関係のあるイベントの因果順序を追跡するために利用します。

 
4.  まとめ
 今回は、アドベントカレンダーに入れるので、この投稿だけで完結する内容として、論理時計のひとつであるLamportClock を紹介しました。LamportClock の考え方は、分散アルゴリズムを実現するために重要な概念のひとつになっていますし、多くのアルゴリズムの基本となっています。例えば、LamportClock を用いる様なアルゴリズムには、分散スナップショットや完全順序を必要とするようなアルゴリズムが挙げられます。完全順序を利用する有名なものには、ブロックチェーンなどの内部で利用されるような、合意問題の内部で利用されたりしています。とてもシンプルなものにも関わらずても重要なものに利用されていたりしますね。分散アルゴリズムの基本的なところは案外簡単なメカニズムで成り立っていることがわかってもらえ、興味を持ってもらえれば嬉しいです。

 アドベントカレンダーで、最近の自分の趣味である蜂蜜に関して書こうかとも思いました。しかし、蜂蜜のネタはまた別の機会にしようかと思います。蜂蜜そのものの話であれば、別のブログで書きますし、蜂蜜と技術的な話のハイブリッドであれば、ここに書くかもしれません。



コメント

このブログの人気の投稿

このBlog は何?