Challenge 6: tips

Questions / Help
1

After spending a few hours on challenge 6, I realized that to make progress, I need some tips.

  1. When implementing an in-memory KV store, the simple approach is to store all data in one hash map. To prevent data races during concurrent access, we have to use mutex (I’m using Golang, by the way) for reading and writing operations with the map. This naturally leads to the serialization of all transactions, meaning that no anomalies can occur. However, I have a feeling that challenge 6 should be much trickier. Could you suggest what I should use as data storage to make this challenge work as intended?

  2. Regarding replication, I noticed that write operations for one particular key can go through any node, which means we have a multi-master topology here. How am I supposed to deal with conflicts? Should it be a “last write wins” reconciliation?

@johnkoepi Tagging you here because you are the most active person for challenge 6. I’m happy to hear any suggestions.

2

@krabradosty (1) you are right but only if the mutex is held for a whole transaction. what you can do is to move the global mutex to the granularity of a single Key write / read. Basically, you can think of the Storage like:

interface Storage {
  int read(key: int)
  write(key, val: int)
}

no mutexes on top of the interface.
you have only 2 atomic multithread safe methods that you can use.
Where a transaction is a set of operations = [Op{op, key, val}].

That will do the job.

Regarding (2):

Replication appears only since 6b, but you have Total Availability requirement which means nodes must respond in 100%. Thus, you can pick any strategy you did like to have (either for individual keys or for whole transactions). LWW works fine (as far as you are not restricted with consistency or serializability).

In 6c the reads of committed-only values change only what values tx-reads can observe that has nothing to do with the replication.

IIRC, maeltstrom workload will not test you for consistency over cocurrent updates (iirc it does not send concurrent updates… but maybe does, don’t remember). But it will test you for sure for the consistency over the brain splits and then convergence.

I don’t remember if it is allowed to leave inconsistent transaction write traces during replication, but generally you have a lot of choice for the implementation and it does not require any serializability for txs or linearizability for keys.

1 Like
3

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.