# Under which conditions is it possible to scale a distributed log with checksums?

This question is related to Amazon's QLDB, but my question is about the generic architecture of such a software system. The question arises from the fact that Amazon advertises the service as "highly scalable".

## System Definition

So, let's forget about Amazon and dive into the abstract software system. We want to develop a software system that stores a log of all transactions that were committed to our database. Each of these transactions should have a cryptographic checksum. The checksum of the previous transaction is used as an input of the current transaction to ensure that no previous transaction can be changed.

This might not be the standard approach, but we could implement it similar to this:

checksum(T) = checksum(checksum(code) + checksum(Tprev))


This defines that the checksum for the current transaction T is calculated from the checksum of the code combined with the checksum of the previous transaction.

This will be an unbalanced Merkle tree that always extends to one side only.

               .
.
.
Hash 3      o
/ \
Hash 2    o  T3
/ \
Hash 1  o  T2
/
T1


We want to develop this system as scalable as possible. Scalability in this case can be split into scale-on-read and scale-on-write.

Scalability in this context means that we can increase the throughput (in number of operations per second) by adding more servers. For read operations is typically done either with a load balancer or by requesting the resource from one random server from a list of servers (round robin). For write operations it's a bit more difficult, but if data is clearly separated it can often be achieved with sharding/partitioning (e.g. by choosing the responsible server according to a hash value or a date).

## Distributability / Scalability (=My thoughts about the problem)

I read about Raft as an algorithm for consensus in distributed systems. In my opinion, Raft seems to fit the problem, because according to Wikipedia Raft ensures "that each node in the cluster agrees upon the same series of state transitions". This is about what we want. I think as the very first condition for our system, we need to make sure that the order of state transitions (=transactions / log entries) is exactly the same. If the order gets changed, the hash sums will be incorrect.

However, to my understanding Raft uses an elected leader that is responsible for handling all update operations. I.e., as far as I understood Raft only adds scalability to the read operations. All update operations go through one dedicated Master node.

As another consensus algorithm we also have Majority Consensus. With Majority Consensus there is a defined number of nodes that need to agree upon a change of state. These nodes can change between transactions. However, with hash sums we get the additional complication that only nodes who are already at the latest state can calculate the new hash sum correctly. Thus, after we performed transaction T1 on k nodes, only those k nodes can participate in the next transaction T2. All other nodes have to wait until the receive transaction T1 or otherwise they would calculate the wrong hash sum. Or to use other words: A node violates the condition that the order of transactions must always remain the same if it did not apply T1 yet, but applies T2 and only later gets the update for T1. The order would then be (T2 -> T1 for this node instead of T1 -> T2).

This means, that in my opinion also Majority Consensus does not bring any scalability to write operations.

## Question

My impression from my own thoughts is that it is not possible at all to have any scale-on-write (within one log) at all.

Am I missing some algorithm or can somebody proof that it is never possible to achieve scalability on write if we want to calculate the checksum for each transaction based on the checksum from the previous transaction?

Can we made a small trade-off to allow us to gain scalability-on-write without losing correctness over time (something like eventual consistency)?

Are there any requirements for read scalability? I think that with the right consensus algorithm (Raft?) we could basically send read operations to any available server and always get the correct result. That means read scalability would be achievable.

• Can you explain your "scalability to write operations"? – Apass.Jack Dec 14 '18 at 12:07
• I tried to clarify it with this sentence. Does this answer your question? "Scalability in this context means that we can increase the throughput (in number of operations per second) by adding more servers. This is typically done either with a load balancer or by requesting the resource from one random server from a list of servers (round robin)." – Aufziehvogel Dec 14 '18 at 14:57
• Suppose that system is allowed to fail for a chance up to 0.000000001. What would you think, then? – Apass.Jack Dec 14 '18 at 20:30
• Do you mean fail = reject the transaction or fail = store the transaction with a wrong hash value? The first one seems totally okay for me, even with a higher failure rate (this would be a question of availability, so up to 0.0001 rejection rate would seem totally OK). But even having a very low rate of wrong hashes might be an interesting case if there is a huge performance increase on the other side. – Aufziehvogel Dec 14 '18 at 22:28