Thankfully, several people have realized the same over the years and took the work by Dr. Leslie Lamport (Paxos) and turned it into scalable solutions like Apache Zookeeper, ETCD, and Chubby. These solutions are wonderful and will always be used to solve hard distributed computing problems. They require a good level of expertise to operate and maintain and usually require a team to support them when they grow really large.

But, sometimes, you have available existing tools that you can use, such as a fully functioning Postgres database. This blog post provides deeper details about how we leveraged Postgres to solve the problem of Distributed Mutual Execution for our invoice generation needs.

Why Not Just SELECT FOR UPDATE?

Postgres already supports SELECT FOR UPDATE or SELECT FOR UPDATE NOWAIT, so why not simply use that? This is a fair argument and would be perfectly valid, but we can do something better and use the underlying mechanism that Postgres uses to acquire locks—enter Postgres Advisory Locks.

There are several advantages to using advisory locks over SELECT FOR UPDATE locking:

• PostgreSQL provides a means for creating locks that have application-defined meanings. This allows you to create locks on items that are not stored in the DB and mean something only to the application (e.g., locking on an arbitrary key that is stored only in application memory).
• The RAW power of locks is exposed in the advisory locks API, so you can achieve fairly sophisticated locking behavior.
• Advisory locks can be session level (connection level) or transaction level, offering flexibility on what level one can lock.
• The cost of an advisory lock when acquired in an optimistic manner (more details later) is trivial, and several thousand such optimistic locks can be acquired at any given time.

WARNING: If you acquire a session level lock from the application, it is the responsibility of the application to explicitly release that lock (otherwise the lock would be held). If you acquire a transaction level advisory lock, Postgres automatically releases the lock when the transaction ends.

NOTE: Advisory locks is a comprehensive topic in Postgres, and the entire list of functions can be found by visiting Admin Functions, and simply searching for "pg_advisory_lock".

To address this problem, we use the hashing library provided by Google Guava. We needed a non-cryptographic fast hash that had great hash distribution properties and also was 64-bit (since we needed to turn a string into a big int).

We settled on the Sip Hash. This is a lesser known but very useful hash function of the “add-rotate-xor” family, which is reasonably fast, has very good distribution properties, and a Guava implementation known to work well.

package com.subskribe.billy.postgres;

import com.google.common.hash.HashCode;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import com.subskribe.billy.validation.Validator;
import java.nio.charset.StandardCharsets;
import java.util.Optional;
import org.apache.commons.lang3.BooleanUtils;
import org.jooq.DSLContext;
import org.jooq.Record;
import org.jooq.Result;

/**
* utility class that uses postgres advisory locks
* to implement application level locking
*/
public class PostgresAdvisoryLock {

   // pg_try_advisory_xact_lock expects bigint as locking key
   private static final String PG_ADVISORY_XACT_LOCK = "SELECT pg_try_advisory_xact_lock(%d)";

   // I chose Sip Hash because it is a decently fast with good unique range
   // this hash function is used in Linux, Haskell and Rust hashtable implementations
   // it is a 64-bit hash and the range is java long
   private static final HashFunction SIP_HASH_FUNCTION = Hashing.sipHash24();

   /**
    * try to acquire an advisory postgres lock with the given String key.
    * the String is converted into a long using a 64 bit non-cryptographic hash
    * the lock is automatically released after the transaction is complete.
    * 
    * if the lock is successful it returns the hash code on which the lock was acquired
    * if the lock was unsuccessful an {@link Optional#empty()} is returned
    *
    * @param dslContext non null DSL context
    * @param key        non-empty lock key
    * @return Optional of hash code if successful {@link Optional#empty()} otherwise
    */
   public static Optional tryAcquireLock(DSLContext dslContext, String key) {
       // calculate hash
       HashCode hashCode = SIP_HASH_FUNCTION.hashBytes(key.getBytes(StandardCharsets.UTF_8));
       long hashKey = hashCode.asLong();

       // use the hash to try locking
       String lockQuery = String.format(PG_ADVISORY_XACT_LOCK, hashKey);
       Result lockResult = dslContext.fetch(lockQuery);

       // Query is guaranteed to return a singleton boolean in the result set.
       if (BooleanUtils.isTrue((Boolean) lockResult.get(0).get(0))) {
           return Optional.of(hashKey);
       }
       return Optional.empty();
   }
}