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

そういえば、プログラミングにおける「式」って英語だとexpressionだよな。formulaでなく。「表現」と訳した方がいいような。なんで「式」なんだろ。

A. C#とJSが最近は多いですかねえ。C#はWindows環境でアプリを書くにはライブラリが充実していますし、強力な補完や豊富な構文でサクサク書けていいなあと思います。あと拡張メソッドが好きです。でJSは、というかWebAPI触れると、UserScript等でQoLを上げられるのでお勧めです。どうせ常時起動してるブラウザで手軽に実行環境が用意できるのも便利。それはそれとしてRubyのSymbolとかF...(続きはリンク先で)
#quesdon https://quesdon.rinsuki.tk/@unarist@mstdn.maud.io/questions/5a30107ad6b812000108375d

前ににさおん先生もTwitterかここで書いてたけど、人気とは「人(ヒト)の気(キ)」だからやっぱり前面にいる人の印象だよなー。

知ってる人が前にいると、イベントの内容はともかく顔を出してしまうし、逆にイベントの内容がよく考えられていても知らない人の主催だと「怪しそう」と思ってしまう。

棚橋選手も著書で知られることがプロモーションの一歩と記している。この辺、にさおん氏の洞察力の鋭さを感じる。

タミヤ のシャーマンはこれで全部組み終わりましたん😌

残りはアスカ (右)とイタレリ (中)とアカデミー(左)

アスカは組立て楽しみ〜😁
イタレリとアカデミーはどうなんだろうな〜

アカデミー(左)成型色がミドリだよ...

シャーマン5台目😂
M4A3 105ミリ榴弾砲
3枚目の写真はM4初期型とツーショット。複雑な面構成の初期型車体と洗練された後期型車体。
似てるようで全然別物なんですなぁ〜

今年の漢字は「北」　その理由は「北朝鮮」に加えて
http://www.asahi.com/articles/ASKDD4J9FKDDPLZB00K.html

でもって #今年の漢字 は「北」ですか。ふうむ。🤔

久しぶりにちゃんと描いたので進捗上げさせて
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