はじめに
前回の記事の「ACID特性、CAP定理、BASEについて」のセクションについての補足事項です。
素人が思いついたことを適当に書きなぐっていることから、多くの技術的に不正確であったり、誤解を招く記述が含まれている可能性があることにご注意ください。
BASEの出典について
探した限りではBASEの出典とされる資料は以下のもののようです。
BASEについて以下のトレードオフが存在することが記述されています。
※検索エンジンやWebキャッシュを構築した知見だと思われますが、断片的な情報しか記載されていないスライドなので詳細はわからず...
Towards robust distributed systems
https://www.researchgate.net/publication/221343719_Towards_robust_distributed_systems
But we forfeit “C” and “I” for availability, graceful degradation, and performance
可用性、graceful degradation、性能のために整合性やIsolationを犠牲にすることを示していることがわかります。
加えて、BASEのテクニックについて以下のように記載されており、BASEという言葉自体に全く意味はないことはないものの、実際には恐らく「ACIDと対比する際に便利な、単なる覚えやすい語呂合わせ」に近いもので、可用性や性能などの必要な品質を確保するための多岐にわたるテクニックの総称であることがわかります。
※当然、「どのテクニックを含めればBASEに該当するか」などの厳密な定義なども存在しないと思われます
Weak consistency
– stale data OK
Availability first
Best effort
Approximate answers OK
Aggressive (optimistic)
Simpler!
Faster
Easier evolution
加えて以下の重要な記述もあり、そもそもACID, BASEのテクニックのどちらかを排他的に選択するものではなく、「システムの要件に合わせて組み合わせるもの」であることも記述されています。
But I think it’s a spectrum
Real internet systems are a careful mixture of ACID and BASE subsystems
– We use ACID for user profiles and logging (for revenue)
なお「Weak Consistency」の箇所は「stale data OK」となっていることから、ACIDトランザクションにおけるConsistency(一意制約やcheck句、外部キー等)と必ずしも完全に一致しているわけではなく、分散システムにおける整合性モデルにて弱い整合性を提供している(レプリカに対するアトミックな更新、強整合性を担保しない)ことを(主に）示していると思われます。
※結果的にWeak ConsistencyはACIDにおけるConsitencyの要件を緩和することになると思われますが...
RDS, AuroraはACIDなの、BASEなの？
そもそもシングルノードのRDBでもConsistencyやIsolationは妥協することがある
前述のとおり、BASEの基本的な考え方は「他の品質特性を改善するためにConsistencyやIsolationを妥協する」というものですが、そもそもシングルノードのRDBにおいても、多くの場合、主に性能の改善のためにConsistencyやIsolationは妥協しています。
例えばOSS、商用問わず主要なRDBMS(Oracle, SQL Server, MySQL, PostgreSQL etc...)においてトランザクションの並行性を向上させるためにtransaction isolation levelのデフォルトではserializableではなく、Read Committed(MySQLではRepeatable Read)が選択されています。
※非常に極端な例としてはSQL ServerやDB2ではUncommitted Read(Dirty Read)すらサポートされています。
https://www.ibm.com/docs/en/db2/11.5?topic=issues-isolation-levels#c0004121__ur
また、複雑なクエリやビューの性能向上のためにマテリアライズド・ビューを作成し、非同期に更新する手法（当然、Weak Consistenyとなる）もよく利用される性能改善のテクニックという認識です。
Join, Group Byのサポート=ACIDトランザクションのサポートではない
前回の記事でも触れた通り、「JOINやGROUP BYを実施できるかどうか」は提供されるAPI, クエリモデルの違いに当たり、ACID、BASEとは独立した要素という認識です。
例えば、RDS, Auroraでは「非同期」Read Replica(=Eventual Consistency Read)でJOIN,GROUP BYを実施可能ですし(当然最新の値は取得できない)、実はDynamoDBにおいてもAthenaのFederated Queryにより、JOIN, GROUP BY等を含むSQL文を実施可能です。
※「JOIN, GROUP BYを実施可能である」点と「アーキテクチャがこのような複雑なクエリの実行に適しており、効率的なのか」「RDBのようなSnapshot Isolationをサポートしているのか」は全く別の観点であることに注意。
https://docs.aws.amazon.com/ja_jp/athena/latest/ug/connect-to-a-data-source.html
Snapshot Isolation=ACIDトランザクションではない
前回の記事でも軽く触れた通り、恐らく当該記事のコンテキストにおける「一貫性」とは、「検索クエリを実行した際に、(non-blockingに)データベースがLSN/SCNで整合性が取れた断面として見えること=Snapshot Isolationのサポート」のことを指していると思われます。
しかしながら、この処理も「ある時点でデータベース全体で一貫性のあるデータ」である必要はあるものの、必ずしも最新のデータが反映されたStrong Consistency Readである必要はなく、Read Replica上でもSnap Isolationは実現可能です。
https://ja.wikipedia.org/wiki/Snapshot_isolation
なお、DynamoDBおいて複数パーティション、アイテムを跨ぎ、特定時点で一貫性のあるデータを取得するは、現時点ではTransactGetItemsを実行するしか方法がなく、以下の制約があることから「ある時点でデータベース全体で一貫性のあるデータ」を元に、複雑な分析クエリの実行はRDBの方が得意と言えそうです。
- 2022年5月時点で最大25アイテムまでしか参照できないこと
- 必ず主キーで検索する必要があること
- Join, Group By等がAPIとしてサポートされていないこと
しかしながら、前述のとおり、「特定時点のスナップショットのデータを見る必要がある」だけで、ConsistencyやIsolationの要件は緩和可能であり、ACID, BASEの比較とは異なる要素であると思われます。
Aurora, RDSは「非同期」リードレプリカを活用せざるを得ない
Aurora, RDSにおいてWriterは一台のみであり、処理性能をスケールさせるためには「非同期」リードレプリカを活用する必要があることから、AuroraやRDSでもConsistencyを緩和するBASEのパラダイムのテクニックは特に大規模なWebシステムにてほぼ必須のテクニックと思われます。
一方で書き込みに関しては単一ノードで実行し、可用性やスケーラビリティを犠牲にすることでACIDトランザクションをサポートしていることから、処理の内容に応じてACID, BASEのどちらの要素も含まれていることがわかります。
まとめ
以上のように、RDBにおいてもConsistencyやIsolationを緩和して性能を稼ぐ手法はよくある方法となります。
また、Join, Group By, Snapshot Isolationについても、RDBの方が得意な処理ではあるものの、実はBASEのパラダイムでも実施可能であり、必ずしもStrong Consistency、強いIsolationにて実施する必要はないです。
DynamoDBはACIDなの、BASEなの？
次に、DynamoDBがACIDなのか、BASEなのかについてみていきます。
original Dynamo(2007)とDynamoDB(2012)の違いについて
初めに前提条件として、2007発表のDynamo論文に記載されている「Dynamo」と、2012年に発表された「DynamoDB」には関連性があるものの「別の製品」であり、「アーキテクチャに違いがある」ことに要注意です。
以下の記事の内容より、original DynamoとSimpleDBの好評だった点を組み合わせてより発展させたものがDynamoDBであることがわかります。
original Dynamoの特性についてみていきます。
Amazon DynamoDB – a Fast and Scalable NoSQL Database Service Designed for Internet Scale Applications
https://www.allthingsdistributed.com/2012/01/amazon-dynamodb.html
original Dynamoについて記述されたDynamo Paperより、Original Dynamoではamazon.comのショッピングカートでの利用が想定され、強い整合性よりも「常に読み書きできること」が重視されていることがわかります。
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
Therefore, the service responsible for managing shopping carts requires that it can always write to and read from its data store, and that its data needs to be available across multiple data centers.
加えてSloppy QuorumやVector clock、あるいは読み取り時にクライアント側で対処することで可用性を向上させ、一時的なサーバーのダウンにそなえていることがわかります。
※つまり特定のアイテムに関して複数のノードに同時に書き込みを行う、Multi-Master(Leaderless)方式のアーキレクチャが採用されています
High Availability for writes
Vector clocks with reconciliation during reads
Handling temporary failures
Sloppy Quorum and hinted handoff
複数のノードに同時に書き込みを実施し、ノード間でデータの不整合が発生する可能性があることから、その対策に同期化も実施します。
※BASEにおけるSoft state, Eventual Consistencyに相当する特性
Recovering from permanent failures
Anti-entropy using Merkle trees
なお、シンプルなQuorum Read/Writeに関しては次の記事に記載されている通り、どんなに工夫しても「ノード間で合意形成された値が存在しない」という根本的な問題を解消できないことから、Single keyにおけるlinearizabilityを担保できないことがわかります。
かつrollbackの操作が存在しないことから、性能を稼ぐために問い合わせるノード数を減らしてしまうと、Dirty Readの危険が存在することもわかります。
https://blog.yugabyte.com/apache-cassandra-lightweight-transactions-secondary-indexes-tunable-consistency/
一方で2012年登場のDynamoDBではこの部分が改良されており、パーティション内でLeader Electionを実施し、「書き込みはLeader経由で実施する」「パーティション内でLeaderとして合意されたノードには必ず最新の結果が保存されている」とすることで、Signle keyにおけるlinearizabilityを担保していることがわかります。
AWS re:Invent 2018: Amazon DynamoDB Under the Hood: How We Built a Hyper-Scale Database (DAT321)
https://www.youtube.com/watch?v=yvBR71D0nAQ
上記のビデオよりEventual Consistency Readとされる操作も、実際には「2/3の確率で最新のデータ」であり、かつ整合性が取れていないデータも、「単に古いだけ」で過去にLeaderでcommitされたはずの値であり、前述のQuorum ReadのようなDirty Readの危険は存在しないと思われます。
※合意形成プロトコルニワカなので調べ切れていませんが、真面目に考えると本当にエッジケースがないのかは不明、実装を考えると無限に難しいのでは...
上記の仕組みによりDynamoDBでは一部のサーバーがダウンしても書き込みを実施できるoriginal Dynamoの「High Availability for writes」の特性は失われてしまったとみられますが、次の記事にある通りLeader Electionは多くの利点が存在することから、この仕組みに変更されたと思われます。
https://aws.amazon.com/builders-library/leader-election-in-distributed-systems/
なお、「Amazon DynamoDB – a Fast and Scalable NoSQL Database Service Designed for Internet Scale Applications」においても次の記述が存在し、特定の整合性モデルを強制しないことが強調されています。
※前述のACID, BASEのパラダイムの比較ではなくて、分散システムにおける整合性モデルにのみフォーカスした記述となっており、正直こちらの方が大分わかりやすいように思います。
Flexible. Amazon DynamoDB is an extremely flexible system that does not force its users into a particular data model or a particular consistency model. DynamoDB tables do not have a fixed schema but instead allow each data item to have any number of attributes, including multi-valued attributes. Developers can optionally use stronger consistency models when accessing the database, trading off some performance and availability for a simpler model. They can also take advantage of the atomic increment/decrement functionality of DynamoDB for counters.
まとめ
以上のことから、DynamoDBにおいても性能や可用性が重要な場合、BASEパラダイムのEventual Consistency Readを利用可能であるものの、現行の製品であるDynamoDBではlinearizabilityがサポートされ、特定のConsistency Modelが強制されていないことがわかります。
加えて前回記事の通り、複数ノード/アイテムを跨るACIDトランザクションもサポートされていることから、RDBとはデータモデルやAPIの違いはあれど、DynamoDBもACIDとBASEのどちらのパラダイムの要素も含まれており、アプリケーションの要件に応じて選択する必要があります。
じゃあCAP, ACID, BASEの用語を利用せずに、どうやって違いを説明すればよいの？
単にデータモデルとサポートされるAPI、それぞれが得意な処理の違いを説明するだけで十分ではないでしょうか。
散々強調してきた通り、ACIDとBASEは排他的に選択される特性ではないことから、「RDBはACID! DynamoDBはBASE!」というのは明確な誤りであり、混乱を招き誤解される可能性が非常に高いように思えます。