Important
Disclaimer
This page is part of the MydriaTech Knowledge Base. There is no guarantee of correctness or value of the provided content. Send any feedback and/or corrections to kb at mydriatech dot se.
Copyright © 2017 MydriaTech AB. All rights reserved, but feel free to get inspired by the content.

Background and scope

Reliable persistent counters that work independent of how many tabs a user has open could potentially be very useful. They can for example be used to reliably count the number of page visits over time by a particular client.

This article will show how to achieve this using only the Web Storage API. For comparison and completeness a solution based on Indexed Database API will be shown as well.

Helper functions used in this article

To be able to show the result of scripts in this article next to the script itself in the case the result is delivered via a callback, the helper function mydriatech.createSpanHere() is used to create a marker that will later on be populated by the callback.

(function() {
    "use strict";
    window.mydriatech = window.mydriatech || {};

    /** @return a new span element right after the current script element */
    mydriatech.createSpanHere = function() {
        var script = document.scripts[document.scripts.length-1];
        var span = document.createElement("span");
        script.parentElement.insertBefore(span, script.nextSibling);
        return span;
    };
}());

Detecting if the used APIs are present

To be able to see the output of the code examples in this article, you need to have support for both the Web Storage and Indexed DB APIs. Please note however that having support for the Web Storage API is sufficient to build a reliable counter.

(function() {
    "use strict";
    window.mydriatech = window.mydriatech || {};

    /** @return true if the API is available via window.apiName */
    mydriatech.isApiAvailable = function(apiName) {
        try {
            return apiName in window && window[apiName] !== null;
        } catch (e) {
            return false;
        }
    };
}());

mydriatech.createSpanHere().innerHTML =
    "[Detect] Web Storage API: " + mydriatech.isApiAvailable("localStorage") + "<br/>" +
    "[Detect] Indexed DB API:  " + mydriatech.isApiAvailable("indexedDB");

Actual script output:

The Web Storage API and concurrency

The Web Storage API defined by W3C Recommendation is a well supported standard for storing key-value pairs in the User Agent (client’s browser).

Basic read and write operation

// Store a value as a string, alternative 1
window.localStorage.setItem("somekey", "somevalue");
// Read back the value "somevalue", alternative 1
var value2 = window.localStorage.getItem("somekey");

Since the localStorage is basically a map, you can use the short format to achieve the same:

// Store a value as a string, alternative 2
window.localStorage["somekey"] = "somevalue";
// Read back the value "somevalue", alternative 2
var value1 = window.localStorage["somekey"];

In this basic read-write example, you expect the variable value to be set to somevalue, but what happens if another browser tab runs the same code and tries to update the value of somekey at the same time? In the simple example here, as you probably figured out, this wont make a difference, since we will always end up with the value somevalue.

The illusive storage mutex

If the value to write to the Web Storage depends on the current value, things get trickier. If two instances of the code read the current value at the same time (say 42), each make an increment (by 1) and then write back the new value twice (42+1) we end up with a different result than the expected (42+1+1). The result is clearly not deterministic, since the result will depend both on the current value and the timing of when the code is run.

The User Agent may (or may not) prevent multiple instances of the code from reading and writing to the Web Storage API concurrently, with a storage-mutex. This storage-mutex is owned by exactly one JavaScript event loop at the time which ensures that concurrent updates can’t happen while an event loop is reading and writing.

The event loop in JavaScript comes from the event driven model of the language and your code is always invoked as a result of an event and is allowed to run without interruptions all the way through. So if a storage mutex is present this means no other browsing context (think of it as a thread or browser tab) is allowed to modify the storage and we could implement a counter as:

function simpleIncrementAndGet(key, increment) {
    var currentValue = window.localStorage[key];
    currentValue = currentValue ? parseInt(currentValue) : 0;
    // ...in a perfect mutexed world nothing will update the value in
    //  localStorage after we read it...
    var valueAfterIncrement = currentValue + parseInt(increment);
    // ...and before we write back the result...
    window.localStorage[key] = valueAfterIncrement;
    return valueAfterIncrement;
};
mydriatech.createSpanHere().innerHTML =
    "[Simple Example] simpleCounter: " + simpleIncrementAndGet("simpleCounter", 1);

Actual script output:

Since using mutual exclusion (mutex) means that only one browser tab (browsing context) at the time is allowed to access the Web Storage API at the time, this implies a performance penalty. Every tab has to wait for other tabs to finish their storage operations before it can perform its own operations.

In reality however, concurrent storage operations might not be as common. So it could be argued that implementing a storage mutex would hence impose a very small performance penalty. At the same time, it could also be argued that the risk of conflicting updates would be very low and since the data stored in the client browser could be be wiped or modified by the client at any moment, this is clearly not the right place to store sensitive or critical data.

As the W3C recommendation clearly states, there are no guarantees either way. This however poses a problem when implementing a reliable counter, since we have to assume that no such storage mutex is present.

Moving towards a more robust solution

From the previous section we know that Web Storage counter increments might not be atomic in respect to multiple browsing contexts. There is also no guarantee that the browser has not crashed before a write has been flushed to disk or that the user has wiped or modified the Web Storage.

Log everything - the awkward approach

One approach would be to generate a unique identifier for each browsing context and that each browsing context would log (append) all increments to the Web Storage under separate keys (unique identifiers). Reading the correct value would be to iterate over all available keys of the correct pattern in the Web Storage and summarize all the written log entries. If each update comes with a timestamp, eventually a browsing context selected randomly could purge and aggregate long gone browsing contexts.

This means tweaking the aggregation solution timeouts and probabilities depending on:

  • how often such logs are written to avoid conflicting updates,

  • available Web Storage on the client

and still make the aggregation fast enough for the user not to notice.

This would be hard to say the least.

The "Log everything" approach would probably be the most crash-resistant, since all increments are persisted as soon as possible, but at a terrible cost. In an environment where there is very little control over the data storage this is hardly worth the effort.

Lock, unblock and two smoking variables

The following is an implementation of Algorithm 1 from the paper A Fast Mutual Exclusion Algorithm by Leslie Lamport.

The algorithm uses two variables (in this case two entries in the Web Storage) _x and _y per lock to ensure that the caller is the sole instance running the critical section. If the variables are already set by another instance, the caller backs off for 50 ms and then retries the operation.

In the case where the lock has been held for more than 5 seconds, the lock is forced. This allows recovery in the case where the lock was never released due to that the browser was closed while the lock was held.

(function() {
    "use strict";

    var uniqueId = new Date().getTime() + "_" + (Math.random()*0xffffffff|0);

    /** Execute the callback function with mutual exclusion using the specified key */
    function mutexedExec(key, callback) {
        // Claim X for this browsing context
        window.localStorage[key + "_x"] = uniqueId;
        // Is Y unclaimed?
        var y = window.localStorage[key + "_y"];
        if (y != undefined) {
            var yTime = y.split("_")[0];
            if (yTime < new Date().getTime()-5000) {
                    // More then 5 seconds has elapsed since it was locked, so assume that
                    // the instance holding the lock has crashed and force a claim
                console.log("Forcing lock...");
                    y = undefined;
            }
        }
        if (y == undefined) {
            // Claim Y for this browsing context
            window.localStorage[key + "_y"] = uniqueId;
            // Is X still claimed for this browsing context?
            if (window.localStorage[key + "_x"] == uniqueId) {
                callback();
                // Free Y so other browsing contexts may run
                window.localStorage.removeItem(key + "_y");
            } else {
                // Delay next attempt 50 ms
                setTimeout(function() {
                    if (window.localStorage[key + "_y"] == uniqueId) {
                        callback();
                        // Free Y so other browsing contexts may run
                        window.localStorage.removeItem(key + "_y");
                    } else {
                        // Try again if not this callback is executing
                        setTimeout(mutexedExec(key, callback), 50);
                    }
                }, 50);
            }
        } else {
            // Try again if a callback is executing
            setTimeout(mutexedExec(key, callback), 50);
        }
    };

    /** Perform an atomic increment of the key's value and return the result in a callback. */
    var mutexedIncrementAndGet = function(key, increment, resultCallback) {
        mutexedExec(key, function() {
            var currentValue = window.localStorage[key];
            currentValue = currentValue ? parseInt(currentValue) : 0;
            var valueAfterIncrement = currentValue + parseInt(increment);
            window.localStorage[key] = valueAfterIncrement;
            resultCallback(valueAfterIncrement);
        });
    };

    // Expose API functions under namespace
    window.mydriatech = window.mydriatech || {};
    mydriatech.mutexedIncrementAndGet = mutexedIncrementAndGet;
}())

var spanMutex = mydriatech.createSpanHere()
// Use the naïve example from before but wrapped in a mutex
mydriatech.mutexedIncrementAndGet("mutexedCounter", 1, function(valueAfterIncrement) {
    spanMutex.innerHTML = "[Mutexed Execution] mutexedCounter: " + valueAfterIncrement;
});

Actual script output:

Eventual consistency

Eventual consistency means that at a future point in time and given a finite set of updates, all participants of the algorithm will agree on the state of things. There is also nothing that prevents the participants from agreeing on the state of things after each update, but the paradigm only promises that it eventually will be that way.

The trick we will use to make this happen is to broadcast each local update to all other instances. The best known value to each instance can then be calculated as first read value + local increments + others increments.

To broadcast and receive broadcasts increments we use the storage event by writing each increment to a separate key.

Celebrate the storage event

Whenever the Web Storage is modified by another browsing context, a StorageEvent named storage is triggered.

Storage event attributes

key

The value of this key is being changed or null if the storage is being cleared.

oldValue

The value before the change.

newValue

The value after the change.

url

URL of the document that changed the storage.

storageArea

The affected Storage object.

This happens to be exactly what we need in order to broadcast increments to other browsing contexts.

Eventually a solution takes form

The following code is the eventually consistent counter implementation:

(function() {
    "use strict";

    /** Add an EventListener callback in a bit more user agent agnostic way. */
    var attachEventListener = function(eventName, eventCallback) {
        if (window.addEventListener) {
            window.addEventListener(eventName, eventCallback, false);
        } else {
            window.attachEvent("on"+eventName, function(e) {
                if (!e) { e = window.event; }
                eventCallback(e);
            });
        };
    }

    /**
     * Main prototype/class that keeps track of counters in an eventual
     * consistent manner.
     */
    function EventualConsistentCounters() {
        var t = this;

        var metaDataPostfix = "_update";
        var trackedKeys = [];
        var othersIncs = {};
        var totalIncs = {};
        var baseline = {};

        /** Listen for updates on all tracked storage keys. */
        this.onStorage = function(e) {
            //console.log("storageEvent { key: " + e.key + ", oldValue: " +
            // e.oldValue + ", newValue=" + e.newValue + "}");
            var key;
            for (var i=0; i<trackedKeys.length; i++) {
                if (e.key == (trackedKeys[i] + metaDataPostfix)) {
                        key = trackedKeys[i]; break;
                    }
            }
            if (!key) return;
            // Read the write to the "_update" key of the form { baseline: x,
            // increment: y}
            var update = JSON.parse(e.newValue);
            if (baseline[key] === undefined || baseline[key]>update.baseline) {
                // The event happened before we started incrementing the key
                return;
            }
            // Sum up received increments that has happened after the baseline
            othersIncs[key] = othersIncs[key] + update.increment;
            // Persist the best known value
            writeCurrentValueCondictional(key);
        };

        /** Increment the counter identified by key "key" with "increment". */
        var increaseValue = function(key, increment) {
            increment = parseInt(increment);
            var currentValue = getValue(key);
            if (!baseline[key]) {
                // Reset increments from other instances
                othersIncs[key] = 0;
                // Subscribe to meta storage events for the key
                trackedKeys.push(key);
                // Save a baseline for all future updates
                baseline[key] = currentValue;
                // Reset our internal counter for this key
                totalIncs[key] = 0;
            }
            // Keep track of total increments by this instance
            totalIncs[key] = totalIncs[key] + increment;
            // Broadcast increment as storage event by writing to localStorage
            window.localStorage[key + metaDataPostfix] = JSON.stringify({
                baseline: currentValue,
                increment: increment
            });
            // Persist the best known value
            return writeCurrentValueCondictional(key);
        }

        /** Persist best known estimate of counter (or do nothing) */
        var writeCurrentValueCondictional = function(key) {
            // The new total is the first read value + this instance's
            // increments + other instances increments
            var newTotal = baseline[key] + totalIncs[key] + othersIncs[key]
            var currentValue = getValue(key);
            // Only update the total count if we have a more accurate value
            if (currentValue<newTotal) {
                window.localStorage[key] = newTotal;
            }
            return newTotal;
        };

        /** Return latest value of the counter */
        var getValue = function(key) {
            var currentValue = window.localStorage[key];
            return currentValue ? parseInt(currentValue) : 0;
        }

        // Start listening for storage events as soon as the object is created
        attachEventListener("storage", t.onStorage);
        // Expose API functions
        this.increaseValue = increaseValue;
        this.getValue = getValue;
    }

    var eccs = new EventualConsistentCounters();

    // Expose API functions under namespace
    window.mydriatech = window.mydriatech || {};
    mydriatech.eccInc = eccs.increaseValue;
    mydriatech.eccGet = eccs.getValue;
}());

mydriatech.createSpanHere().innerHTML =
    "[Eventual Consistent] ecCounter: " + mydriatech.eccInc("ecCounter", 1);

Actual script output:

The Indexed Database API and transactions

The Indexed Database API defined by W3C Recommendation is a partially supported standard for storing simple values and hierarchical objects in the User Agent (client’s browser). The API supports indexes and a query language for quick lookup and (most importantly for this article) support for transactions.

Database transactions allow multiple clients to perform read and write operations on the storage as if the client was the sole user of the storage. The API provides serializable isolation level (at least it seems like the storage is locked exclusively for one caller at the time) and it is up to browsing contexts to release the resources once the browsing context is done using the resource.

A reliable counter implementation would look like this:

(function() {
    "use strict";

    var incAndGet = function(key, callback) {
        var request = indexedDB.open("counterDataBase", 1);
        var db;
        /** Initialize object store if needed */
        request.onupgradeneeded = function(event) {
            db = request.result;
            db.createObjectStore("counterObjectStore", {keyPath: "name"});
        };

        // Invoked when database has been initialized and opened
        request.onsuccess = function() {
            db = request.result;
            // Start a read-write transaction
            var tx = db.transaction("counterObjectStore", "readwrite");
            var store = tx.objectStore("counterObjectStore");
            var currentValue;
            store.get(key).onsuccess = function(event) {
                var value = event.target.result;
                if (!value) {
                    // Lazy init if this is the first increment
                    value = { count: 0, name: key };
                }
                value.count++;
                currentValue = value.count;
                store.put(value);
            };
            tx.oncomplete = function() {
                // All requests have succeeded and the transaction has committed.
                db.close();
                callback(currentValue);
            };
        };

        request.onerror = function(e) {
            console.error("Database operation failed: " + e.target.errorCode);
        };
    };

    // Expose API functions under namespace
    window.mydriatech = window.mydriatech || {};
    mydriatech.idbIncAndGet = incAndGet;
}());

var spanIdb = mydriatech.createSpanHere()
mydriatech.idbIncAndGet("idbCounter", function(result) {
        spanIdb.innerHTML = "[Indexed DB] idbCounter: " + result;
});

Actual script output:

Comparison of counter solutions

As discussed in this article there are plenty of strategies for how to implement a reliable counter. The properties of the different solutions are summarized in the two tables below, with and without the presence of a storage mutex.

If you care about the correct sum of all increments in the end, then eventual consistency based on the Web Storage API makes sense.

If you care about each and every intermediate value (for example as a unique page view id), mutual exclusion based on the Web Storage API or (if user agent support does not matter) transactional increments based on the Indexed DB API.

If you don’t really care about missing updates, then stick to the simple approach based on the Web Storage API. As it happens, it will be fully correct anyway on browsers that implement the storage mutex.

Comparison of counter solutions when storage mutex is present
Simple Mutual exclusion Eventual consistency Indexed DB

Missing update condition

Browser crash

Browser crash

Browser crash

Browser crash

Read, delay

No

Instant callback

No

Eventual callback

Read, accuracy

Full

Full

Full

Full

LocalStorage keys/counter

1

2 (+1 temporarily)

2

-

Comparison of counter solutions when storage mutex is not present
Simple Mutual exclusion Eventual consistency Indexed DB

Missing update condition

Concurrent updates

Browser crash

Browser crash

Browser crash

Read, delay

No

Eventual callback

No

Eventual callback

Read, accuracy

Unreliable

Full

Very high

Full

LocalStorage keys/counter

1

2 (+1 temporarily)

2

-

Thanks for reading and happy counting!