Uniqueness with Postgres advisory locks and FNV hashing

River has a unique job insertion feature that'll insert a job, but only if a job doesn't already exist for a set of unique insertion criteria. For example, we might want to stipulate a maximum of one job of a specific kind per queue, or that only one is inserted per hour.

Postgres has built-in ways to guarantee uniqueness with unique constraints and unique indexes, but they're schema-level controls that aren't dynamic enough for River's particular use case around unique jobs.

A naive unique implementation might be implemented like:

1. Check (with a SELECT) whether a job matching the unique criteria exists already.
2. Insert a job if not. Skip insertion otherwise.

The problem with this approach is that it's not safe in the presence of multiple clients, and could easily result in accidentally duplicated unique jobs. Imagine if two concurrently running operations both did their check in (1) in close succession to each other, each finding no existing job, and advancing to step (2). Both would perform their insertion, the result being two of the same unique job instead of the expected one.

Instead, River guarantees uniqueness using transactions and transaction-level advisory locks. Here's the corrected approach:

1. Open a transaction (or subtransaction).
2. Acquire an advisory lock based on the specific parameters of the unique insertion.
3. Check (with a SELECT) whether a job matching the unique criteria exists already.
4. Insert a job if not. Skip insertion otherwise.

An "advisory lock" sounds scary as a concept, but like many things in computer science, it's actually a pretty simple one that's been given a melodramatic name. It's a feature provided by Postgres specifically for applications to use for coordination. Advisory locks have no meaning within the underlying Postgres backend (Postgres uses plenty of locks, just not these ones), but if two clients try to acquire the same advisory lock, Postgres will guarantee that only one of them succeeds.

River opens a transaction, and takes a lock based on the unique job to be inserted:

BEGIN;
SELECT pg_advisory_lock(hash('unique_key|kind=my_unique_job'));

The lock's held for the duration of the transaction, giving the client that acquired it a chance to check for an existing unique job, and insert a new one if appropriate. Another client operating simultaneously would try to acquire the same lock, but be forced to wait until after the first client finished up.

An idiosyncrasy of the advisory lock system is that it requires that lock keys are integers. 64 bits of space is provided, so locks should be a value between -9,223,372,036,854,775,808 and 9,223,372,036,854,775,807.

SELECT pg_advisory_lock(9223372036854775807);

This isn't ideal for application use, many of which (like River) would prefer to send a lock as a more human-friendly string like my_lock_name.

A common way around this is to use a hash function to turn a string into an integer. Well-designed hash functions specialize in taking input and distributing it widely and evenly over their output hash space to minimize the probability of a hash collision.

A nice aspect of Go is that it's a "batteries included" language, and provides some hash functions built into the standard library so that it's not necessary to pull them in from third party dependencies. One of those that we found nearly perfect for this use case is is the FNV (Fowler–Noll–Vo) hash function. FNV isn't a crytographic hash that's insulated against malfeasance, but it's fast and simple, and for our case of trusted clients dealing only with other trusted clients, it's fine.

import "hash/fnv"

// overflow allowed
key := int64(fnv.New64().Write([]byte("my_unique_properties")).Sum64())

The only piece that may not be perfectly intuitive is that the hash produced will be in the uint64 integer space. Postgres' advisory lock keys are also 64 bit integers, but signed, so we have to cast the key to int64. This might overflow its value from a large positive number to a negative one which would be very bad in many situations, but for the purposes of a hash, it's okay.

Go providing it in the standard library is one nice aspect of FNV, but another is that it's trivial to implement in cases where it's not. Ruby's standard library doesn't have FNV built in, and although it can be found in a third party gem, we opted to implement it ourselves so that River's gem could stay dependency free.

Here's the whole thing. It's succinct without even trying to be, and could easily be code golfed down to half this number of LOCs.

module River
  module FNV
    def self.fnv1_hash(str, size:)
      hash = OFFSET_BASIS.fetch(size)
      mask = MASK.fetch(size)
      prime = PRIME.fetch(size)

      str.each_byte do |byte|
        hash *= prime
        hash &= mask # take lower N bits of multiplication product
        hash ^= byte
      end

      hash
    end

    MASK = {
      32 => 0xffffffff, # mask 32 bits long
      64 => 0xffffffffffffffff # mask 64 bits long
    }.freeze

    OFFSET_BASIS = {
      32 => 0x811c9dc5,
      64 => 0xcbf29ce484222325
    }.freeze

    PRIME = {
      32 => 0x01000193,
      64 => 0x00000100000001B3
    }.freeze
  end
end

In case you try this at home, make sure to compare results against the test suite of another implementation. You probably didn't get it right on the first try.

Advisory locks provide 64 bits of key space which is quite a lot. Enough so to make accidental key collisions unlikely within the bounds of anything even resembling reasonable use.

However, for users who are making use of advisory locks in other ways and who are paranoid about collisions, River can be configured with an advisory lock "namespace". 32 bits of leading space to which all locks it takes will be constrained. By choosing a prefix for River and avoiding it for their own uses, applications can better guarantee that conflicts don't happen.

// Config is the configuration for a River Client.
type Config struct {
    // AdvisoryLockPrefix is a configurable 32-bit prefix that River will use
    // when generating any key to acquire a Postgres advisory lock. All advisory
    // locks share the same 64-bit number space, so this allows a calling
    // application to guarantee that a River advisory lock will never conflict
    // with one of its own by cordoning each type to its own prefix.
    //
    // If this value isn't set, River defaults to generating key hashes across
    // the entire 64-bit advisory lock number space, which is large enough that
    // conflicts are exceedingly unlikely. If callers don't strictly need this
    // option then it's recommended to leave it unset because the prefix leaves
    // only 32 bits of number space for advisory lock hashes, so it makes
    // internally conflicting River-generated keys more likely.
    AdvisoryLockPrefix int32

    ...
}

Once again, FNV makes this easy to implement since it comes in both 32-bit and 64-bit variants. Calculating a lock key with a prefix is almost the same as calculating one without, except we shift the 32-bit prefix onto the left half of the number, and use a 32-bit FNV hash for the rest:

// overflow allowed
key := int64(uint64(h.configuredPrefix)<<32 | uint64(h.hash32.Sum32()))