- 投稿日:2020-08-04T23:54:12+09:00
64ビット整数の最大値は計算の限界ではない
はじめに
最近競技プログラミングを始めました。
普段の仕事で64ビットでは扱えないような天文学的な値や細かすぎる浮動小数点数に触れることって滅多に無いのですが、競技プログラミングではそのような機会がちょくちょくあります。
うまく回避する方法を検討するのも醍醐味ですが、初心者は巨大な値に慣れるところから勝負です。
今回は競プロ初心者として得た知見をメモします。数値型における64ビットの最大値は変数の限界であって計算の限界ではない
まずは下記のコードをご覧ください。
package main import ( "fmt" ) func main() { num := int64(9223372036854775808) fmt.Println(num) }最近は仕事でGoを書いているので競プロもGoで解いています。
これを実行すると下記のようなエラーが出力されます./main.go:8:14: constant 9223372036854775808 overflows int6464ビット符号付き整数配列の最大値は9,223,372,036,854,775,807なので整数オーバーフローが発生します。
では下記の場合は...?
package main import ( "fmt" ) func main() { num := int64(9223372036854775808 / 9223372036854775808) fmt.Println(num) }164ビットの最大値を超えた値同士の計算ですが問題なく1が出力されます。
これはどこまで値が大きくなっても最終的な計算結果が9223372036854775807以下であれば変わりません。
(常軌を逸した値同士を計算したら何か起こるかもしれませんが)※2020/08/05追記: Goの実装を漁ってみて確認しました13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095
(512ビットで表現できる値の最大値)まで対応しているようです。念のためC++でも書いてみましたが同様の結果でした
なおC++は9999999999999999999まで耐えましたが桁が増えるとエラーが発生しました...※2020/8/5追記: 嘘ですね、こちらも64ビット符号なしで表現できる限界である18446744073709551615まで計算可能です。
大きな値が扱えても2のN乗が閾値になる辺りからコンピュータがビットの塊である事が伺えます、面白いですね。#include <iostream> using namespace std; int main(void){ long long x = 9223372036854775808LL / 9223372036854775808LL; std::cout << x << std::endl; }結論
仮にbit値をbyteに変換して表示する下記のようなコードが64ビットの限界を超えて動かなくなったとします。(具体例としては少々苦しいですが)
package main import ( "fmt" ) func main() { bit := int64(9223372036854775808) byte := bit / 1024 fmt.Println(byte) }途中結果がオーバーフローするような巨大な値でも、変数に格納する前に必要な計算を実行するだけで動かせる場合があるという事です。
package main import ( "fmt" ) func main() { byte := int64(9223372036854775808 / 1024) fmt.Println(byte) }追記
Goはconstであれば64ビット以上の値も格納できるそうです。
@Nabetani さん、ご指摘いただきありがとうございます。
試してみたらconstも512ビットまで使えるみたいです。package main import ( "fmt" ) const huge0 = (1 << 127) - 1 const huge1 = 0x987654321abcdef0 func main() { v0 := huge0 / (1 << 64) v1 := huge1 / (1 << 16) fmt.Printf("v0=%x v1=%x\n", v0, v1) //=> v0:7fffffffffffffff v1=987654321abc }
- 投稿日:2020-08-04T07:53:51+09:00
分散システムにおけるScalableな名前付けアルゴリズム「Chord Protocol」を実装してみた
この記事はEnjoy Architectingからの転載です。
概要
分散システムを学術的に学びたくて、
Chord Protocolというアルゴリズムが面白かったので実際に論文を読んで実装してみました。
この記事では、分散システムにおける名前付けの概念と、Chord Protocolの紹介、簡単な検証について言及していこうと思います。
実際に作ったサーバ 分散システムにおける名前付けとは?
分散システムの分野には「名前」、「名前付け」、「アドレス」と呼ばれる概念があります。
それぞれどのような意味を持っているのでしょうか?名前付けと名前
分散システムはネットワークを通じてそれぞれのサーバ、プロセスが協調して動作しています。
この中で、各サーバ、プロセスはやり取りをする相手の「名前」を知らなければやり取りを行うことができません。
この名前の解決を行うことを「名前付け」と呼んでいます。
そして、あるリソース(特定のプロセス、サーバなど)を一意に特定するための文字列を「名前」呼んでいます。アドレス
名前が分かっていても実際にはそれだけではやり取りできず、実際には「アドレス」と呼ばれるリソースの住所に対してアクセスすることでやり取りが成立します。
つまり、リソースに対する実質的なアクセスポイントをアドレスと呼んでいます。
名前との違いは、名前は永続的にリソースを一意に特定するもの、
アドレスはアクセスするために必要な実際のリソースの住所、つまり位置情報を持っているということです。
名前は永続的に同じリソースを指し続けるのに対し、アドレスはそのときリソースが存在する位置によって変化します。具体例
ドメイン名(example.com)が「名前」、example.comに紐づくAレコードのIPが「アドレス」に当たります。
ドメイン名はずっと変わりませんが、IPアドレスはサーバを移管したりすることで変化することがありえます。
永久に同じリソースへのポインタになるのでドメインは「名前」として成立するわけです。Naming Serverとは?
名前からアドレスを解決したり、特定のリソースに名前をつけてくれるサービスのことをNaming Serviceと呼びます。
一番わかり易い例としては、DNSが挙げられます。
DNSは、ドメインという名前からIPというアドレスを解決し、またIPに対してドメイン名をつける名前付けを行うことで成立しています。代表的なアルゴリズム ~Consistent Hash~
名前付け、名前解決のためのアルゴリズムとしてメジャーなものにConsistent Hashがあります。
Consistent Hashは、
サーバの集合(以降各要素をノードと呼ぶ)に対してハッシュ関数で一意のID(たいていはホスト名などのハッシュ)を振り、
各ノードをID順に円状に並べ、
あるIDがどのノードに配置されるべきかを決定するアルゴリズムです。
与えられたID以上であり、値が一番近いノードに解決され、
円状になっているので、
仮にそのノードがいなくなったとしても次のノードに回されるといったように、ノード障害に強いアルゴリズムになっています。詳しくは、こちらがわかりやすいです。
コンシステントハッシュ法ハッシュによって名前付けを行い、
ハッシュによるIDから対応するサーバを解決して名前解決を行います。
(引用: https://vitalflux.com/wtf-consistent-hashing-databases/)Consistent Hashの拡張、Chord Protocol
前述のConsistent Hashは完璧ではなく、欠点があります。
それは、ノードの離脱、ノードの参画がいつ起こったとしても、
ただしい結果を返し続けるためには一つのノードは、参加している他のすべてのノードの状態を把握している必要があることです。
(そうでないとノードが増えたり減ったりした時点で正しく結果を返すことができなくなる)
これは大規模な分散システムになればなるほど、大きな課題になりえます。
大規模なノードの集合では各ノードは他のノードの情報を保持するために大規模なリソースを要求し、また、ノードの参加、離脱時の情報更新などの計算コストも高くつくことになります。
これを解決するべく生まれたのがChord Protocolになります。基本的なアルゴリズムは下記の資料がとてもわかり易くまとめられています。
Chord Protocolは何が優れているのか?
基本的なことは上の資料がとてもわかり易いので、ここではかいつまんで何が優れているポイントなのかを説明しておきます。
乱暴にいってしまえば、
- 経路表による高速な検索
- ノード参画、離脱時に各ノードが独立して経路表を更新する仕組み
- 経路表が最新化されていない場合のためのFallback手段としてのSuccessorList
が主なポイントになります。
これらのポイントにより、耐障害性を担保しつつスケーラビリティを向上させることに成功しています。
順に追っていきましょう。経路表による高速な検索
各ノードは、全てのノードの状態を維持する代わりに、一定サイズの経路表をメンテナンスします。
例えば、32ビット長のハッシュをIDとする場合、32個の行数を持つ経路表を持ち、
この表を元にして、他ノードにルーティングして検索します。
計算量はO(logN)になり(Nはノード数)、これによって大幅にスケーラビリティを担保できるようになります。ノード参画、離脱時に各ノードが独立して経路表を更新する仕組み
Chord Protocolでは、ノードの参画、離脱時に各ノードがそれぞれ安定化させるためのルールを規定しています。
このルールに従った非同期プロセス、ないしスレッドが一定間隔で動作していて、経路表のメンテナンスを行います。
このメンテナンスは、ノードの離脱、参画に対して、メッセージ数がO(log^2N)程度で、そこそこ高速に実行されます。経路表が最新化されていない場合のためのFallback手段としてのSuccessorList
ノードが参加した直後などは当然経路表は最新化されていません。
よって一時的に正しい結果を返せない可能性もあります。
そこで、この資料のスライド131ページあたりに記載されているように、
Successor Listというリストも保持しておき、経路表による検索に失敗した場合はこのリストを使ってFallbackすることができます。実際に実装してみた
ここまでがNaming Service及び、Chord Protocolの説明でした。
今回は、これをもとに実際にNaming ServiceをGoで実装してみました。
Goで書いたChordの参照実装なので名前はgordです。(安直)https://github.com/taisho6339/gord
gordの概要
これはどういう実装かというと、
GordがChord Protocolのノード郡を管理するためのプロセスとして常駐し、
別途ストレージを管理するソフトウェアがgRPCでGordに対してアクセスし、
特定のキーがどのノードに存在するかを検索したり、
自分たちが管理するべきキーを判別したりする、といった機能を提供します。
k8sであればサイドカーとして各Podにくっついているイメージになります。
この構成は実際に論文でもサンプルとして提案されている構成になります。
論文で提案されている構成
実際に落とし込んだ構成 実装に対する検証
実際に実装に落とし込んだところで、ちゃんと実装できているのかを検証したいと思います。
機能的な観点は、単体テストにて実装しているので今回はパフォーマンス、耐障害性について検証してみます。
ただし、ローカルマシンでの検証につき、プロセッサ数に限度があるため、
お遊び程度の検証しかできないのはあしからず...パフォーマンスに関する検証
探索のパフォーマンスを測定してみます。
ノード数を1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024と増やしていったときに特定キーの検索にかかる時間を計算してみましょう。
すでにStabilizationを完了したノードを指定数用意し、検索のパフォーマンスの違いを見ていきます。
実験にした私のマシンは下記のスペックになります。
OS: MacOS Catalina 10.15.5 プロセッサ: 2.4 GHz 8コア/16スレッド Intel Core i9 メモリ: 64 GB 2667 MHz DDR4結果はこんな感じになりました。
ノード数 検索にかかった時間 1 20.1 ns/op 2 4440 ns/op 4 4450 ns/op 8 4644 ns/op 16 4644 ns/op 32 6473 ns/op 64 19778 ns/op 128 25808 ns/op 256 35940 ns/op 512 35825 ns/op 1024 36940 ns/op ローカルマシンでの検証なので32ノード以上になってくると、
ノードが実行している大量のゴルーチンを限られたプロセッサで共有せざるを得なくなってくるため、アルゴリズム以外の要因で遅くなっていそうです。
少なくともノード数によって線形に増加している傾向は見られませんでした。耐障害性に関する検証
docker-compose build && docker-compose up gord1_1 | time="2020-07-22T06:59:08Z" level=info msg="Running Gord server..." gord1_1 | time="2020-07-22T06:59:08Z" level=info msg="Gord is listening on gord1:26041" gord1_1 | time="2020-07-22T06:59:08Z" level=info msg="Running Chord server..." gord1_1 | time="2020-07-22T06:59:08Z" level=info msg="Chord listening on gord1:26040" gord1_1 | time="2020-07-22T06:59:09Z" level=info msg="Host[gord1] updated its successor." gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Running Gord server..." gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Gord is listening on gord2:26041" gord3_1 | time="2020-07-22T06:59:09Z" level=info msg="Running Gord server..." gord3_1 | time="2020-07-22T06:59:09Z" level=info msg="Gord is listening on gord3:26041" gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Running Chord server..." gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Chord listening on gord2:26040" gord3_1 | time="2020-07-22T06:59:09Z" level=info msg="Running Chord server..." gord3_1 | time="2020-07-22T06:59:09Z" level=info msg="Chord listening on gord3:26040" gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Host[gord2] updated its successor."すぐにStabilizerがノード間連携をし、経路表を更新することでどのノードも一貫した結果を返しています。
grpcurl -plaintext -d '{"key": "gord1"}' localhost:26041 server.ExternalService/FindHostForKey \ && grpcurl -plaintext -d '{"key": "gord1"}' localhost:36041 server.ExternalService/FindHostForKey \ && grpcurl -plaintext -d '{"key": "gord1"}' localhost:46041 server.ExternalService/FindHostForKey { "host": "gord1" } { "host": "gord1" } { "host": "gord1" }つぎに試しに1ノード退場させてみます。
docker stop 1a3bf85b693b gord3_1 | time="2020-07-22T07:04:43Z" level=error msg="successor stabilizer failed. err = &errors.errorString{s:\"NodeUnavailable\"}" gord2_1 | time="2020-07-22T07:04:43Z" level=warning msg="Host:[gord1] is dead." gord3_1 | time="2020-07-22T07:04:43Z" level=warning msg="Host:[gord1] is dead." gord_gord1_1 exited with code 0すぐにノードのダウンを検知し、更新に入っています。
grpcurl -plaintext -d '{"key": "gord1"}' localhost:36041 server.ExternalService/FindHostForKey \ ✘ 1 && grpcurl -plaintext -d '{"key": "gord1"}' localhost:46041 server.ExternalService/FindHostForKey { "host": "gord2" } { "host": "gord2" }ノード1がダウンしてもすぐに経路表が更新され、さらにノード1に本来属していた"gord1"というキーが別のノードに移っていることがわかります。
まとめ
実際にChord Protocolを実装することで、
実装としては、未熟な点やバグなど残っていると思いますが、何が優れていて、既存の手法とは何が違うのかを実際に理解することができました。
また付加価値として256ビットにもなる大きな数値をGolangでどう計算するのか、
Golangでの並行処理についても勉強することができました。
こういったことが直接お仕事の役に立つケースは多くはないかもしれませんが、実装力のレベルを一段引き上げてくれる良い機会になり、楽しむことができました。
今度はもっと身近なOSSなどで利用されているアルゴリズムなども実装してみたいと思います。