NewSQLの特徴とされている技術の大部分はNoSQLでも採用されている

# 注意事項

- 個人用のメモ、ポエムなので、情報に誤りが含まれている可能性があります
- 一旦エビデンス提示のために列挙するのみに留めます(裏でちまちま読んでいます...)

# はじめに

NoSQLデータベースには明確な定義はないことから、解決しようとしている問題や特徴は製品によって様々です。
そのため、一部界隈ではNewSQL独自の特徴とされる技術の大半は、NoSQLでも広く採用されています。
以下の項目に関して、主に論文で見つけることができたものをいくつかピックアップして該当箇所を見ていきます。

- 強整合性の提供
- 合意形成アルゴリズムの利用
- データ構造としてLSM-Treeの採用
- ACIDトランザクションのサポート

# 強整合性の提供、合意形成アルゴリズムの利用

多くのNoSQL DBでは読み取り、書き込み操作での強整合性を提供し、ノード間のレプリケーション、リーダー・エレクションなどに合意形成アルゴリズムを採用しています。

## A Survey on the Usage of Consensus Algorithms in Key-Value Databases

次の論文では10種類の強整合性を提供しているNoSQL DB(Key-Value Database) 10種類について調査を行っています。

[A Survey on the Usage of Consensus Algorithms in Key-Value Databases](https://yatian-liu.github.io/public/Survey_on_Usage_of_Consensus_Algorithms_in_Key-Value_Databases.pdf)

引用箇所の通り、4製品ではRaft, PaxosをDBMS内のいずれかのコンポーネントのリーダー・エレクション、あるいはデータのレプリケーションの合意形成に利用していることがわかります。
残り6つのNoSQL DBについてはprimary-backup方式であり、実装のシンプルさが採用の理由として推測されており、製品による多様性があるようです。

>Secondly, Raft is used more often than Paxos in implementing strong consistency for the database surveyed. In the 10
databases surveyed in detail, etcd and Hazelcast use Raft for
data replication and ArangoDB uses Raft for configuration
replication, while only Oracle NoSQL DB uses Paxos, and
Paxos is only used for new leader election in primary-backup
failure recovery but not the full data replication process
...
>A majority of systems (Couchbase, Ehcache, Apache Ignite,
Aerospike, ArangoDB, and Oracle NoSQL, which is 6 out of
>10) in our survey use protocols based on primary-backup
instead of consensus algorithms for state machine replication. Possible reasons for this are that primary-backup is
significantly easier to implement than consensus algorithms
and the systems using primary-backup for replication mostly
only do replication within a cluster of machines in the same
data center, making the synchrony assumption valid.

## MongoDB

次の論文ではMongoDBにおけるRaftアルゴリズムを元にしたレプリケーションと、linearizability(強整合性)のサポートについて説明しています。

[Fault-Tolerant Replication with Pull-Based Consensus in MongoDB](https://www.usenix.org/system/files/nsdi21-zhou.pdf)

>In this paper, we present the design and implementation of
strongly consistent replication in MongoDB. MongoDB provides linearizability and tolerates any minority of failures
through a novel consensus protocol that derives from Raft. 

## Amazon DynamoDB

次の論文ではDynamoDBにおける読み取り時の選択式の整合性と、Multi-Paxosによるリーダー・エレクションと合意形成を実施していることを解説しています。

[Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service](https://www.usenix.org/system/files/atc22-elhemali.pdf)

>Developers can request strong or eventual consistency when reading items
from a table.
...
>The replication group uses Multi-Paxos [14]
for leader election and consensus. Any replica can trigger a
round of the election. Once elected leader, a replica can maintain leadership as long as it periodically renews its leadership
lease.

# データ構造としてLSM-Treeの採用

NoSQL DBもLSM-Treeは広く採用されています。
次の論文ではLSM-Treeを利用したインデックス、Key-Value Storeについての調査を行っています。

## A survey of LSM-Tree based Indexes, Data Systems and KV-stores

[A survey of LSM-Tree based Indexes, Data Systems and KV-stores](https://ieeexplore.ieee.org/abstract/document/10482249)

以下の引用箇所の通り、複数のNoSQLデータシステム(DBMSおよびライブラリ)がLSM-Treeを採用しています。

>In recent years, LSM-Tree has gained popularity and has been adopted by a number of NoSql databases, and key-value stores.
...
>A number of open source NoSql data systems implementing
LSM-Tree have been proposed by the research community
namely, RocksDB [22], Cassandra [27], LevelDB [29], HBase
[28], and AsterixDB [15].

# ACIDトランザクションのサポート

NoSQL DBにおいても、製品によって様々な形でACIDトランザクションをサポートしています。
NoSQL DBではスケーラビリティやパフォーマンスを求める関係でRDBと同じスタイルのトランザクションを実行できるわけではなく、やはり製品によりどのようなユースケース、ワークロードに最適化しているのかをよく確認する必要があります。

## FoundationDB

次の論文ではFoundationDBについて10年以上前から存在するトランザクショナルなキー・バリュー・ストアであり、ACIDトランザクションをサポートしていると説明されています。
また、「It is one of the first systems to combine the flexibility and scalability of NoSQL architectures with the power of ACID transactions (a.k.a. NewSQL)」と力強く主張しています。

[FoundationDB: A Distributed Unbundled Transactional Key Value Store](https://www.foundationdb.org/files/fdb-paper.pdf)

>FoundationDB is an open source transactional key value store created more than ten years ago. It is one of the first systems to combine
the flexibility and scalability of NoSQL architectures with the power
of ACID transactions (a.k.a. NewSQL). 

## OrientDB

OrienDBの論文では再設計によりACIDトランザクションがサポートされ、その点がdifferentiatorであると強調されています。

[OrientDB: A NoSQL, Open Source MMDMS](https://ceur-ws.org/Vol-3163/BICOD21_paper_3.pdf)

>While OrientDB’s initial open source release was in 2010, many improvements like the multi-model API / query language
and full ACID support came with a recent re-design.
...
>As one of the first MMDMSs, OrientDB provides a single,
multi-model persistence with ACID transactions (cf. differentiator (3)), whose main aspects we briefly introduce.

## Amazon DynamoDB

次の論文ではAmazon DynamoDBでのACIDトランザクションのサポートについて解説しています。
既存の操作の性能や可用性、スケーラビリティについて妥協せずにACIDトランザクションをサポートしていることが強調されています。

[Distributed Transactions at Scale in Amazon DynamoDB](https://www.usenix.org/system/files/atc23-idziorek.pdf)

>This paper explains how transactions
were added to Amazon DynamoDB using a timestamp
ordering protocol while exploiting the semantics of a keyvalue store to achieve low latency for both transactional
and non-transactional operations. The results of experiments against a production implementation demonstrate
that distributed transactions with full ACID properties
can be supported without compromising on performance,
availability, or scale.

## Firestore

次の論文ではGoogle FireStoreでのACIDトランザクションのサポートについて解説しています。
内部的にGoogle Spannerのトランザクションに一対一でマッピングされることが説明されています。

[Firestore: The NoSQL Serverless Database for the Application Developer](https://storage.googleapis.com/gweb-research2023-media/pubtools/7076.pdf)

>Firestore’s schemaless data model, ACID transactions, strong consistency,
and index-everything default means that developers can focus
more on the data they wish to store and present to the
end user without worrying about the details of the database
configuration
...
>Firestore’s
transactions map directly to Spanner transactions, which are
lock-based and use two-phase-commits across tablets.

## MongoDB

開発元が仕組みについて解説している論文などを見つけることはできませんでしたが、MongoDBの公式ページによると複数のシャードをまたがるmulti-collectionのトランザクションをサポートしているようです。

[A Guide to ACID Properties in Database Management Systems](https://www.mongodb.com/resources/basics/databases/acid-transactions)

>In MongoDB, a write operation is atomic on the level of a single document, even if the operation modifies multiple embedded documents within a single document. For situations that require atomicity of reads and writes to multiple documents (in a single collection or multiple collections), MongoDB supports distributed transactions, including transactions on replica sets and sharded clusters.

# おまけ: ジョインのサポートについて

どのような形でサポートが行われているのか、そもそも記述が正しいのかは要確認ですが、wikipediaのNoSQLのページにてジョインやACIDトランザクションをサポートしたNoSQL DBの一覧とさせるものが掲載されています。
※Wikipediaは情報が更新されていなかったり、堂々と嘘が掲載されていることもあり、信憑性が怪しいことが多々あるので「おまけ」としています

[ACID and join support - NoSQL](https://en.wikipedia.org/wiki/NoSQL#ACID_and_join_support)

|Database|ACID|Joins|
|:-:|:-:|:-:|
|Aerospike|Yes|No|
|Apache Ignite|Yes|Yes|
|ArangoDB|Yes|Yes|
|Amazon DynamoDB|Yes|No|
|Couchbase|Yes|Yes|
|CouchDB|Yes|Yes|
|IBM Db2|Yes|Yes|
|InfinityDB|Yes|No|
|LMDB|Yes|No|
|MarkLogic|Yes|Yes[nb 1]|
|MongoDB|Yes|Yes[nb 2]|
|OrientDB|Yes|Yes[nb 3]|

 >1. Joins do not necessarily apply to document databases, but MarkLogic can do joins using semantics.[31]
 >2. MongoDB did not support joining from a sharded collection until version 5.1.[32]
 >3. OrientDB can resolve 1:1 joins using links by storing direct links to foreign records.[33]

ACIDトランザクションのサポートもそうですが、「ジョインをサポートをしているから偉い、サポートしていないから時代遅れ！」といった単純なものではなく、どのようなユースケースを想定し、どういった形でサポートが行われているのか、既存の操作への影響等を個別に見ていく必要があり、星取表自体にそれほど深い意味はないと考えられます。
※なお、NoSQLは一般的にスケーラビリティやレイテンシー、可用性、コスト削減などを重視しており、非正規化したデータ・モデルを採用し、強整合性を提供する製品でも整合性を妥協したクエリを発行することが多いので、RDBMSのデータ・モデルやクエリをそのまま載せられるわけではないです。

# まとめ

以上のように、2024年現在ではNoSQLでも以下の技術的な特徴を有する製品は複数存在します。

- 強整合性の提供
- 合意形成アルゴリズムの利用
- データ構造としてLSM-Treeの採用
- ACIDトランザクションのサポート

繰り返しになりますが、その製品が想定するユースケース等を無視した作為的な星取表にはほとんど意味はないです。
またNoSQL, NewSQLという名称にも明確な定義があるわけではなく、どういった問題課題を解決する製品であるのか、どういった経緯でその仕組み、機能が採用されているのか等を個別に見ていく必要があります。