クマノテツ @kumanotetu@mstdn.mini4wd-engineer.com

久しぶりにちゃんと描いたので進捗上げさせて
https://under-bank.blue/media/XUgQdntvMXno0IgIPDA

Mastodon 2 Advent Calendar 2017, 12日目の記事です.
最初はGNU Socialの思想とかいった話を書こうと思っていたのですが, 今あるバグ修正で詰んでいるのでそれについて解説します. 熱しやすく冷めやすい猫なんです.

# だれ?
猫です. Mastodonにコードをちょっと貢献しています. その派生であるPawooとPawoo Musicにも貢献していますが今回この2つの派生はあまり関係がありません.

# Snowflake
雪です. この季節にはうってつけですね. 私は外では耳が寒くなるために出たくないので縁がありませんが.
SnowflakeはTwitterで用いられている, 投稿につけるIDの生成アルゴリズムです. Snowflakeによって生成されたIDは次のような特徴を持ちます:
* 投稿を一意に特定できる (IDなので当然ですね)
* ある程度予測が困難である
* 時間に対して単調増加であり, 一定時間ごとにある程度間隔がある数値である
* IDから投稿の総数を推定できない * 64ビット以下である

Twitterの場合, これには次のような利点があります:
* 時間ごとの間隔を活用することで, ロックなしでサーバー間でのIDの衝突を回避できる
* セキュリティの強化

Mastodonの場合, これらの特徴により次のような利点を享受できると考えられました.
* 連合を通して過去の投稿を受け取った場合, 時間に対応したIDを付与し, ソートに用いることができる
* セキュリティの強化

連合を通してかなり前の投稿を受け取るということはありうることです. 例えば, あるインスタンスで誰にもフォローされていない人の投稿がブーストされて転送されてきたといった場合です. そのインスタンスはブーストを受け取った時初めて投稿を受け取り, IDを割り当てますが, 実際に投稿されたのは1か月前かもしれませんし, 1年前かもしれません. こういったものに時系列に従ったIDを割り当てたいという要求が存在します.
また, セキュリティは言わずもがなです. 単なる投稿インターフェイス以外にも, 連合を経由して投稿を受け取るMastodonの場合では, 攻撃対象領域が広くなります. これらのインターフェイスは標準化されているものもあり, 隠蔽することもできません. このような状況で少しでもセキュリティを強化したいというのは当然のことです.
さて, Snowflakeはこれらの問題を解決する救世主たりうるのでしょうか?

# アルゴリズム
まずこれから紹介する疑惑に向き合う前に, Snowflakeの *本来の* アルゴリズムを紹介します. Snowflakeはビットの位置で次の3つに分けることができます.
* マシンごとの連番
* マシンID
* 時刻

ここで, 時刻は最上位に位置します. これにより, IDは時系列に並ぶことになります.

次に, マシンごとの連番とマシンIDです. 連番はマシン, 時系列, データの種類によって異なるシードと, 各々のマシンが持つカウンタを加算することで決定しています. このシードによりIDは予測不能になります.
ところで, 連番といってもここで保存できるビット数は16ビットやそこらです. 全ての投稿にカウンタの値をそのまま用いていたら当然収まりません. そのため, このカウンタは循環するようになります. 比較的長い時間で循環していても, IDには時刻がついているので, 同時に循環が発生するほど大量の投稿がされないかぎりIDの衝突は起きません.
そして, マシンIDはマシン間のIDの衝突を防ぎます.

こう見てみると, 組み込み機器や言語インタプリタにような性能が重要になってくるシステムでよく見られるような, ビット演算を用いたテクニックに過ぎません. Snowflakeはこの簡潔さが売りのようです.

では, これをMastodonに応用してみましょう. 現状, Mastodonは1つのマシンがデータベースを維持するようになっているので, マシンIDは不要になります. つまりIDは次のもので構成されることになります.
* 連番
* 時刻
とても簡単ですね. 実際には連番は0から15ビットまでの16ビット, 時刻はミリ秒で16ビットから63ビットまでの48ビットで格納され, 計64ビットとなっています.

# 課題: 過去の投稿に対し時間に対応したIDを付与できるか
さて, 過去の投稿に対し時間に対応したIDを付与するというのは, 実はSnowflakeにおける前提の1つを破綻させています. 連番の整合性です. 先程, カウンタは循環しても時刻がついているため, その時刻において循環が発生しなければ問題ないと言っていました. しかし, 過去の投稿を扱うことで, 次の2点間で循環が発生してはならないということになります.
* 実時刻がその時刻になった時点
* 過去の投稿にIDを割り振る時点
1年前の投稿を受け取った場合, 1年間の間で投稿が16ビットに収まる量, つまり65,536件以下でなければならないということです. これは成り立ちません.

## 解法1: 乱択
ではどうするか, Mastodonの場合は過去の投稿に対するIDは乱択によって付与しています. そうなると非常に小さい確率でIDが衝突します. 現状, そのような場合には単に投稿の保存が失敗します.
もっとも, 非常小さい確率といっても, 1ミリ秒以内に同時に行われた投稿の数が限られていることを前提にしています. ある時刻を示す投稿を大量に送ることによってDoSを引き起こす誕生日攻撃が成立するかもしれません. 攻撃に必要な投資はかなり大きいものの, 攻撃の成功確率が次第に上昇するので見返りも大きいでしょう.

## 解法2: 既にある投稿のIDから連番で次のIDを決定する
カウンタが循環していて使えなくても, 既にある投稿のIDに1足せば次のIDを決定できるはずです. 乱択とは違って衝突が起きる可能性は65,536回投稿するまで0です.
でもこれはこれで問題があります. まずその時刻の投稿に対しデータベース上でロックを書ける必要がある点です. 実装が難しく, また, 本来TwitterがSnowflakeで目的としていた, ロックレスで最高のパフォーマンスを得るというのは不可能になってしまいます.
セキュリティにおいても「完璧」とは言えません. 過去の投稿に対してIDが予測可能になってしまうからです. 「過去の投稿」と言うと限定的に聞こえるかもしれませんが, 投稿の発信源より少しでも早いインスタンスを用意できれば「過去の投稿」に見せかけることは可能です. 投稿の発信源に対しDoS攻撃を行い, タイムラグを発生させればIDを予測することは可能でしょう.

# 結局どうなの
ここまでで述べたように, MastodonのIDの実装は「マシンごとの連番」, 「マシンID」, 「時刻」の3つからなるSnowflakeの構造からは逸脱しており, 「ロックなしでIDを生成する」という目的も失われ,「過去の投稿に対し時間に対応したIDを付与する」という異なる目標が設定されています.
そのために, Snowflakeを単に導入するだけでは解決できない問題が発生します. 連合があるMastodonではさらなる工夫と, 場合によっては妥協が求められるのです.

# クリスマスまであと13日
アドベントカレンダーはまだまだ続きます. 明日, 13日は墓場人夜さんの『ココミネココナの死』です. 私も楽しみにしています.

# 参照
Mastodon 2 Advent Calendar 2017 - Adventar https://adventar.org/calendars/2265
twitter/snowflake at snowflake-2010 https://github.com/twitter/snowflake/tree/snowflake-2010

さらにつづき。

とかいうことを考えてしまうと、一般参加者としてイベントに参加してても、何か色んなコトを考えてしまい。こないだの武道館でも、一糸乱れず揺れ動くサイリウムを見ながら「果たして彼らにとってステージ上の彼女はナニの対象なのだろうか……《崇拝》という言葉が正しいだろうか……」とか考えたりしたりして。

38歳の一年は色々踏み外したりコケたりしたけど、失敗から学べることほど大きいものはないので。練習通りの成功を積み重ねたところで、それは予定調和を反復したにすぎない。コースから外れてスッ転がって、這い上がるときにこそ力は発揮されると信じてます。

39歳は、さらにアグレッシブに、無遠慮に、偉い人を怒らせることを恐れずに、同人ライトノベルと同人ボイスドラマ、さらにその先の未知なる楽しさを目指して行きますので、ひとつよろしくお願いします。

2017.12.12 バーニーにへい

おっでっんー

イグレス完成
https://mstdn.mini4wd-engineer.com/media/C1qvH9yMIF-hEhZQL5A

おつまみ🐮 https://mstdn.jp/media/LQ74rGztHNrF7sVt36M

ニコニコ別にままで通りでも気にしなかったんだけど、最近の動きを見ていると
・ユーザーに文句言われるまで問題を自覚していなかった
・ユーザーに文句言われたらある程度すぐに実装できることがあった
って言うことが露呈してしまってちょっと。。。

ここでだけ第一次中間報告。

デクロスとラウディーブルの一騎討ち。マンガ原作ではないタミヤオリジナルデザインが抜け出てきて嬉しい限り。 https://mstdn.mini4wd-engineer.com/media/Bk0KVDUkyeeHzlqoFQQ

そうか、わたしはマイニングではなく、まいっちんぐを求めていたのか。

そういえば真夜中に作ってそのままだったので適当に投げてくだち

https://quesdon.rinsuki.tk/@rk_asylum@under-bank.blue

ギネスをたんたんと
#beer #びいる
https://mstdn.beer/media/DS3swnrfLk-SLIZuAmc

見ようと思えば見られるけど他愛もない話みたいな

そっか、未収載(unlisted)って公開トゥートとTwitterでいうtosの中間くらいな用途なんだ自分の認識だと

ソーセージ https://mstdn.jp/media/ejj1jOjJzBrJn-V7Gl4