Gossip glomers - Challenge 6

1

Hi,

I’m working my way through the gossip glomers (kudos for doing this) and reached the transactions exercise (Challenge #6a: Single-Node, Totally-Available Transactions · Fly Docs). I’ve a couple of questions:

  • Are we supposed to use one of the storage services provided by maelstrom? I assume so but would love hearing what other folks are doing
  • On the first iteration of the exercise, what should I return if I detect that there’s a write cycle? How do I signal that one of the transactions has to abort?
2

If you will use LinKV or SeqKV external service that would be equivalent to implementing External Shared Disk/Storage Architecture with Stateless compute layer. But how would you guarantee Total Availability? (that is required by the task)

You can respond with TxnConflict code error as it is now shown in 6c, but the Maelstrom will probably count it as the reduced availability. The task is to show in your logs that you can (a) detect g0 (check your history manually) (b) abort conflicts, then you can proceed with the transactions. Maelstrom at the moment will not be detecting g0 afaik.

3

The reason why I was asking about using the storage service is the following: with one node unless I do something explicit, the operations in one transaction would be executed in one go and all the incoming transactions would be serialized (in the order the node receives and processes the txn messages) and so there won’t be any dirty writes. If I used something like the LinKV then the operations on it would interleave with the processing of the txn messages. Am I missing something obvious?

You can respond with TxnConflict code error as it is now shown in 6c, but the Maelstrom will probably count it as the reduced availability. The task is to show in your logs that you can (a) detect g0 (check your history manually) (b) abort conflicts, then you can proceed with the transactions. Maelstrom at the moment will not be detecting g0 afaik.

Thanks for the clarification :slightly_smiling_face:

4

But wouldn’t that count as reduced availability?

5

only if you implement it like that. do not implement it like that. do not use global single mutex per database or at least release it once you do single key read/write. then you will get desirable granularity.

as soon as you will not be holding a single mutex during the whole tx execution you will get your local storage fine for having dirty writes and all the other effects. there are some things that must be atomic during the execution, but just don’t lock the whole thing. don’t serialize the whole tx.

you could use external storage. but you will instantly fail Total Availability (TA). plus without coordination, it will be hard if not impossible to do correct tx processing. think of how you would be resolving key write conflicts… you need either tx ordering and mvcc or a locking scheduler, locking is more coordination. coordination means no TA.

anyway, I can tell, this can be solved without any external storage. plus writing replication layer is the most of the fun of this problem. even though the Maelstrom would not punish you if you will not implement it at all! guess why?

thank authors, for this perfect restriction. :raised_hands:

1 Like
6

I should have added that I’m writing the exercises in Typescript (node) which means that by default once I have consumed a txn message, any new incoming txs will be waiting till I process the current one :rofl:. I have worked around by artificially delaying the processing of each tx’s operation to a later moment, which allows node’s event loop to advance and consume a new incomming txn message giving me the interleaving.

:point_up_2: :+1:

7

oh, I assumed you were using Go.

not a problem, though. even though the JS demo is implemented with lin-kv (https://github.com/jepsen-io/maelstrom/blob/main/demo/js/single_key_txn.js) I think their problem statement is a bit different than what fly.io asks todo.

Therefore, for solving fly.io challenge in JS it seems like you still can do it with the following trick (I am sorry, I am not writing node.js for many many years, but that worked for me) - use async function generators as in async function - JavaScript | MDN* like that:

/* jshint esversion: 9 */

// A basic echo server
var node = require('./node');

function timeout(ms) {
    return new Promise(resolve => setTimeout(resolve, ms));
}

async function* tx_step(j) {
  i = 0;
  while (i < 100) {
    i ++;
    await timeout(50);
    yield await Promise.resolve(j + i);
  }
}

async function process_tx(id) {
  for await (const val of tx_step(id)) {
    console.error(val);
  }
}

id = 1;

node.on('echo', function(req) {
  process_tx(id);
  node.reply(req, {type: 'echo_ok', 'echo': req.body.echo});
  id *= 10;
});

node.main();

execute like

~/maelstrom/maelstrom test -w echo --bin ./1.js --node-count 1 --time-limit 10 --concurrency 2 --rate 2 --log-stderr

and you will see that it does the trick:

INFO [2023-04-04 10:44:08,430] jepsen worker 0 - jepsen.util 0	:invoke	:echo	"Please echo 96"
INFO [2023-04-04 10:44:08,431] n0 stderr - maelstrom.process Got {"id":2,"src":"c2","dest":"n0","body":{"echo":"Please echo 96","type":"echo","msg_id":1}}
INFO [2023-04-04 10:44:08,432] n0 stderr - maelstrom.process Sending {
INFO [2023-04-04 10:44:08,432] n0 stderr - maelstrom.process   src: 'n0',
INFO [2023-04-04 10:44:08,432] n0 stderr - maelstrom.process   dest: 'c2',
INFO [2023-04-04 10:44:08,432] n0 stderr - maelstrom.process   body: { type: 'echo_ok', echo: 'Please echo 96', in_reply_to: 1 }
INFO [2023-04-04 10:44:08,432] n0 stderr - maelstrom.process }
INFO [2023-04-04 10:44:08,435] jepsen worker 0 - jepsen.util 0	:ok	:echo	{:type "echo_ok", :echo "Please echo 96", :in_reply_to 1}
INFO [2023-04-04 10:44:08,482] n0 stderr - maelstrom.process 2
INFO [2023-04-04 10:44:08,532] n0 stderr - maelstrom.process 3
INFO [2023-04-04 10:44:08,537] jepsen worker 0 - jepsen.util 0	:invoke	:echo	"Please echo 68"
INFO [2023-04-04 10:44:08,538] n0 stderr - maelstrom.process Got {"id":4,"src":"c2","dest":"n0","body":{"echo":"Please echo 68","type":"echo","msg_id":2}}
INFO [2023-04-04 10:44:08,538] n0 stderr - maelstrom.process Sending {
INFO [2023-04-04 10:44:08,538] n0 stderr - maelstrom.process   src: 'n0',
INFO [2023-04-04 10:44:08,538] n0 stderr - maelstrom.process   dest: 'c2',
INFO [2023-04-04 10:44:08,538] n0 stderr - maelstrom.process   body: { type: 'echo_ok', echo: 'Please echo 68', in_reply_to: 2 }
INFO [2023-04-04 10:44:08,538] n0 stderr - maelstrom.process }
INFO [2023-04-04 10:44:08,539] jepsen worker 0 - jepsen.util 0	:ok	:echo	{:type "echo_ok", :echo "Please echo 68", :in_reply_to 2}
INFO [2023-04-04 10:44:08,583] n0 stderr - maelstrom.process 2
INFO [2023-04-04 10:44:08,589] n0 stderr - maelstrom.process 12
INFO [2023-04-04 10:44:08,632] n0 stderr - maelstrom.process 4
INFO [2023-04-04 10:44:08,640] n0 stderr - maelstrom.process 14
INFO [2023-04-04 10:44:08,683] n0 stderr - maelstrom.process 6
INFO [2023-04-04 10:44:08,691] n0 stderr - maelstrom.process 16
INFO [2023-04-04 10:44:08,733] n0 stderr - maelstrom.process 8
INFO [2023-04-04 10:44:08,743] n0 stderr - maelstrom.process 18

execution interleaves…

even

async function* tx_step(j) {
...
  while (i < 50) {
...
    await timeout(10);
...
  }
}
node.on('echo', async function(req) {
...
  await process_tx(id);
...
});

INFO [2023-04-04 10:57:54,127] jepsen worker 1 - jepsen.util 1	:invoke	:echo	"Please echo 26"
INFO [2023-04-04 10:57:54,129] n0 stderr - maelstrom.process Got {"id":4,"src":"c2","dest":"n0","body":{"echo":"Please echo 26","type":"echo","msg_id":2}}
INFO [2023-04-04 10:57:54,139] n0 stderr - maelstrom.process 101
...
INFO [2023-04-04 10:57:54,253] n0 stderr - maelstrom.process 112
INFO [2023-04-04 10:57:54,263] jepsen worker 0 - jepsen.util 0	:invoke	:echo	"Please echo 62"
INFO [2023-04-04 10:57:54,263] n0 stderr - maelstrom.process 113
INFO [2023-04-04 10:57:54,266] n0 stderr - maelstrom.process Got {"id":5,"src":"c3","dest":"n0","body":{"echo":"Please echo 62","type":"echo","msg_id":1}}
INFO [2023-04-04 10:57:54,274] n0 stderr - maelstrom.process 101
INFO [2023-04-04 10:57:54,277] n0 stderr - maelstrom.process 1002
INFO [2023-04-04 10:57:54,285] n0 stderr - maelstrom.process 103
INFO [2023-04-04 10:57:54,287] n0 stderr - maelstrom.process 1004
INFO [2023-04-04 10:57:54,295] n0 stderr - maelstrom.process 105
8

btw, Aphyr’s solution (maelstrom/single_key_txn.js at main · jepsen-io/maelstrom · GitHub) is generally fine as you can just iterate infinitely over failing CAS ops, but it will render you unavailable under the network partitioning or under the constant presence of conflicts…

1 Like
9

This is what I’m doing for now (inside txn’s message handler)

  const applyTxn = (txn: Array<TransactionAction>) => {
    const action = txn.shift()

    if (action === undefined) {
      return
    }

    const [op, key, value] = action

    log(`[txn] msg_id ${msg_id} src ${src} apply ${action}`)
    if (op === TransactionOperation.Read) {
      result.push([op, key, state.db[key] ?? null])
    } else {
      state.db[key] = value

      result.push(action)
    }

    setImmediate(applyTxn, txn)
  }

The setImmediate gives node a change to do another round in the event loop and poll messages or interleave another transaction handling handler

image
image1531×542 104 KB

10

@johnkoepi do you know if maelstrom checks the replication of transaction operations in 6b?

I just increased the number of nodes from 1 to 2 (without adding any replication logic), ran maelstrom again and it says that “Everything looks good! ヽ(‘ー`)ノ” so it looks like it doesn’t validate it.

11

Though on second thought the challenge just says that writes have to be replicated but it doesn’t specify anything about the consistency expectations so in theory I could replicate the writes after an infinite amount of time and still be valid :thinking:

12

@madtrick it actually does check. but as far as we are given total availability there is no limit on the data staleness. however, as soon as you will begin replicating values it will quickly mention any bad values or inconsistencies there are. this is a big thing in this task to implement correct replication. for example, the writes of the transaction from another node can overlap with the currently executing transaction and overall the system can end up in an inconsistent state. Maelstrom will find out and report.

So, even though there is no limit on data staleness the reads observe the replication is meant to be implemented. This is where the complexity of this task resides and what mainly affects the design choices an author makes.

1 Like
13

Yeah, that’s what I was thinking when I then wrote:

Though on second thought the challenge just says that writes have to be replicated but it doesn’t specify anything about the consistency expectations so in theory I could replicate the writes after an infinite amount of time and still be valid :thinking:

14

I can share a few additional flags that will help to do fuzz-testing besides obvious - increasing concurrency, increasing time limit, increasing rate:

  • making transactions bigger - containing more ops with --max-txn-length 20 means put 20 reads/writes into a tx
  • removing the limit of max writes per key by --max-writes-per-key 10000000, not sure if it affects anything but sounds like something we don’t want to have
  • reducing the amount of keys over which the txns are performing to some very low values with --key-count 2 to test consistency
~/maelstrom/maelstrom test -w txn-rw-register --bin ./maelstrom-txn 
    --node-count 2 --concurrency 10n --time-limit 20 --rate 1000 
    --consistency-models read-committed --availability total --nemesis partition 
    --max-txn-length 20 --max-writes-per-key 10000000 --key-count 2
1 Like
15

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