CRDTs and Distributed Consistency - Part 3: Building a distributed counter

Originally published in Streaver's blog.

This is the third part of a series of posts on CRDTs and Distributed Consistency. You can find previous parts on these links:

1. CRDTs and Distributed Consistency - Part 1: Building a distributed counter.
2. CRDTs and Distributed Consistency - Part 2: Building a distributed counter.

Building a peer-to-peer game using the PNCounter, WebRTC and React

The game will be simple, we will increment a distributed counter with the keyboard. The winner will be the client that has the greatest balanced count. I call a balanced count when the number of increments are equal to the number of decrements. So if User A increments 2 units and decrements 4, the user score will be 2. If User B increments 5 and decrements 4 the user score will be 4 and it will be the winner with a total score amount of 7, because 7 increments and 8 decrements happened in total if we count across clients.

The flow of the game is the following:

1. User A joins, this generates a game Id.
2. User A shares the game link with the rest of the participants.
3. Each participants joins.
4. User A starts the game.
5. Each participant presses the left/right arrow keys as fast as possible to increase the score.
6. Fifteen seconds later the games finishes.
7. The winner is shown.
8. You take note of the global score, reload the page and play a second round.

The user that accumulates the most amount of points in N=3 rounds is the winner. Pretty basic, but it will help us cover a lot of missing parts on the usage of CRDTs within a real context.

Extending the PNCounter to be used as an external React store

In order to use the counter with React we need to be able to notify React that changes to the counter happened so React can properly rerender when things change.

The first thing to do is to emit a change event (and other events) when the PNCounter gets incremented, decremented or merged with the state from another agent. In the following example you can see that we need to extend the EventEmitter class and then emit the events:

import EventEmitter from 'events';

// Extend EventEmitter
class PNCounter extends EventEmitter {

  constructor(...) {
    // Call the EventEmitter constructor
    super();
    ...
  }

  public increment(num: number): void {
    this.positive.increment(num);

    this.emit('increment');
    // Emit a change event to notify all subscribed clients about changes
    this.emit('change');
  }

  public decrement(num: number): void {
    ...
    this.emit('decrement');
    this.emit('change');
  }

  public merge(counter: PNCounter) {
    ...
    this.emit('merge');
    this.emit('change');
  }
  ...
}

The next step is to create a hook that allows a user to create a PNCounter and use it across the application.

import PNCounter, { PNCounterId } from './PNCounter';

// Global map of counters
const counters = new Map<PNCounterId, PNCounter>();

// This function creates and cached a counter with a given Id
const createCounter = (id: PNCounterId) => {
  const newCounter = new PNCounter(id);

  counters.set(id, newCounter);

  return newCounter;
};

export default function usePNCounter(id: PNCounterId): PNCounter {
  // Find or create the counter
  const counter: PNCounter = counters.has(id) ? counters.get(id)! : createCounter(id);

  return counter;
}

Now that the counter is initialized and we have a stable reference to it we can subscribe to its changes thanks to it being an EventEmitter.

For this we will make use of the useSyncExternalStore hook that allows us to synchronize React renders with the external store. Moreover, we will use the Redux Selector pattern to fetch or calculate derived values from the counter. The combinations of these two things allows us to be very efficient in terms of renders.

import { isEqual } from 'lodash';
import { useCallback, useRef, useSyncExternalStore } from 'react';
import PNCounter, { PNCounterId } from './PNCounter';
import usePNCounter from './usePNCounter';

export default function usePNCounterSelector<T>(id: PNCounterId, selector: (counter: PNCounter) => T): T {
  const counter = usePNCounter(id);

  const subscribeToCounter = useCallback(
    (callback: () => void) => {
      counter.on('change', callback);
      return () => {
        counter.off('change', callback);
      };
    },
    [counter],
  );

  const previousValue = useRef<T>(selector(counter));

  const getSnapshot = useCallback(() => {
    const newCandidateValue = selector(counter);
    const newValue = isEqual(newCandidateValue, previousValue.current) ? previousValue.current : newCandidateValue;

    previousValue.current = newValue;

    return newValue;
  }, [counter, selector]);

  return useSyncExternalStore(subscribeToCounter, getSnapshot, getSnapshot);
}

Now that we have all the required boilerplate we can start building the actual game. For the communications between peers we are going to use PeerJS a peer-to-peer library built on top of WebRTC.

First let's clarify some things:

1. The code in the article is just sample code, more like pseudo-code, the actual code is much more complex.
2. The final result is not a mesh of clients where all clients are treated equal. For simplicity we are going to say that we have a host client.
3. I will provide very little details on how PeerJS works, sorry!

Sharing state between clients

First we need to create the clients and link them, if you are using PeerJS or will be something like this:

// Client A
const peer = new Peer();
const conn = peer.connect('ClientB');
// on open will be launch when you successfully connect to PeerServer
conn.on('open', function(){
  // here you have conn.id
  conn.send('hi!');
});

peer.on('connection', function(conn) {
  conn.on('data', function(data){
    // Will print 'hi!'
    console.log(data);
  });
});

// Client B
const peer = new Peer();
const conn = peer.connect('ClientA');
// on open will be launch when you successfully connect to PeerServer
conn.on('open', function(){
  // here you have conn.id
  conn.send('hi!');
});

peer.on('connection', function(conn) {
  conn.on('data', function(data){
    // Will print 'hi!'
    console.log(data);
  });
});

Each client can independently increment or decrement the counter and that change will be sent to the the other clients. In order to do that we will just subscribe to the local counter changes, something like this:

...
// On ClientA
const clients = //some how get other connected clients
const counter = usePNCounter('ClientA')

useEffect(() => {
  // This effect subscribes to all remote changes
  // it parses the messages and merges the changes into the local counter
  const clientDataHandler = (data) => {
    const receivedCounter = PNCounter.parse(data.payload);

    counter.merge(receivedCounter);
  }

  clients.forEach((conn) => {
    clientBConnection.on('data', clientDataHandler);
  });

  return () => {
    clients.forEach((conn) => {
      clientBConnection.off('data', clientDataHandler);
    });
  };
}, [counter, clients])

useEffect(() => {
  // This effect subscribes to local changes and pushes them to remote clients
  // You will need to find a way of avoiding infinite loops, because a merge
  // will send a message that will in turn result in another message from remote
  // clients. I will leave this as homework!
  const changeHandler = () => {
    clients.forEach((conn) => {
      clientBConnection.send({
        type: 'counter-state',
        payload: PNCounter.stringify(counter)
      });
    });
  }

  counter.addEventListener('change', changeHandler);

  return () => counter.removeEventListener('change', changeHandler);
}, [counter, clients])

With this ideas you should be able to iterate and build the game I described that the start of the article that uses the PNCounter.

I decided not to share the full code in the article because it would make it too long and boring, but I have a full example working here and the source code here.

Conclusions

Building a simple CRDT like a counter is not that hard, but if you are interested and keep digging into this topic you will see that other types of CRDTs have more complex challenges as I mentioned in the previous part of the series.

Also, using a CRDTs has its challenges, you need to figure out how to connect clients and share that information between them, but both problems can be thought in almost complete isolation from each other, this allows you to use them in many contexts, via the internet, HTTP, WebSocket, SMS, Letters, you name it.

These structures are really useful in distributed computing or realtime apps where network partitions will happen, so the next time you have to build a distributed system you can keep these ideas in mind (or you can send us an email 😉).