【感想】Linearizability versus Serializability

ということで、replicationを理解する前にconsistencyを理解する必要があると気が付きました。

Jepsenの各consistency modelの説明を読むにあたって第二層のlinearizabilityとserializabilityを初めに理解するのが良さそうというところまでは来た。

著者のPeter Bailisは第一層strict serializabilityの提唱者という認識。上記記事と元論文がすべてを言い尽くしているが、

• linearizabilityはCAPのC
• serializabilityはACIDのI

が最短の説明となる。また、

• linearizabilityの出自は分散システム
• serializabilityの出自はデータベース

である。出自の異なるこれらの特性を包括的に語るための生み出されたterminologyがstrict serializabilityであると理解した。自信はないが、システムパフォーマンスを語るときにresponse time/throughputをそれぞれ議論するようなものだと思った。本質的には出自の異なるこれらの特性を語るための理論がqueueing theoryであるという理解。

個人的にはlinearizabilityのほうが難しい。数学に疎いのでこれまた自信はないが、線形代数の線形と似た概念だと理解している。すなわちoperationが時間軸上で点として表現されるということだと理解している。しかし、これがCAPのCとどう関係するのかがわからない。

"This is the idea behind linearizability [6] (also known as atomic consistency [7], strong consistency, immediate consistency, or external consistency [8])."

via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html

linearizabilityの同義語多すぎでは…。

"the basic idea is to make a system appear as if there were only one copy of the data, and all operations on it are atomic."

via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html

あーなるほど。Figure 9-4がいままで読んだ説明で一番わかりやすかった。replicationの文脈ではlinearizabilityはwrite operationが時間軸上で点として表現されるゆえに全replicaに一瞬でデータがコピーされるようなconsistency modelということかな。すなわち全てのprocessからのread operationは必ず1つしかreplicaしか存在しないような振る舞いになる。ただし、invocation/completion timeについては何も言及していない。ACIDのIについても何も言及していない。

"In other words, linearizability is a recency guarantee."

via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html

ヤバいわかりやすすぎる。結局素直にDesigning Data-Intensive Applicationsを前から読むのが良いのでは…

"One way of electing a leader is to use a lock: every node that starts up tries to acquire the lock, and the one that succeeds becomes the leader [14]. No matter how this lock is implemented, it must be linearizable: all nodes must agree which node owns the lock; otherwise it is useless."

via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html

ここでlinearizabilityがleader electionに繋がってくるのか…感動がすごい。

"If you want to enforce this constraint as the data is written (such that if two people try to concurrently create a user or a file with the same name, one of them will be returned an error), you need linearizability."

via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html

linearizabilityはuniquenessにも使われている。
ビジネス要件やシステム要件によってはlinearizabilityより緩くconsistencyを管理して良いケースはあるだろうが、アプリケーションではなくDBMSで実装すべきだろうと思う。

"Similar issues arise if you want to ensure that a bank account balance never goes negative, or that you don’t sell more items than you have in stock in the warehouse, or that two people don’t concurrently book the same seat on a flight or in a theater."

via Check out this quote from Designing Data-Intensive Applications - https://learning.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/ch09.html

在庫や予約の一貫性にもlinearizabilityが使われる。

なお、CAPとACIDについてはこれらの記事に詳しかった。自分は用語を耳にしたことがあるだけで、全然腹落ちできてなかったとことに気がついた。

私なりに理解をまとめると、

• consistency modelを正しく理解することと、システム要件を正しく理解することが非常に重要
• consistencyの問題はアプリケーションではなくDBMSで解決するのが良さそう

あたり前のことしか言えてない…。

【感想】楠木建教授が伝授！「“秘孔”を突けば組織文化はガラリと変わる」

そもそも人にはできることとできないことがあって、普通の人ができないことをやってのけるのが本当のリーダーです。

https://diamond.jp/articles/-/262919?page=2

これはいい言葉だと思う。私はいままでよく「皆がリーダーになる必要はない」という言い方をしていたが、上記引用の方がロジカルで適切だと思う。すなわち、「皆ができないことをできるのがリーダーである」という定義を取るのであれば、「皆が、皆ができないことできるよう（=リーダー）になることはできない」が論理的に正しい。

話は変わるが、リーダーがいない場合、つまり誰も解決できない問題がある場合どうするのかということは下記記事に書いてある。

すなわち、局地戦のリーダーシップ、トヨタの中主査・小主査みたいな話です。むしろ世の中の大半のことはいかに局地で善戦しながら「風が吹いた時に凧をあげる」という気持ちで待てる人を増やすかという話だと思う。「果報は寝て待て」ではなく、「果報は鍛えて待て」なのである。

鍛えるにあたって、「畳の上の水練」はありえないので、限られた人、モノ、カネで現実のケースを通じて鍛えているということかと。

【感想】11. Replication and Consistency - Database Internals

"Data replication is a way of introducing redundancy by maintaining multiple copies of data in the system. However, since updating multiple copies of data atomically is a problem equivalent to consensus [MILOSEVIC11], it might be quite costly to perform this operation for every operation in the database."

via Check out this quote from Database Internals - https://learning.oreilly.com/library/view/database-internals/9781492040330/ch11.html

日常会話でこういう発言をできる人間になりたい。

"When talking about replication, we care most about three events: write, replica update, and read."

via Check out this quote from Database Internals - https://learning.oreilly.com/library/view/database-internals/9781492040330/ch11.html

まさに抜け落ちていた基本的な視点の指摘。

"Instead of being either consistent or available, systems can provide relaxed guarantees. We can define two tunable metrics: harvest and yield, choosing between which still constitutes correct behavior [FOX99]:"

via Check out this quote from Database Internals - https://learning.oreilly.com/library/view/database-internals/9781492040330/ch11.html

• harvestは例えば検索結果100件のうち1件の取得・計算に失敗しても99件を返すようなことか？
• yieldはrate limitやoptimistic concurrencyのことか？

• Strict Consistency
• Linearizability
• Sequential Consistency
• Causal Consistency

via Check out this quote from Database Internals - https://learning.oreilly.com/library/view/database-internals/9781492040330/ch11.html

Jepsenも参考にしつつconsistencyの学習。Strict consistencyは実現不可能な理論モデルと書いてある。

Azul Systemsという会社ではJavaを実行するための専用のプロセッサを開発し、JVMとCPUの密結合アーキテクチャによってガベージコレクションや並列化の性能を向上させていた。

https://qiita.com/kumagi/items/3867862c6be65328f89c

すごい…。

ちょっと話が広がってきたので一度Consistency Modelsの理解に注力する。

【感想】Elasticsearch: The Definitive Guide シーズン2

Chapter 2, 4, 9がこの本のマニアックな部分なので積極的に読んでいきたい。

"If you set replication to async, it will return success to the client as soon as the request has been executed on the primary shard. It will still forward the request to the replicas, but you will not know whether the replicas succeeded."

via Check out this quote from Elasticsearch: The Definitive Guide - https://learning.oreilly.com/library/view/elasticsearch-the-definitive/9781449358532/part01ch04.html

MongoDBでいうところのwrite concernのようなものかと。7.3の公式ドキュメントでこの記述がなかなか見つからない。

"By default, the primary shard requires a quorum, or majority, of shard copies (where a shard copy can be a primary or a replica shard) to be available before even attempting a write operation."

via Check out this quote from Elasticsearch: The Definitive Guide - https://learning.oreilly.com/library/view/elasticsearch-the-definitive/9781449358532/part01ch04.html

公式ドキュメントの構造がいまだに理解できないのだが、関係するのはおそらくここらへん。

By default, write operations only wait for the primary shards to be active before proceeding (i.e. wait_for_active_shards=1). This default can be overridden in the index settings dynamically by setting index.write.wait_for_active_shards. To alter this behavior per operation, the wait_for_active_shards request parameter can be used.

https://www.elastic.co/guide/en/elasticsearch/reference/7.3/docs-index_.html

これは7.3までにデフォルトquorumが変わったということか？

で変わったことを確認。Elasticsearchは公式ドキュメントよりGithub issuesの方が分かりやすい気がする。

By default, index.translog.durability is set to request meaning that Elasticsearch will only report success of an index, delete, update, or bulk request to the client after the translog has been successfully fsynced and committed on the primary and on every allocated replica. If index.translog.durability is set to async then Elasticsearch fsyncs and commits the translog every index.translog.sync_interval (defaults to 5 seconds).

https://www.elastic.co/guide/en/elasticsearch/reference/7.3/index-modules-translog.html

• index.translog.durability: request
• wait_for_active_shards: 1

がデフォルトということは分かったが、結局いつclientにacknowledgeが返るかのデフォルトがわからない。

Since replicas can be offline, the primary is not required to replicate to all replicas. Instead, Elasticsearch maintains a list of shard copies that should receive the operation. This list is called the in-sync copies and is maintained by the master node. As the name implies, these are the set of "good" shard copies that are guaranteed to have processed all of the index and delete operations that have been acknowledged to the user.

…

3. Forward the operation to each replica in the current in-sync copies set. If there are multiple replicas, this is done in parallel.
4. Once all replicas have successfully performed the operation and responded to the primary, the primary acknowledges the successful completion of the request to the client.

https://www.elastic.co/guide/en/elasticsearch/reference/7.3/docs-replication.html#_basic_write_model

ふわっとしているが全てのin-sync copies上でindexingが終わって始めてclientにacknowledgeが返るように読める。MongoDBでいうところのなんだ？

Stennie氏はStack OverflowのMongoDBトピックで個人的に信頼のおける方。曰く、MongoDBにおいてw: allのようなwrite concernはない。強い一貫性を求める場合、read preferenceをprimary（デフォルト）とし、write concernをmajorityとするとのこと。なるほど。言われてみれば当たり前だがwrite/readを同時に考えずにreplicationを語ることはできないと気がついた。

ここまで読んでreplicationに対する理解が圧倒的に弱いことがわかったので、別の本へ移動。

【感想】Elasticsearch: The Definitive Guide

ようやくElasticsearchの内部を学べる日が来た…。

"Instead of rewriting the whole inverted index, add new supplementary indices to reflect more-recent changes. Each inverted index can be queried in turn—starting with the oldest—and the results combined."

via Check out this quote from Elasticsearch: The Definitive Guide - https://learning.oreilly.com/library/view/elasticsearch-the-definitive/9781449358532/part01ch11.html

転置インデックスは更新の都合で分割されている。全く知らなかった。

"Lucene, the Java libraries on which Elasticsearch is based, introduced the concept of per-segment search. A segment is an inverted index in its own right, but now the word index in Lucene came to mean a collection of segments plus a commit point—a file that lists all known segments, as depicted in Figure 11-1."

via Check out this quote from Elasticsearch: The Definitive Guide - https://learning.oreilly.com/library/view/elasticsearch-the-definitive/9781449358532/part01ch11.html

• Luceneにおける分割の単位はsegmentと呼ばれる
• segmentの集合がLuceneにおけるindexと呼ばれる。これは、Elasticsearchにおけるindexとは異なる。
• LuceneにおけるindexはElasticsearchのshardである。
• Elasticsearchのshardの集合がElasticsearchにおけるindexである。

Elasticsearchが検索するとき、2段階の集約が行われている。

• Elasticsearchのshardの集約
• Luceneのsegmentの集約

OracleやMongoDBと比較して大きく異なる点はin-memory bufferのrefreshが行われるまで、そのsegmentはsearchができない点だと考えられる。私の理解が正しければMVCCを採用しているストレージエンジンではディスクへのfsyncが起こる前から、メモリ上で読み込みができる認識。

"Document updates work in a similar way: when a document is updated, the old version of the document is marked as deleted, and the new version of the document is indexed in a new segment. Perhaps both versions of the document will match a query, but the older deleted version is removed before the query results are returned."

via Check out this quote from Elasticsearch: The Definitive Guide - https://learning.oreilly.com/library/view/elasticsearch-the-definitive/9781449358532/part01ch11.html

delete/updateの場合、古いsegment内のdocumentは単にマーキングされる。クエリにマッチした場合でもレスポンスを返す前にフィルタリングされる。この方式ではsearchのコストは多少高いようだ。

ここまで読んできて、MongoDB/WiredTigerの関係から類推すると、Lucene上でsegmentのfull commitが専用のスレッドだけでは間に合わなくなった場合にElasticsearchのスレッドでクエリ・コマンドの受付が停止するのではないか。

"In Elasticsearch, this lightweight process of writing and opening a new segment is called a refresh. By default, every shard is refreshed automatically once every second. This is why we say that Elasticsearch has near real-time search: document changes are not visible to search immediately, but will become visible within 1 second."

via Check out this quote from Elasticsearch: The Definitive Guide - https://learning.oreilly.com/library/view/elasticsearch-the-definitive/9781449358532/part01ch11.html

つまりfull commitとは別に、デフォルト1秒毎にrefreshが行われる。私の理解では、in-memory bufferからfilesystem cache（メモリ）上にsegmentの書き込みが行われ、filesystem cacheからsegmentのsearchが可能になる。

CQRSのようなアーキテクチャパターンを採用している場合、index.refresh_intervalはデータ同期のSLOに合わせて良いように思われる。

ただ、in-memory bufferにdocumentがより多くとどまることになるが、頻繁なrefreshと多量のデータに対するrefreshの間のトレードオフはまだ分からない。

"The translog is also used to provide real-time CRUD."

via Check out this quote from Elasticsearch: The Definitive Guide - https://learning.oreilly.com/library/view/elasticsearch-the-definitive/9781449358532/part01ch11.html

ひぇー！！！😲なんで？🤔
WiredTigerでjournalからデータを読むことはないはず。secondary indexを別のタイミングでつくるというのは今まであまり考えたことがなかったので要学習。

"The action of performing a commit and truncating the translog is known in Elasticsearch as a flush. Shards are flushed automatically every 30 minutes, or when the translog becomes too big."

via Check out this quote from Elasticsearch: The Definitive Guide - https://learning.oreilly.com/library/view/elasticsearch-the-definitive/9781449358532/part01ch11.html

一度用語の整理を

• refresh → delete in-memory buffer
• full commit=flush → delete translog

なお、上記引用のデフォルト値は本書執筆当時の1.4のもの。

1.4では、（おそらく）translogのfsyncはrequest毎、flushは30mもしくは200mb毎がデフォルト値となっている。

7.3では、デフォルトのindex.translog.durability: requestの場合request毎だが、asyncの場合インターバルを指定できる。5s毎のfsyncがデフォルト。flushは512mb毎。

MongoDBと比較してみる。

If a write operation includes or implies a write concern of j: true.

まず、write concernとして指定できる点は違う。j: trueでない場合、100ms毎のfsyncがデフォルト。

index.translog.durability: requestの挙動が文献によってややブレがある

• translogのfsyncをrequest毎に行う
• translogのflushをrequest毎に行う

普通に考えると、後者のflush（full commit）がコストだからrefreshやtranslogが存在するわけで、前者が正しい挙動だと思われるが…

個人的にはindex.translog.durabilityは7.3デフォルトのrequestのままで良いように思われる。そもそもディスクI/Oがボトルネックになり、アプリケーションの性能に影響が出るのはtranslogのfsyncではなく、flush（full commit）なのではないかという仮説を持っている。
flushがボトルネックの場合、デフォルトの512mbのindexing毎にパフォーマンスのスパイクが観測できると考えられる。なお、flushがボトルネックである場合、indexing rateが変えられないのであれば、スケールアップもしくはnode/shardの追加ぐらいしか本質的にはできることがなさそう。

他のシチュエーションとしては、全てのindexingがclient側で待ちが発生している場合、translogのfsyncを待っている可能性がある。async/100msを試す価値はあると思われるが、単にin-memory buffer/translogにボトルネックが移る。他にTOO_MANY_REQUESTS、optimistic concurrency controlのモニタリングも必要になる。

直接関係ないがこういう回答ができる人になりたい。

IoT と時系列データと Elasticsearch | Data Pipeline Casual Talk Vol.4 from SORACOM,INC

これも分かりやすいが、refresh/flushの用語が混ざっている。

なお、2018年にtranslog依存であった種々の操作をLuceneのsoft delete依存に移植したようだ。

ここまで読んできて、reindexini/initial loadの場合には短時間ですべてメモリ上で完結するに越したことはないが、具体的なパラメーターは非常に状況依存なのと、near-realtime処理をするときとの切り替えも気を使うので、注意深い設計とテストが必要という当たり前の結論に至る。

"The merging of big segments can use a lot of I/O and CPU, which can hurt search performance if left unchecked. By default, Elasticsearch throttles the merge process so that search still has enough resources available to perform well."

via Check out this quote from Elasticsearch: The Definitive Guide - https://learning.oreilly.com/library/view/elasticsearch-the-definitive/9781449358532/part01ch11.html

他にもsegment mergingの際にもコストがかかる。MongoDB/WiredTigerではcompactに相当すると思うがあまり意識できてないな。

【感想】相続の落とし穴！共有名義不動産

昨年から税金の学習を続けている。今回はその一環の共有名義不動産。あまり税金は関係なかった。共有名義不動産について事前知識はゼロだったが、この本は非常に分かりやすかった。主張はシンプルで一刻も早く共有関係を解消すべきということに尽きる。

【感想】SDGs（持続可能な開発目標）

この本はどこで知ったんだっけな。多分新聞書評。

「SDGsとは何か？」
この質問に対して、筆者は
「SDGsは未来の世界の形だ」
と答えることにしている。

p. 1

なるほど。「共通善」との関係は何なのだろう。

SDGsでは、従来国際レジームのなかで考えられていたような、国内でSDGs実現に向けた政策を実施する際の寄り処となるようなルールが、国際的に定められているわけではない。
p. 11

常識が常識的に実践されていることは少ないという感じだ。

目標によるグローバルガバナンスが、これほどまでに包括的に行われたことはこれまでにない。
p. 12

ひょっとして目標による管理の歴史や根拠が書かれていたら嬉しい。

知らなかった。面白い。

I've found Sustainable Development Report 2020. Japan is ranked 17th. Points were reduced for SDG10, "Eliminate inequality among people and countries". https://t.co/3B6rdigVpI

— Mitsuishi Tomomi 三津石智巳 (@tlila) 2021年1月22日

17目標はむしろ、目標達成を目指す取り組みの「入口」が17個あると考えるほうがよい。17個もの異なる入口があれば、少なくともそのどれか一つは取り組みのきっかけになるだろう。
大事なのは、どの側面から入ったとしても、何らかの取り組みを進めようと思えばその活動が他の目標にも関連することになり、結果として総合的視点から取り組みをすすめる必要が出てくる、という点である。
p. 30

この考え方は思いつかなかった！コンピテンシーにも同じことが言える。

SDGs策定プロセスの最大の効果は…多分に偶然のタイミングがなせる業でもあった。
p. 55

非常に面白い。

人間の歴史をみると、行動したところで世界は変わらない。行動しても99.9％は失敗すると理解しながらも、それでも行動しなければ何も変わらないと信じて世界を変えようという人がいたので、人間の社会は進化したのです。すべて結果論。行動しないと世界は変わらないので、自分が正しいと思うことをやりつづければそれでいいのだと思います。
https://nakamaaru.asahi.com/article/12449025

を思い出した。

環境と開発を包括するというのは、品質とスケジュールみたいな。会社の利益と従業員の幸せみたいな。

総じてSDGsについて学んでいくのは私にとって非常に大事であると感じた。