Silicon JungleSilicon Jungle

Last-writer-wins map

So we've talked about how to create the last-writer-wins algorithm , but how do we use it in practice?

You can apply it to any data-structure you need. The important part is that per value you need to store a version (e.g. [sequence, userId]) to determine when it should be replaced.

In this post we'll be implementing a flat map. The core data-structure will be made of an object where at each key we store a last-writer-wins register.

Last-writer-wins algorithm

For this example we will be separating out the version from the value.

This way, we can store the values however we'd like and still be able to determine when a value should be replaced.

export const create = (sequence, userId) => [sequence, userId]

export const shouldSet = (currentVersion, version) =>
  currentVersion[0] > version[0] ||
  (currentVersion[0] === version[0] && currentVersion[1] > version[1])

Creating a map

It only takes a few additional lines of code to turn a single lww register into a flat map of them.

import * as lww from './lww'

export const create = () => ({})

export const shouldSetChild = (map, key, version) => {
  const currentVersion = map[key]
  return currentVersion === undefined || lww.shouldSet(currentVersion, version)
}

Making local changes

If you update the value at the key 'jungle', you will need to increment the sequence number stored and then notify any other servers or clients that are listening.

import * as lww from './lww'
import * as lwwMap from './lwwMap'

const userId = 'James'

const values = {}
const versions = lwwMap.create()

const applyLocalChange = (versions, values, key, userId, value) => {
  const version = versions[key]
  const sequence = version === undefined ? 0 : version[0] + 1
  const newVersion = lww.create(sequence, userId)
  versions[key] = newVersion
  values[key] = value
  return [key, newVersion, value]
}

const change = applyLocalChange(
  versions,
  values,
  'jungle',
  userId,
  'Hello world'
)
// ...notify other servers or clients

Receiving remote changes

If you receive a change from a remote server, you will need to check if the version is higher than the one you have. If it is, the value will be updated.

// Should be called when you receive a change from a remote server or client.
const applyRemoteChange = (versions, values, key, version, value) => {
  if (lwwMap.shouldSetChild(versions, key, version)) {
    values[key] = value
    versions[key] = version
    return [key, version, value]
  }

  return null
}

Further reading

Learn how to create a simple syncing protocol: simple-syncing .