Scylla是仿照Apache Cassandra的分布式数据库。我们评估了Scylla 4.2-rc3的社区版本，发现LWT和正常操作均未达到要求的保证：LWT在健康集群中表现出裂脑，非LWT操作未如要求的那样被隔离。裂脑问题已在4.2中修复，Scyla的文档不再声称非LWT操作是隔离的。此外，在成员资格更改（部分解决）后，我们观察到LWT裂脑，LWT终止读取（在4.2.1中修复），以及响应LWT批处理语句而丢失行（在4.3.rc1中修复）。 Scylla仍然表现出裂脑，但是在我们的测试中，这仅限于与其他故障同时发生的成员资格更改。 Scylla有一篇补充性的博客文章，这些发现也将在2021年Scylla峰会上发表。这项工作由ScyllaDB资助，并根据Jepsen道德政策进行。
Scylla是一个分布式的宽列1数据库，起源于Cassandra的C ++端口，旨在提高性能。它同时支持与Cassandra和DynamoDB兼容的API，旨在用于高吞吐量，低延迟的工作负载，包括分析，消息传递和其他时间序列数据。
Scylla将数据组织到包含表和行的键空间中。行由主键唯一标识。每行在物理上都是一个排序的一系列（ke，y，v，l，t，t，mp）三元组，称为单元格，但是从概念上讲，Scyla行是列名称到值的映射。这些值可以是原语（例如字符串，整数，布尔值，日期），计数器或集合，例如地图，列表或集合。集合使用多个单元在内部存储。通过分区键将行分组为分区，然后通过Dynamo样式的哈希环将这些分区分配给群集中的节点子集。每个分区跨多个节点复制以实现冗余。
与Cassandra一样，Scylla通常允许客户端在任何时间写入任何节点，即使当节点崩溃或分割开时也是如此。写入是否持久取决于它是否到达可以存储该行的节点。是否向客户端确认写操作取决于是否有足够的节点响应来满足客户端请求的一致性级别。 Scylla声称，写操作是隔离的，只要它们发生在单个分区内即可：
在UPDATE语句中，同一分区键中的所有更新都是原子且独立地应用的。
当有多个写入单个单元格时，Sylla会使用“ Last-write-wins（LWW）”（最后写入获胜）（LWW）来解决它们：具有新时间戳记的值将替换具有旧时间戳记的值。如果发生时间戳冲突，则按字典顺序的较高值获胜。
上次写赢表示更新有可能丢失：如果客户端读取某个值v 1，然后回写v 2，则并发更新也可能会观察v 1并写入v 3，从而覆盖v 2。 v 2的有效丢失。为避免此问题，Scylla用户可以将其更新构造为唯一的插入内容，从而利用Scylla的宽行将每个更改存储为该行中的不同列。然后，客户可以在读取时将这些列合并在一起以恢复有效值。
这种方法要求操作是通勤的：写入应该能够以任一顺序生效。对于非交换操作，Scyla（如Cassandra）通过轻量级事务（LWT）提供线性化的更新。 LWT仅在谓词成立的情况下才允许执行单个Cassandra操作。它们在单个事务中不提供任意会话或多个操作的序列。虽然这可以防止事务混淆读写，但单个事务选择可以读取多行，而单个批处理可以插入，更新或删除多行。这两种构造都限于单个分区，这意味着单个分区上的全LWT历史记录应严格可序列化。
Scylla和Cassandra都使用基于Paxos的共识算法来进行这些交易，但是在Cassandra每次交易需要四次往返的情况下，Scyla仅需要三次往返。其他共识算法（例如Raft）可以在一次往返中达成共识，这就是Scylla为基于Raft的LWT实现奠定基础的原因。
Scylla有一个现有的Jepsen测试套件，该套件适用于Cassandra的Jepsen测试。我们审查了Scylla 4.2-rc3的测试套件，并通过4.2.rc5对其进行了大幅扩展，包括创建了新的，更具攻击性的工作负载和更复杂的针对错误注入的敌人。我们的新测试在五个Debian Buster节点的群集上运行，这些节点部署在LXC，Docker和EC2中。
我们对Scylla的默认配置进行了一些调整，以加快测试速度。默认情况下，由于启动时闲聊涉及临时死锁，Scylla需要一分钟以上的时间来检测节点故障，并需要300秒才能从进程崩溃中恢复。我们降低了phi_convict_threshold，ring_delay_ms，shadow_round_ms，并调整了其他设置以减少启动和恢复时间。
在这些测试期间，我们注入了各种故障，包括网络分区，进程终止，进程暂停，时钟偏斜和成员资格更改，包括添加，修复，停用和强制删除节点。此外，我们在使用和未使用自定义时间戳生成器的情况下都测量了行为，这些生成器引入了合成时钟偏移并增加了时间戳冲突的可能性。
Scylla的原始测试套件包括CQL（卡桑德拉查询语言）映射和集合的工作负载，它们都将几个一致性为ONE的元素插入到单个集合中，并尝试以一致性为ALL的最终读取结果将它们读回。批处理工作负载将成对的行插入在一起，并尝试读回这两行。计数器工作负载创建单个CQL计数器，并尝试重复递增它。读取结果验证计数器值保持在预期范围内。专用的实例化视图工作负载会更新地图值并查询实例化视图，以查看是否反映了这些更改。
在我们简要评估这些工作负载的同时，当前的工作重点是Scylla的轻量级事务安全性。为了验证LWT的安全性，我们使用了三个工作负载。
第一个是cas寄存器，它使用LWT在几行上执行读取，写入和比较设置操作。它使用Knossos验证每行上的操作历史记录是否可线性化。 Knossos的并发性是指数级的，并且在Jepsen测试中，并发性（由于不确定的响应）迅速增加。这将历史记录的长度限制为每行几百次操作。
为了补充Knossos检查器，我们设计了list-append和wr-register工作负载，这两个工作负载均使用Elle来搜索违反严格可序列化性的行为。 Elle利用对所涉及的历史和数据结构的了解来推断对每个单独密钥的版本顺序以及这些密钥上的事务顺序的约束。这些约束图中的循环对应于隔离异常。 list-append测试执行将唯一整数附加到CQL列表的事务，并通过主键读取这些列表，而wr-register测试将唯一整数写入单个行，而不是CQL集合。
两种工作负载均执行由单个SELECT或BATCH更新组成的LWT事务。 Scylla禁止在单个查询中混合读写操作，也禁止使用CQL集合读取多个行的查询以及跨越分区边界的LWT查询。即使有这些限制，我们也可以验证单键线性化以及单个分区内有限的多键严格可序列化性。
我们还设计了各种特殊用途的工作负载来调查异常行为。批处理返回检查响应于LWT批处理而返回的行。此测试验证返回的行与每个批次中请求的更新相对应。写隔离执行对多个单元的非LWT写操作，并执行并发读操作，以查找仅部分值来自同一写操作的情况：读偏斜的证据。
我们的测试侧重于轻量级事务安全性，但是在此过程中，我们发现了非LWT操作中的一些其他行为。我们将首先讨论一些有关时间戳，批处理退货和非LWT隔离的小问题，然后讨论轻量级事务中的过时读取和裂脑。
我们发现Scylla现有的CQL集和映射测试存在异常行为：当我们使用不完善的时间戳进行测试时，它们似乎丢失了公认的插入内容。较高的时钟偏斜度会导致更多的写入丢失，但是即使是仅一秒钟的偏斜也会导致更新丢失。这种行为特别令人惊讶，因为不同的set和map插入应该通勤。换句话说，将a然后b添加到集合应该与将b然后a相加相同。
事实证明，此行为不是错误。实际上，这是有据可查的行为。要了解原因，我们必须查看在设置（或映射）工作负载期间执行的事务。他们首先创建一个带有set（地图）列的表，然后插入一行：
CREATE TABLE集合（id int PRIMARY KEY，值set ）; INSERT INTO集合（id，值）VALUES（0，{}）
创建此空集后，客户端将执行更新：每个客户端都会向该集添加一个唯一元素。例如：
这些UPDATE语句都相互通勤，而INSERT和UPDATE则不行。如果INSERT收到的时间戳比UPDATE的时间戳高，则它将以静默方式否定该更新的写入操作，而不考虑实时顺序。这出于三个原因是令人惊讶的。
首先，数据库用户通常隐式地假定线性化：如果INSERT完成，则在该完成之后开始的UPDATE应该稍后生效。这对于LWT是正确的，但对于正常的Scylla操作则不是。习惯了Scylla（或其他Cassandra样式的数据库）的用户可能知道此行为，而是可能询问这些操作涉及的一致性级别，因为它们可能发生在不相交的节点上。这是一条红色的鲱鱼：行为是最后写入胜出时间戳仲裁的结果，选择一致性级别QUORUM或ALL并不能阻止它。
其次，CQL中的INSERT和UPDATE具有与大多数查询语言不同的语义。例如，在SQL中，INSERT创建一个新行，而UPDATE更改一个现有行。 SQL中成功的INSERT和UPDATE对只能按一个顺序执行：INSERT必须在UPDATE之前进行，因为否则UPDATE将没有行可以修改。相比之下，CQL的INSERT和UPDATE几乎（几乎）无法区分：都表示“ upsert”。 UPDATE语句会在不存在任何新行时创建新行，并且即使每个副本已经具有要“插入”该行的数据，INSERT语句也可以成功执行；它会覆盖时间戳较低的所有单元。
第三，习惯于使用CRDT的用户可能希望CQL集类似于OR集或G集：这些集可以始终安全地添加元素，但是可能会删除并发删除项。在这种情况下，插入{}值将是安全的：可能希望插入是无操作的（本质上是没有元素的加法），或者删除因果关系的先前值，但不删除因果关系的并发或更高值。 Scylla和Cassandra一样，都不做任何事情。插入是设计上的破坏性操作。实际上，编写任何集合文字（例如{}或（1，2））是在内部通过写入删除逻辑删除和新值来实现的。
请注意，与SQL不同，INSERT默认情况下不检查该行的先前存在：如果之前不存在该行，则创建该行，否则进行更新。此外，没有办法知道是哪个创建或更新发生的。
对于UPDATE同样如此。尽管Cassandra集合文档显示了INSERT后跟着UPDATE，好像两者应该按顺序进行，而Scylla数据类型文档也是如此，但这些示例都没有明确声明该顺序是有保证的，而不是可能的。通常，应该预期Scylla和Cassandra中的操作（偶尔）以任意顺序进行。同样，INSERT和UPDATE的名称是暗示性的，而不是确定性的：由于UPDATE ... SET value = {}可以破坏信息，而UPDATE和INSERT实际上是同一操作，因此INSERT也可以破坏信息。
如果您对此感到惊讶，那么您并不孤单。最初设计该测试的Cassandra工程师并未意识到INSERT ... {}是不安全的。该工作量由Scylla工程师移植到Scylla，由Jepsen审核，然后由多个Scylla工程师再次审核，直到一个人意识到错误。杰普森发布了一项非正式调查，询问CQL用户在这种情况下会发生什么情况，在11项回应中，没有人能正确预测这一结果。 2
用户可能仅通过执行（交换）UPDATE操作而无需初始INSERT即可解决此问题。 Scylla的文档不再声称非LWT操作是隔离的，而是解释了时间戳冲突行为，并提到插入空映射与删除相同。
通常，在网络分区和进程崩溃的情况下，LWT对Scylla的写入可能会失败，但实际上会成功。特别是，错误消息UnavailableException：没有足够的副本可用于一致性QUORUM的查询，这应表示该操作肯定没有发生，但这些操作实际上对于以后的读取是可见的。例如，在此列表追加测试中，后来读取到了对键618的52追加失败。
759：fail：txn [[：append 629 127] [：append 618 52]] ... 648：ok：txn [[：r 618 [50 52 69 74]]]
如果我们将此异常表示未提交52的追加，则这对操作构成异常中止的读取！但是我们应该如何解释这个错误呢？
截至2020年9月29日，ScylaDB的文档似乎并未包含任何有关错误消息含义或结果是否确定的描述。 Datastax的Java客户端文档将该错误描述为“当协调员知道没有足够的副本来执行具有请求的一致性级别的查询时抛出的错误”，Cassandra错误文档对此进行了确认。 Cassandra图的文档显示，如果没有与副本进行通信，则协调器会返回UnavailableException-而当协调器向副本发出请求时，会抛出其他异常（如WriteTimeout）。
用户可以合理地得出结论，UnavailableException表示确定的失败。事实并非如此：Scylla（与Cassandra不同）在LWT过程中多次检查可用性。因此，在已经发出请求的情况下，它可能引发UnavailableException。 Scylla 4.3.rc1通过返回WriteTimeout解决了此问题。
许多查询语言都包含批处理事务的概念：一个语句，该语句一起执行多个子语句，并返回其应用程序的结果。在Scylla中，我们可能会像这样执行LWT BATCH语句：
BEGIN BATCHUPDATE batch_ret SET a = 3 WHERE键= 1如果lwt_trivial = null; UPDATE batch_ret SET b = 5 WHERE key = 2如果lwt_trivial = null; APPLY BATCH;
IF条件表示这些更新应使用LWT进行。在CQL中，条件是强制性的；我们使用lwt_trivial（在我们的架构中定义的列，但其值始终为null）允许这些更新始终成功。
各个LWT UPDATE语句返回具有[applied]字段的一行，以及该行的键的先验值以及LWT条件中使用的任何字段。批处理的返回值是未记录的，但是可能希望它是与批处理中每个语句的结果相对应的一系列行。确实，有时候是这样：
实际上，UPDATE的返回值是按聚类键排序的，而不是按BATCH语句中写入的顺序排序。结合update返回LWT键的先前值（可能为null！）这一事实，这意味着（通常）不可能弄清楚哪个返回行对应于哪个UPDATE语句。两次更新可能会返回一行，如下所示：
Scylla团队确认这是预期的行为。但是，我们还观察到完全丢失的行。在这里，更新键1和2的BATCH返回的结果集没有键2的任何值：
实际上，这是一个错误，是由Scylla有时（但并非总是如此！）引起的，该结果去除了具有零前键的结果行。 Scylla通过按语句顺序返回批处理结果解决了该问题，这使客户可以可预测地识别出哪个结果对应于哪个更新，并记录了行为。
Scylla的DML文档反复宣称INSERT，UPDATE，DELETE和BATCH都是隔离的（至少在限于单个分区时）。情况并非如此：客户例如仅将元素添加到单个CQL集可以观察到状态{1}和{2}。在通常意义上，不能将这样的历史理解为孤立的，因为没有总的操作顺序可以同时产生两个值。状态{1}的存在意味着2的加法必须跟随1，而状态{1}的存在意味着1的加法必须跟随2。对集合和计数器的非LWT更新基本上是并发的。
此问题不仅限于部分更新-完全替换某些列的值的写入也不孤立。我们在批处理和单行更新中反复观察到隔离违例。在写隔离测试中，我们执行写操作，将一组键中的每个值设置为+ x或-x。对该组的任何读取都应确保每个键具有相同的绝对值。相反，我们观察到如下交易：
在这里，密钥4的值为-5，密钥3的值为-2，密钥5的值为-3：来自三个完全独立的写入的值被混杂在一起。即使在读写一致性级别为ALL的状况良好的群集中，以及在使用标准Scylla客户端的AtomicMonotonicTimestampGenerator时，也会出现此问题。以每秒一千次操作（在读写之间平均分配），我们大约每20秒观察到一次隔离违规。通过量化时间戳，我们可以在少数写入中引起异常。
作者于2013年首次向Cassandra报告了此问题。在2014年，Cassandra意识到他们的读取修复机制也可能违反分区级隔离，因此当时决定不解决该问题。 Scylla的工程师再次报告了这些问题，包括在2017年Cassandra可能无法实现其声称的隔离保证的其他情况。截至2020年9月，面对时间戳冲突提供行级隔离在Cassandra中仍然是一个未解决的问题，文件记录尚未解决，而Cassandra的文档仍然坚持认为写入操作是“在完全行级隔离的情况下进行的”。这个问题继续困扰着用户，这些用户在导致逻辑数据损坏时偶尔会发现此行为。
一些工程师认为，这种行为仍是孤立的：仅仅是Scylla和Cassandra等系统中的写操作并不意味着大多数人会认为写操作。如果将写入理解为“可以根据其他人是否或如何在将来的某个时间写入此信元来设置此单元格的值”，则可以将这种行为隔离。只是Scylla在锻炼我
......