Journal

[huachaohuang]

This discussion is about the design and implementation of Journal.

Quorum Journal

We are going to need a strongly-consistent journal to persist recent updates.

One possible implementation is a QuorumJournal. Let's say we have three compute units and three journal units. One of the compute units should be elected as the leader. The algorithm looks like this:

• Any compute units can request votes from journal units
• If a compute unit receives majority votes from journal units, it becomes the leader.
• On client updates, the leader sends the updates to all journal units.
• When the leader receives ok responses from majority journal units, the updates are regarded as committed.

Some more details:

• Every leader election has a term (like Raft)
• The leader should send the election term with any updates to journal units.
• If a journal unit receive updates with a term that doesn't match the latest election, it should reject the updates

However, there are still a lot of details needed to be figured out. For example, how do we do membership changes?

We can not simply apply the Raft consensus algorithm here because we disaggregate the compute and journal.

References

• LogDevice Distributed Consensus
• Virtual Consensus in Delos

[huachaohuang]

@PatrickNicholas This is what we discussed offline before. Maybe some details are missing, I will add more gradually. Welcome to help with this topic :)

[w41ter]

Good, regarding the implementation details, I also have an idea: to introduce a new role on the basis of raft, which is played by the computing node, so that the accumulated engineering practice on raft can be directly used, eg joint consensus, log replicate pipeline.

[huachaohuang]

Well, we can use the roles from Paxos: proposer, accepter, learner. So the leader compute unit is the proposer, all journal units are accepters and learners, while follower compute units are learners.

[huachaohuang]

I think the consensus algorithm from LogDevice looks great! LogDevice employs a decoupled architecture, so its design fits our journal very well.

[huachaohuang]

Boki: Stateful Serverless Computing with Shared Logs another paper about logs. I haven't checked it carefully, just put it here as a reference.

[tisonkun]

Here is the talk from the author https://www.youtube.com/watch?app=desktop&v=SgfLK1p3dx4 .

[zojw]

https://bookkeeper.apache.org/docs/4.5.1/development/protocol/ maybe bookkeeper protocol also can be a reference - -

[gengliqi]

How about binding the one journal unit to one compute unit? In other words, a compute unit can only send updates to its corresponding journal unit. The journal unit is just used for persisting data, like a remote disk.
If so, we don't need to change much of code of existing implementations. (Maybe just change some code path of using synchronous I/O)

I guess the only reason to use the method you mentioned is to reduce one network round-trip time. But if the compute unit is close to its corresponding journal unit or the compute unit is close to each other, the optimization effect is no longer obvious.

[huachaohuang]

Yes, the quorum method saves one network round-trip.
While treating a journal unit as a remote disk is feasible, we need to consider the situation when the number of journal units and compute units doesn't match. For example, it is possible that we have two compute units (primary and secondary) but five journal units (for durability).

[levy5307]

• If a compute unit receives majority votes from journal units, it becomes the leader.

Do you mean the leader compute unit is elected by journal units? Why don't we elect leader compute unit by all of the compute units?
By the way, Hermes is a replication protocol suitable for states maintained in memory with Low latency and high throughput. It allows write to(read from) all replicas

[huachaohuang]

Do you mean the leader compute unit is elected by journal units?

Yes, for the quorum journal.

Why don't we elect leader compute unit by all of the compute units?

Hmm, this may also work. Or simply use a distributed lock service like ZooKeepr. Although I intend not to introduce external dependencies except those provided by the platform, like S3, etc.

Hermes also looks interesting, let me take a look first.

[tisonkun]

@huachaohuang I second to @levy5307 that replication is different from leader election in some way. If there is a metadata service in our system (the Kernel, perhaps), we can adopt a quorum base replication.

Apache BookKeeper adopts this way as @zojw mentioned at #70 (comment). Here are more references:

• https://fpj.systems/2015/01/23/so-many-ways-of-replicating/
• https://zookeeper.apache.org/doc/r3.3.3/bookkeeperOverview.html
• http://web.mit.edu/6.033/2005/wwwdocs/quorum_note.html

... where ZK/etcd can act as the metadata service.

Although I intend not to introduce external dependencies except those provided by the platform, like S3, etc.

You can check out the talk "How We Build Firebolt" for how Firebolt employs a metadata service on cloud. We don't have to reimplement everything since we're aimed at cooperating on cloud ;-) (at the first place, at least)

cc @w41ter-l

[huachaohuang]

Thanks for your information. I need a more detailed design on this topic. I think @w41ter-l is working on it.