Adding Real-Time Collaboration to uMap, second week


I continued working on uMap, an open-source map-making tool to create and share customizable maps, based on Open Street Map data.

Here is a summary of what I did:

  • I reviewed, rebased and made some minor changes to a pull request which makes it possible to merge geojson features together ;
  • I’ve explored around the idea of using SQLite inside the browser, for two reasons : it could make it possible to use the Spatialite extension, and it might help us to implement a CRDT with cr-sqlite ;
  • I learned a lot about the SIG field. This is a wide ecosystem with lots of moving parts, which I understand a bit better now.

The optimistic-merge approach

There were an open pull request implementing an “optimistic merge”. We spent some time together with Yohan to understand what the pull request is doing, discuss it and made a few changes.

Here’s the logic of the changes:

  1. On the server-side, we detect if we have a conflict between the incoming changes and what’s stored on the server (is the last document save fresher than the IF-UNMODIFIED-SINCE header we get ?) ;
  2. In case of conflict, find back the reference document in the history (let’s name this the “local reference”) ;
  3. Merge the 3 documents together, that is :
  4. Find what the the incoming changes are, by comparing the incoming doc to the local reference.
  5. Re-apply the changes on top of the latest doc.

One could compare this logic to what happens when you do a git rebase. Here is some pseudo-code:

def merge_features(reference: list, latest: list, incoming: list):
    """Finds the changes between reference and incoming, and reapplies them on top of latest."""
    if latest == incoming:
        return latest

<span class="n">reference_removed</span><span class="p">,</span> <span class="n">incoming_added</span> <span class="o">=</span> <span class="n">get_difference</span><span class="p">(</span><span class="n">reference</span><span class="p">,</span> <span class="n">incoming</span><span class="p">)</span>

<span class="c1"># Ensure that items changed in the reference weren't also changed in the latest.</span>
<span class="k">for</span> <span class="n">removed</span> <span class="ow">in</span> <span class="n">reference_removed</span><span class="p">:</span>
    <span class="k">if</span> <span class="n">removed</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">latest</span><span class="p">:</span>
        <span class="k">raise</span> <span class="n">ConflictError</span>

<span class="n">merged</span> <span class="o">=</span> <span class="n">copy</span><span class="p">(</span><span class="n">latest</span><span class="p">)</span>
<span class="c1"># Reapply the changes on top of the latest.</span>
<span class="k">for</span> <span class="n">removed</span> <span class="ow">in</span> <span class="n">reference_removed</span><span class="p">:</span>
    <span class="n">merged</span><span class="o">.</span><span class="n">delete</span><span class="p">(</span><span class="n">removed</span><span class="p">)</span>

<span class="k">for</span> <span class="n">added</span> <span class="ow">in</span> <span class="n">incoming_added</span><span class="p">:</span>
    <span class="n">merged</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">added</span><span class="p">)</span>

<span class="k">return</span> <span class="n">merged</span>

The pull request is not ready yet, as I still want to add tests with real data, and enhance the naming, but that’s a step in the right direction :-)

Using SQLite in the browser

At the moment, (almost) everything is stored on the server side as GeoJSON files. They are simple to use, to read and to write, and having them on the storage makes it easy to handle multiple revisions.

I’ve been asked to challenge this idea for a moment. What if we were using some other technology to store the data? What would that give us? What would be the challenges?

I went with SQLite, just to see what this would mean.

  • SQLite is originally not made to work on a web browser, but thanks to Web Assembly, it’s possible to use it. It’s not that big, but the library weights 2Mb.
  • With projects such as CR-SQLite, you get a way to add CRDTs on top of SQLite databases. Meaning that the clients could send their changes to other clients or to the server, and that it would be easy to integrate ;
  • The clients could retrieve just some part of the data to the server (e.g. by specifying a bounding box), which gives it the possibility to not load everything in memory if that’s not needed.

I wanted to see how it would work, and what would be the challenges around this technology. I wrote a small application with it. Turns out writing to a local in-browser SQLite works.

Here is what it would look like:

  • Each client will get a copy of the database, alongside a version ;
  • When clients send changes, you can just send the data since the last version ;
  • Databases can be merged without loosing data, the operations done in SQL will trigger writes to a specific table, which will be used as a CRDT.

I’m not sure SQLite by itself is useful here. It sure is fun, but I don’t see what we get in comparison with a more classical CRDT approach, except complexity. The technology is still quite young and rough to the edges, and uses Rust and WebASM, which are still strange beasts to me.

Here are some interesting projects I’ve found this week :

  • Leaflet.offline allows to store the tiles offline ;
  • geojson-vt uses the concept of “vector tiles” I didn’t know about. Tiles can return binary or vectorial data, which can be useful to just get the data in one specific bounding box This allows us for instance to store GeoJSON in vector tiles.
  • mapbox-gl-js makes it possible to render SIG-related data using WebGL (no connection with Leaflet)
  • leaflet-ugeojson and leaflet.Sync allows multiple people to share the same view on a map.

Two libraries seems useful for us:

  • Leaflet-GeoSSE makes it possible to use SSE (Server Sent Events) to update local data. It uses events (create, update, delete) and keys in the GeoJSON features..
  • Leaflet Realtime does something a bit similar, but doesn’t take care of the transport. It’s meant to be used to track remote elements (a GPS tracker for instance)

I’m noting that:

  • In the two libraries, unique identifiers are added to the features to allow for updates.
  • None of these libraries makes it possible to track local changes. That’s what’s left to find.

How to transport the data?

One of the related subjects is transportation of the data between the client and the server. When we’ll get the local changes, we’ll need to find a way to send this data to the other clients, and ultimately to the server.

There are multiple ways to do this, and I spent some time trying to figure out the pros and cons of each approach. Here is a list:

  • WebRTC, the P2P approach. You let the clients talk to each other. I’m not sure where the server fits in this scenario. I’ve yet to figure-out how this works out in real-case scenarii, where you’re working behind a NAT, for instance. Also, what’s the requirement on STUN / Turn servers, etc.
  • Using WebSockets seems nice at the first glance, but I’m concerned about the resources this could take on the server. The requirement we have on “real-time” is not that big (e.g. if it’s not immediate, it’s okay).
  • Using Server Sent Events is another way to solve this, it seems lighter on the client and on the server. The server still needs to keep connexion opens, but I’ve found some proxies which will do that for you, so it would be something to put between the uMap server and the HTTP server.
  • Polling means less connexion open, but also that the server will need to keep track of the messages the clients have to get. It’s easily solvable with a Redis queue for instance.

All of these scenarii are possible, and each of them has pros and cons. I’ll be working on a document this week to better understand what’s hidden behind each of these, so we can ultimately make a choice.

Server-Sent Events (SSE)

Here are some notes about SSE. I’ve learned that:

  • SSE makes it so that server connections never ends (so it consumes a process?)
  • There is a library in Django for this, named django-eventstream
  • Django channels aims at using ASGI for certain parts of the app.
  • You don’t have to handle all this in Django. It’s possible to delegate it to pushpin, a proxy, using django-grip

It’s questioning me in terms of infrastructure changes.