Last week, I’ve been lucky to start working on uMap, an open-source map-making tool to create and share customizable maps, based on Open Street Map data.

My goal is to add real-time collaboration to uMap, but we first want to be sure to understand the issue correctly. There are multiple ways to solve this, so one part of the journey is to understand the problem properly (then, we’ll be able to chose the right path forward).

Part of the work is documenting it, so expect to see some blog posts around this in the future.

Installation

I’ve started by installing uMap on my machine, made it work and read the codebase. uMap is written in Python and Django, and using old school Javascript, specifically using the Leaflet library for SIG-related interface.

Installing uMap was simple. On a mac:

1. Create the venv and activate it

python3 -m venv venv
source venv/bin/activate
pip install -e .

1. Install the deps : brew install postgis (this will take some time to complete)

createuser umap
createdb umap -O umap
psql umap -c "CREATE EXTENSION postgis"

1. Copy the default config with cp umap/settings/local.py.sample umap.conf

# Copy the default config to umap.conf
cp umap/settings/local.py.sample umap.conf
export UMAP_SETTINGS=~/dev/umap/umap.conf
make install
make installjs
make vendors
umap migrate
umap runserver

And you’re done!

On Arch Linux, I had to do some changes, but all in all it was simple:

createuser umap -U postgres
createdb umap -O umap -U postgres
psql umap -c "CREATE EXTENSION postgis" -Upostgres

Depending on your installation, you might need to change the USER that connects the database.

The configuration could look like this:

DATABASES = {
    "default": {
        "ENGINE": "django.contrib.gis.db.backends.postgis",
        "NAME": "umap",
        "USER": "postgres",
    }
}

How it’s currently working

With everything working on my machine, I took some time to read the code and understand the current code base.

Here are my findings :

• uMap is currently using a classical client/server architecture where :
• The server is here mainly to handle access rights, store the data and send it over to the clients.
• The actual rendering and modifications of the map are directly done in JavaScript, on the clients.

The data is split in multiple layers. At the time of writing, concurrent writes to the same layers are not possible, as one edit would potentially overwrite the other. It’s possible to have concurrent edits on different layers, though.

When a change occurs, each DataLayer is sent by the client to the server.

• The data is updated on the server.
• If the data has been modified by another client, an HTTP 422 (Unprocessable Entity) status is returned, which makes it possible to detect conflicts. The users are prompted about it, and asked if they want to overwrite the changes.
• The files are stored as geojson files on the server as {datalayer.pk}_{timestamp}.geojson. A history of the last changes is preserved (The default settings preserves the last 10 revisions).
• The data is stored in a Leaflet object and backups are made manually (it does not seem that changes are saved automatically).

Data

Each layer consists of:

• On one side are the properties (matching the _umap_options), and on the other, the geojson data (the Features key).
• Each feature is composed of three keys:
• geometry: the actual geo object
• properties: the data associated with it
• style: just styling information which goes with it, if any.

Real-time collaboration : the different approaches

Behind the “real-time collaboration” name, we have :

1. The streaming of the changes to the clients: when you’re working with other persons on the same map, you can see their edits at the moment they happen.
2. The ability to handle concurrent changes: some changes can happen on the same data concurrently. In such a case, we need to merge them together and be able to
3. Offline editing: in some cases, one needs to map data but doesn’t have access to a network. Changes happen on a local device and is then synced with other devices / the server ;

Keep in mind these notes are just food for toughs, and that other approaches might be discovered on the way

I’ve tried to come up with the different approaches I can follow in order to add the collaboration features we want.

• JSON Patch and JSON Merge Patch: Two specifications by the IETF which define a format for generating and using diffs on json files. In this scenario, we could send the diffs from the clients to the server, and let it merge everything.
• Using CRDTs: Conflict-Free Resolution Data Types are one of the other options we have lying around. The technology has been used mainly to solve concurrent editing on text documents (like etherpad-lite), but should work fine on trees.

JSON Patch and JSON Merge Patch

I’ve stumbled on two IETF specifications for JSON Patch and JSON Merge Patch which respectively define how JSON diffs could be defined and applied.

There are multiple libraries for this, and at least one for Python, Rust and JS.

It’s even supported by the Redis database, which might come handy in case we want to stream the changes with it.

If you’re making edits to the map without changing all the data all the time, it’s possible to generate diffs. For instance, let’s take this simplified data (it’s not valid geojson, but it should be enough for testing):

source.json

{
    "features": [
        {
            "key": "value"
        }
    ],
    "not_changed": "whatever"
}

And now let’s add a new object right after the first one :

destination.geojson

{
    "features": [
        {
            "key": "value"
        },
        {
            "key": "another-value"
        }
    ],
    "not_changed": "whatever"
}

If we generate a diff:

pipx install json-merge-patch
json-merge-patch create-patch source.json destination.json
{
    "features": [
        {
            "key": "value"
        },
        {
            "key": "another-value"
        }
    ]
}

Multiple things to note here:

1. It’s a valid JSON object
2. It doesn’t reproduce the not_changed key
3. But… I was expecting to see only the new item to show up. Instead, we are getting two items here, because it’s replacing the “features” key with everything inside.

This is actually what the specification defines:

4.1. add

The “add” operation performs one of the following functions, depending upon what the target location references:

o If the target location specifies an array index, a new value is inserted into the array at the specified index.

o If the target location specifies an object member that does not already exist, a new member is added to the object

o If the target location specifies an object member that does exist, that member’s value is replaced.

It seems too bad for us, as this will happen each time a new feature is added to the feature collection.

It’s not working out of the box, but we could probably hack something together by having all features defined by a unique id, and send this to the server. We wouldn’t be using vanilla geojson files though, but adding some complexity on top of it.

At this point, I’ve left this here and went to experiment with the other ideas. After all, the goal here is not (yet) to have something functional, but to clarify how the different options would play off.

Using CRDTs

I’ve had a look at the two main CRDTs implementation that seem to get traction these days : Automerge and Yjs.

I’ve first tried to make Automerge work with Python, but the Automerge-py repository is outdated now and won’t build. I realized at this point that we might not even need a python implementation:

In this scenario, the server could just stream the changes from one client to the other, and the CRDT will guarantee that the structures will be similar on both clients. It’s handy because it means we won’t have to implement the CRDT logic on the server side.

Let’s do some JavaScript, then. A simple Leaflet map would look like this:

import L from 'leaflet';
import 'leaflet/dist/leaflet.css';

// Initialize the map and set its view to our chosen geographical coordinates and a zoom level:
const map = L.map('map').setView([48.1173, -1.6778], 13);
// Add a tile layer to add to our map, in this case using Open Street Map
L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
    maxZoom: 19,
    attribution: '© OpenStreetMap contributors'
}).addTo(map);
// Initialize a GeoJSON layer and add it to the map
const geojsonFeature = {
    "type": "Feature",
    "properties": {
        "name": "Initial Feature",
        "popupContent": "This is where the journey begins!"
    },
    "geometry": {
        "type": "Point",
        "coordinates": [-0.09, 51.505]
    }
};
const geojsonLayer = L.geoJSON(geojsonFeature, {
    onEachFeature: function (feature, layer) {
        if (feature.properties && feature.properties.popupContent) {
            layer.bindPopup(feature.properties.popupContent);
        }
    }
}).addTo(map);
// Add new features to the map with a click
function onMapClick(e) {
    const newFeature = {
        "type": "Feature",
        "properties": {
            "name": "New Feature",
            "popupContent": "You clicked the map at " + e.latlng.toString()
        },
        "geometry": {
            "type": "Point",
            "coordinates": [e.latlng.lng, e.latlng.lat]
        }
    };
    // Add the new feature to the geojson layer
    geojsonLayer.addData(newFeature);
}
map.on('click', onMapClick);

Nothing fancy here, just a map which adds markers when you click. Now let’s add automerge:

We add a bunch of imports, the goal here will be to sync between tabs of the same browser. Automerge announced an automerge-repo library to help with all the wiring-up, so let’s try it out!

import { DocHandle, isValidAutomergeUrl, Repo } from '@automerge/automerge-repo'
import { BroadcastChannelNetworkAdapter } from '@automerge/automerge-repo-network-broadcastchannel'
import { IndexedDBStorageAdapter } from "@automerge/automerge-repo-storage-indexeddb"
import { v4 as uuidv4 } from 'uuid';

These were just import. Don’t bother too much. The next section does the following:

• Instantiate an “automerge repo”, which helps to send the right messages to the other peers if needed ;
• Add a mechanism to create and initialize a repository if needed,
• or otherwise look for an existing one, based on a hash passed in the URI.

// Add an automerge repository. Sync to 
const repo = new Repo({
    network: [new BroadcastChannelNetworkAdapter()],
    storage: new IndexedDBStorageAdapter(),
});

// Automerge-repo exposes an handle, which is mainly a wrapper around the library internals.
let handle: DocHandle<unknown>
const rootDocUrl = </span><span class="si">${</span><span class="nb">document</span><span class="p">.</span><span class="nx">location</span><span class="p">.</span><span class="nx">hash</span><span class="p">.</span><span class="nx">substring</span><span class="p">(</span><span class="mf">1</span><span class="p">)</span><span class="si">}</span><span class="sb">
if (isValidAutomergeUrl(rootDocUrl)) {
    handle = repo.find(rootDocUrl);
    let doc = await handle.doc();
    // Once we've found the data in the browser, let's add the features to the geojson layer.
    Object.values(doc.features).forEach(feature => {
        geojsonLayer.addData(feature);
    });
} else {
    handle = repo.create()
    await handle.doc();
    handle.change(doc => doc.features = {});
}

Let’s change the onMapClick function:

function onMapClick(e) {
    const uuid = uuidv4();
    // ... What was there previously
    const newFeature["properties"]["id"] = uuid;

    // Add the new feature to the geojson layer.
    // Here we use the handle to do the change.
    handle.change(doc => { doc.features[uuid] = newFeature});
}

And on the other side of the logic, let’s listen to the changes:

handle.on("change", ({doc, patches}) => {
    // "patches" is a list of all the changes that happened to the tree.
    // Because we're sending JS objects, a lot of patches events are being sent.
    // 
    // Filter to only keep first-level events (we currently don't want to reflect
    // changes down the tree — yet)
    console.log("patches", patches);
    let inserted = patches.filter(({path, action}) => {
        return (path[0] == "features" && path.length == 2 && action == "put")
    });

    inserted.forEach(({path}) => {
        let uuid = path[1];
        let newFeature = doc.features[uuid];
        console.log(Adding a new feature at position </span><span class="si">${</span><span class="nx">uuid</span><span class="si">}</span><span class="sb">)
        geojsonLayer.addData(newFeature);
    });
});

And… It’s working, here is a little video capture of two tabs working together :-)

It’s very rough, but the point was mainly to see how the library can be used, and what the API looks like. I’ve found that :

• The patches object that’s being sent to the handle.on subscribers is very chatty: it contains all the changes, and I have to filter it to get what I want.
• I was expecting the objects to be sent on one go, but it’s creating an operation for each change. For instance, setting a new object to a key will result in multiple events, as it will firstly create the object, and the populate it.
• Here I need to keep track of all the edits, but I’m not sure how that will work out with for instance the offline use-case (or with limited connectivity). That’s what I’m going to find out next week, I guess :-)
• The team behind Automerge is very welcoming, and was prompt to answer me when needed.
• There seem to be another API Automerge.getHistory(), and Automerge.diff() to get a patch between the different docs, which might prove more helpful than getting all the small patches.

We’ll figure that out next week, I guess!