DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Coding
  3. JavaScript
  4. A Fast Mutex Lamport Lock With JavaScript Promises

A Fast Mutex Lamport Lock With JavaScript Promises

In this post, we look at a more theoretically complex system, the Lamport lock algorithm, and how to incorporate it into our JavaScript.

Swizec Teller user avatar by
Swizec Teller
·
Mar. 31, 17 · Tutorial
Like (6)
Save
Tweet
Share
5.96K Views

Join the DZone community and get the full member experience.

Join For Free


I'm trying something new. Today the video is stronger than the post. Check it out above. 

On Tuesday, I implemented a JavaScript queue backed by local storage. Its goal in life is to ensure we don't lose events when tracking usage funnels on our app.

Yes, losing an event that takes 600ms to send is an edge case.

Yes, we still want to make sure we don't lose anything.

Plus, with a queue, we have more flexibility to send bursts of events to our backend. Firing an XHR request every time a user clicks a button feels excessive. That's why it's going in a queue, and the queue will eventually process it. At first, 1 event is 1 request, and we have a good path forward to send in batches. Because we store the queue in local storage, you don't lose events even if you close your tab before something finishes saving. Hopefully, you come back a second time so we get a chance to process your queue. If you don't, we can't.

Simple, right?

Yep. Stringify a JSON array. Save to local storage. Pull out, JSON parse, add stuff, put back in.

And what if the same user runs multiple tabs? What if some events that you want to track happen without user interaction? And just like that, tabs step on each other's toes, and you lose events because local storage is a shared resource.

Fast Mutex to the Rescue!

Here's how the Lamport lock algorithm works:

You need 2 shared memory locations, A and B.

When a new thread needs the lock, it first sets A to its id. Then it checks if B is free. If B is not free, we retry. If Bis free, we set B to id. Then we check that A is still equal to id.

If A has changed, we're potentially facing a lock contention. So we wait long enough for others to realize we're doing stuff and back off. Then we check that B is still id. If B is not equal to id, then we've lost the lock and we go back to the beginning. If Bis equal to id, it means we've won the lock and we do stuff.

It sounds confusing because it is confusing. Study the flowchart. Drawing it helped me understand how this works. And I'm not sure I could prove that it works.

Here's what the Lamport lock looks like when implemented with JavaScript promises:

get lock() {
    return this._lock(0);
}

_lock(retries) {
    const A = `${this.name}_lock_A`,
          B = `${this.name}_lock_B`;

    const _retry = (resolve, reject) => {
        window.requestAnimationFrame(() =>
            this._lock(retries + 1).then(resolve, reject)
        );
    }

    const _free = (name) => {
        const val = this._getItem(name);
        return Number(val) === 0 || val === undefined || val === null;
    }

    this._setItem(A, this.id);

    return new Promise((resolve, reject) => {
        // retries > 10, force lock
        if (_free(B) || retries > 10) {
            this._setItem(B, this.id);

            if (this._getItem(A) === this.id) {
                // no contention, do stuff
                resolve();
                this._setItem(B, 0);
            }else{
                // possible contention
                window.requestAnimationFrame(() => {
                    if (this._getItem(B) === this.id) {
                        // won lock, do stuff
                        resolve();
                        this._setItem(B, 0);
                    }else{
                        _retry(resolve, reject);
                    }
                });
            }
        }else{
            _retry(resolve, reject);
        }
    });
}

I did it with promises so it's easier to use. You'd do something like this when writing to local storage:

this.lock.then(() => writeStuff())

That's elegant, right? I think it is.

But what does all that lock code do? Well, it implements the Lamport lock algorithm with one small addition.

Our threads – browser tabs – can die before releasing the lock. The user closes the tab, JavaScript error, things like that. That's why we limit retries to <10.

Yes, that's an arbitrary value. No, saving to local storage should never take more than 10 requestAnimationFrames. It's a fast, synchronous operation.

Look at the code and the flowchart side-by-side. I made sure they're the same.

Don't believe that it works? Read Lamport's original paper; it includes correctness proofs.

Watch the video to see it in action.

Thanks to Dan Pupius for the idea.

Lock (computer science) JavaScript

Published at DZone with permission of Swizec Teller, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • A Complete Guide to AngularJS Testing
  • Unlocking the Power of Polymorphism in JavaScript: A Deep Dive
  • How to Develop a Portrait Retouching Function
  • What Should You Know About Graph Database’s Scalability?

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: