matrixai / js-async-locks Goto Github PK

Specification

Locking functions that have a possibility of being deadlocked should be able to take ContextTimed contexts. Like: await lock.waitForUnlock(ctx);.

Where ctx: { timer, signal }.

This is where we can apply our context decorators like @timed and @cancellable.

This will be a major breaking API, but most users won't need to adjust, since they are not even using the timeout parameter atm.

Additional context

• MatrixAI/Polykey#438 (comment)
• Use the signalPromise utility when doing a Promise.race with the underlying async-mutex

  /**
   * Promise constructed from signal
   * This rejects when the signal is aborted
   */
  function signalPromise(signal: AbortSignal): Promise<void> {
    return new Promise<void>((_, reject) => {
      if (signal.aborted) {
        reject(signal.reason);
        return;
      }
      signal.addEventListener('abort', () => {
        reject(signal.reason);
      });
    });
  }
  

• Note that unresolve/unrejected promises are auto garbage collected once no more references are there. So as long as async-mutex doesn't have a memory leak, racing with a cancellable/abortable promise should work.
  • https://stackoverflow.com/questions/29341683/can-this-function-be-garbage-collected
  • https://stackoverflow.com/questions/54400611/dealing-with-forgotten-promises-in-javascript
• Use a symbol to know that it's due to explicit cancellation and not some other reason that the race rejected.

        try {
          await Promise.race([this.queuingLock.waitForUnlock(), abortP]);
        } catch (e) {
          if (e === abortQueuingLoopReason) {
            break;
          } else {
            throw e;
          }
        }
  

• Allow the ability to throw literals in eslint due to the usage of symbols as cancellation reason.
• Discussion about cancellable async generators and generators: from: MatrixAI/Polykey#297 (comment) to MatrixAI/Polykey#297 (comment)

Tasks

1. ...
2. ...
3. ...

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 MatrixAI/Polykey#294
• Related to MatrixAI/js-encryptedfs#63
• Related to MatrixAI/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

Specification

If we need to be able to "retry" locking due to deadlocks MatrixAI/Polykey#294 (comment).

Then we would need to integrate the withTimeout and tryAcquire decorators from async-mutex. They can be represented with parameters to our acquireRead and acquireWrite. But that would also mean we have to lambda-abstract them.

public read(timeout?: number): ResourceAcquire<RWLockWriter> {
  // by default timeout: undefined
  // but if 0, use tryAcquire
  // if above 0, use withTimeout
  return async () => {
    // same contents as this.acquireRead()
  };
}

Note that when timed out, an exception is thrown. We don't actually retry here. It is up to the user of the lock to attempt to call again, in case they need some random jitter delay.

We can keep the acquireRead method if we want to preserve the API. Or expect users to just do this.read() and this.write() with the relevant timeouts.

Additional context

• https://github.com/DirtyHairy/async-mutex#limiting-the-time-waiting-for-a-mutex-or-semaphore-to-become-available

Tasks

1. Import withTimeout and tryAcquire from async-mutex
2. Add in read and write methods that have a timeout parameter
3. Usage is now like withF([rwLock.read(1000)], async ([lock]) => ...)
4. Add timeout parameters to withRead and withWrite variants too as the second parameter after f and g for function and generator variants.