LockBox - Collection structure for managing multiple locks

[CMCDragonkai]

Specification

Both EFS and PK are currently using collections of locks structure. This is necessary when dealing with multiple locks, and some tricks to eliminate deadlocks.

One of the things is to have locks identified by string keys. Sorting these string keys deterministically, so that multiple locks are always locked in the same order. It's also important to filter these locks by uniqueness, so the request of the same lock twice is prevented. Thus the locks requested is always an "ordered set".

As an extension, it's also possible to introduce structured locks. This enables a more detailed fine-grained locking to avoid https://en.wikipedia.org/wiki/Giant_lock problems. And by this I mean that you can lock ['a', 'b'] and ['a'], where 'a' is on top of ['a', 'b']. Think of a prefix trie, where each element of the array identifies a level. This can be applied to nested structures for example where you may have a level identifying a file, and within each file, there are blocks. You can lock specific blocks, or you can lock the entire file. To do this you now have a vertical axis to consider as well. To prevent deadlocks, you need to sort them by shortest-prefix and remove duplicates, but also remove longer-prefixes.

For example:

lock(['a', 'b', 'c'], ['a', 'b'])

Is equivalent to:

lock(['a', 'b'])

There's no need to lock ['a', 'b', 'c'] if you're already locking ['a', 'b'].

This would require implementing a prefix trie structure, it's bit more complex, so we will add this as an extension later.

The first part is just flat LockBox based on what we already have implemented in EFS and PK.

The LockBox should be generic, or it can deal with all of the lock classes that we already have. If generic, a lockbox can only contain one specific type of locks. If heterogenous, we would need to have a type specifier on what kind of lock to use. We could do something like:

class LockBox<T> {
  public async lock(c: T)
}

const lockBox = new LockBox<Lock | RWLockWriter>;

But the exact "acquisition" of the lock resource is different. In RWLockReader, there's read and write. While Lock only has lock. You would also need to pass in the the method:

acquire: (l: T) => ResourceAcquire<T>

Along with T so that LockBox knows how to lock it.

Given that this would make the API quite verbose like:

lockBox.lock(Lock, (l) => l.lock())
lockBox.lock(RWLockWriter, (l) => l.read())

One could instead pre-program the lockbox to have the necessary utilities ahead of time and have it default.

Later DB could inherit this, or programs can combine all of these together with js-resources and js-db.

Additional context

• Related to Fine Grained Concurrency Control Standardisation Polykey#294
• Related to Upgrading @matrixai/async-init, @matrixai/async-locks, @matrixai/db, @matrixai/errors, @matrixai/workers and integrating @matrixai/resources js-encryptedfs#63
• Related to WIP: Upgrading @matrixai/async-init, @matrixai/async-locks, @matrixai/db, @matrixai/errors, @matrixai/workers, Node.js and integrating @matrixai/resources Polykey#366

Tasks

1. Integrate ideas used in EFS and PK
2. Cross-domain usage combined with withF
3. Filter duplicate locking to avoid deadlocks
4. Add in deadlock tests to demonstrate
5. Make it generic to the type of lock being used with existential types

[CMCDragonkai]

I've already written Locks class in PK in MatrixAI/Polykey#366. However it's actually lacking the unique filtering. It only has the sorting feature.

And EFS has it's own system too. So I can port this here first, and see how I can make LockBox generic.

[CMCDragonkai]

Using string has the key for any given lock is just a good base type, everything can be converted into a raw string. In the case of EFS, they are using INodeIndex which are numbers. These can just be done with toString(). We can take an interface ToString and just do the toString() conversion automatically. Users can also just provide the string version directly.

[CMCDragonkai]

The LockBox.lock method must itself return a ResourceAcquire<Array<T>>.

[CMCDragonkai]

Given our lock IDs, we have to convert them to string AND also sort and filter out duplicates:

      let ids_ = ids.map((id) =>
        ( typeof id === 'string') ? id : id.toString()
      );
      ids_.sort();
      ids_ = ids_.filter((id, i, arr) => {
        return i === 0 || id !== arr[i - 1];
      });