Fine Grained Concurrency Control Standardisation

Specification

Locking in js-polykey has gone through alot of iterations. The most recent iteration is in js-db usage of locks where fine grained locks provided by async-mutex is used, as well as the RWLock abstraction in src/utils.ts.

For most domains such as ACL, the locks are too coarse-grained, causing one to lock the entire domain itself. Many of these locks should be replaced with the usage of DB transactions as it is done in js-encryptedfs.

In some places, fine grained locks can replace the existing coarse grained locking or even replace the usage of condition variables. Currently the src/network/Connection.ts and derived classes makes use of a _composed boolean which did double duty in terms of indicating when composition was done but as a way to prevented repeated concurrent calls of compose. The first duty is fine, but the second duty should done with a fine grained lock shared between the all the calls that should be blocked when composition operation is occurring. This means all the methods that currently check _composed and throw exceptions when it is not true.

Transactions has been introduced to js-db. With this we can replace a lot of the existing locking with the use of the new db transactions. The general changes that need to be implemented are as follows.

Updating any transact wrappers by removing them or using withF, withG locking directly.
In all cases where there is a conflict just throw it up the stack. We will expect to handle them within the handlers or look deeper into it later.
ErrorDBTransactionConflict Error should never be seen by the user. We should catch and override it with a more descriptive error for the context.
Transactions should be started within the handlers and passed all the way down to where they are needed. The idea is to make each handler attomic.
Concurrency testing should be introduced but only after SI transactions has be implemented.
All usage of DB should be updated to use the new API. This means removing sublevels and utilising LevelPath and KeyPaths instead.
All usage of db streams should be replaced with the db iterator.
All instances of db.put, db.get and db.del should be using transactions via tran.put/get/del

This applies to all domains that make use of DB OR domains that depend on others that make use of DB. The goal here is to make any even starting from the handlers atomic.

There are limitations to this however. Since a transaction can fail if there is overlapping edits between transactions. We can't really include changes to the db that will commonly or guarantee conflict. Example of this are counters or commonly updated fields. So far this has been seen in;

NotificationsManager. Makes use of a counter so any transactions that include Adding or removing a notification WILL conflict. Reads also update metadata so concurrently reading the same message WILL conflict.
More to follow?

Some cases we will need to make use of locking along with a transaction. A good example of this is in the NotificationManager where we are locking the counter update. When this is the case we need to take extra care with the locking. Unless the lock wraps the whole transaction it is still possible to conflict on the transaction. we can't compose operations that rely on this locking with larger transactions.

An example of this problem is.

start tran1
start tran2

start lock
	tran1 update counter
end lock

start lock
	tran2 update counter
end lock

end tran1
end tran2 // conflict!

To avoid this tran2 has to start after tran1 ends. 
We need to force serialisation of the transactions here.
As a result we can't compose with a transaction outside of
the lock.

This means that some operations or domains can't be composed with larger transactions. It has yet to be seen if this will cause an issue since more testing is required to confirm any problem. I suppose this means we can't mix pessimistic and optimistic transactions. So far it seems it will be a problem with the following domains.

Vaults domain - Lifecycle and editing of vaults relies heavily on locks.
NotificationsManager - Locking is needed for the counter and preventing other conflicts.

Note that this has nothing to do with IPC locking as in #290.

Additional Context

Implement True Snapshot Isolation for LevelDB js-db#4 - true snapshot isolation
https://gitlab.com/MatrixAI/Engineering/Polykey/js-polykey/-/merge_requests/213#note_740902479 - Issue involving the testing of NodeConnection and network connections and having a race condition with this._composed being true, but the properties that should only be used when composition finishes being undefined.
Enable the usage of withF and withG context for DB transactions and provide transactional iterators js-db#10 - Enabling withF and withG usage in DB

Tasks

Updating any transact wrappers by removing them or using withF, withG locking directly.
In all cases where there is a conflict just throw it up the stack. We will expect to handle them within the handlers or look deeper into it later.
ErrorDBTransactionConflict Error should never be seen by the user. We should catch and override it with a more descriptive error for the context.
Transactions should be started within the handlers and passed all the way down to where they are needed. The idea is to make each handler attomic.
Concurrency testing should be introduced but only after SI transactions has be implemented.
All usage of DB should be updated to use the new API. This means removing sublevels and utilising LevelPath and KeyPaths instead.
All usage of db streams should be replaced with the db iterator.
All instances of db.put, db.get and db.del should be using transactions via tran.put/get/del

The development of the RWLock system here https://gist.github.com/CMCDragonkai/4de5c1526fc58dac259e321db8cf5331 may be usable by a number of domains to increase their concurrency.

The RWLock system has been improved with the ability to do read-preferring or write-preferring.

The async-init has been upgraded to use locking for their start, stop, destroy methods. This makes it alot better now, they are using write-preferring rwlock.

There was some discussion about locking abstractions, the usage of a generic with since alot of domains are using a sort of transact or withTransaction method and this can be made unto a generic withF or withG utility function that also avoids the need the nest a bunch of transact callbacks.

I'm just trying to find where I wrote that.

The commentary about a general with is here: #310 (comment)

It came out of discussion about general resource management which includes locking.

Attempting to implement withF combinator. One of the problems is avoiding lots of overloaded type signatures. I originally thought I'd have to implement it similar to Promise.all. But it turns tuple types are spreadable in TS 4.0.

However I also need to map & index into the tuple type before spreading. This is a bit more complicated, had to ask a SO question about this: https://stackoverflow.com/questions/70736753/how-to-map-index-into-tuple-types-that-is-generically-spread-in-typescript

Initial attempt, however the types are not correct due to f callback still taking a spread of the resources, we need a magic TC to convert Resources to the second element of the return type of each resource.

type Resource<T = void> = () => Promise<[
  release: () => Promise<void>,
  resource: T
]>;

async function withF<
  Resources extends Array<Resource<unknown>>,
  Result
>(
  resources: Resources,
  f: (...resources: [...Resources]) => Promise<Result>
): Promise<Result> {
  const releases = [];
  const items = [];
  try {
    for (const resource of resources) {
      const [release, item] = await resource();
      releases.push(release);
      items.push(item);
    }
    return await f(...items);
  } finally {
    releases.reverse();
    for (const release of releases) {
      await release();
    }
  }
}

It appears one of the problems is that mapped types don't seem to work correctly for tuple types.

For example:

type Api = {
  createItem: (name: string) => Promise<any>;
  getItem: (id: number) => Promise<any>;
  updateItem: (item: any) => Promise<any>;
  deleteItem: (id: number) => Promise<void>;
};

// type Api = [() => number, () => string];

type NewApi = {
  [K in keyof Api]: ReturnType<Api[K]>
};

The above type checks, however if you switch to using the second Api, where it's a tuple of functions, then it doesn't type check. I thought mapped types already work fine with tuples, however this does not appear to be the case. And if it's not possible to map into a tuple type like this, then we can't really create the signature we want for withF.

Actually maybe the Resource can return a record type instead, and then we could actually map into it.

However we will need to also index into the Promise type to get rid of the promise wrapper.

Based on this answer: https://stackoverflow.com/a/60713409/582917, there appears to be a way to do this.

We will need to dispense with ReturnType, it just doesn't work. However ReturnType relies on conditional type expressions and the usage of the infer keyword, which we can use as well.

Here's an example:

type Call<R> = (...args) => R;

type FunctionReturns<T extends Record<number, Call<any>>> = {
  [K in keyof T] : T[K] extends Call<infer R> ? R: never
}

type FunctionReturns2<T extends readonly Call<any>[]> = {
  [K in keyof T] : T[K] extends Call<infer R> ? R: never
}

function getReturns<
  T extends (readonly [Call<any>] | readonly Call<any>[])
>(fs: T): FunctionReturns2<T> {
  // Escape hatch!
  return fs.map(f => f()) as any;
}

getReturns([() => 123, () => 'abc', () => [1,2] as const])

// force inference as a tuple, and not as an array
const fs = [() => 123, () => 'abc'] as const;

getReturns(fs);

The getReturns here can either return tuple type or array type depending on what the input type is. This is what the as const does, it ensures that TS infers the array as a tuple, by default TS assumes it is an array.

Notice I have 2 variants. The FunctionReturns2 constrains T to be an tuple type.

It is essential to understand that tuples are "readonly arrays". It has to be written like readonly X[] or readonly [X].

Note that the equivalent FunctionReturns that uses what ReturnType does is like this:

type ReturnType<T extends (...args: any) => any> = T extends (...args: any) => infer R ? R : any

However it's better for us to have a separate Call type just so that we can refer to it in the getReturns.

Some solutions are incoming...

type ResourceAcquire<T = void> = () => Promise<[() => Promise<void>, T?]>;

type Resources<T extends readonly ResourceAcquire<any>[]> = {
  [K in keyof T] : T[K] extends ResourceAcquire<infer R> ? R: never
}

async function withF<
  ResourceAcquires extends readonly [ResourceAcquire<unknown>] | readonly ResourceAcquire<unknown>[],
  Result
>(
  resourceAcquires: ResourceAcquires,
  f: (...resources: Resources<ResourceAcquires> & unknown[]) => Promise<Result>
): Promise<Result> {
  const releases: Array<() => Promise<void>> = [];
  const resources: Array<unknown> = [];
  try {
    for (const resourceAcquire of resourceAcquires) {
      const [release, resource] = await resourceAcquire();
      releases.push(release);
      resources.push(resource);
    }
    return await f(...resources as unknown as Resources<ResourceAcquires>);
  } finally {
    releases.reverse();
    for (const release of releases) {
      await release();
    }
  }
}

async function x() {
  let count: number = 0;
  const h: ResourceAcquire<number> = async () => {
    ++count;
    return [async () => { --count; }, count];
  };
  await withF(
    [
      h,
      async () => {
        return [async () => { }];
      }
    ],
    async (c, cs) => {
      console.log(c, cs);
      return c;
    }
  );
}

x();

One of the strange things is when we make the resource array constant. Functions that don't have readonly applied if given a readonly array will fail. If we say the parameter is readonly, we're guaranteeing that we won't modify this array. So having a strictly readonly array is technically more flexible. So a few more tweaks on the above and things should work.

Slight extension:

type ResourceAcquire<T = void> = () => Promise<readonly [() => Promise<void>, T?]>;

type Resources<T extends readonly ResourceAcquire<any>[]> = {
  [K in keyof T] : T[K] extends ResourceAcquire<infer R> ? R: never
}

async function withF<
  ResourceAcquires extends readonly [ResourceAcquire<any>] | readonly ResourceAcquire<any>[],
  Result
>(
  resourceAcquires: ResourceAcquires,
  f: (...resources: Resources<ResourceAcquires> & any[]) => Promise<Result>
): Promise<Result> {
  const releases: Array<() => Promise<void>> = [];
  const resources: Array<any> = [];
  try {
    for (const resourceAcquire of resourceAcquires) {
      const [release, resource] = await resourceAcquire();
      releases.push(release);
      resources.push(resource);
    }
    return await f(...resources as unknown as Resources<ResourceAcquires>);
  } finally {
    releases.reverse();
    for (const release of releases) {
      await release();
    }
  }
}

async function x() {
  let count: number = 0;

  await withF(
    [
      async () => {
        return [async () => { }];
      }
    ] as const,
    async (c) => {
      console.log(c);
      return c;
    }
  );

  const h: ResourceAcquire<number> = async () => {
    ++count;
    return [async () => { --count; }, count];
  };

  await withF(
    [
      h,
      async () => {
        return [async () => { } ];
      }
    ] as const,
    async (c, cs) => {
      console.log(c, cs);
      return c;
    }
  );

  const arr = [
    h
  ] as const;

  await withF(arr, async (c) => {
    console.log(c);
  });

  const y = async () => {
    return [async () => {}] as const;
  }

  const arr2 = [
    y
  ] as const;

  await withF(arr2, async (c) => {
    console.log(c);
  });

}

x();

Notice the usage of as const, that is required if there's no explicit typing of the resources as a tuple.

Changed to any instead of unknown:

type ResourceAcquire<T = void> = () => Promise<readonly [() => Promise<void>, T?]>;

type Resources<T extends readonly ResourceAcquire<any>[]> = {
  [K in keyof T] : T[K] extends ResourceAcquire<infer R> ? R: never
}

async function withF<
  ResourceAcquires extends readonly [ResourceAcquire<unknown>] | readonly ResourceAcquire<unknown>[],
  Result
>(
  resourceAcquires: ResourceAcquires,
  f: (...resources: Resources<ResourceAcquires> & any[]) => Promise<Result>
): Promise<Result> {
  const releases: Array<() => Promise<void>> = [];
  const resources: Array<unknown> = [];
  try {
    for (const resourceAcquire of resourceAcquires) {
      const [release, resource] = await resourceAcquire();
      releases.push(release);
      resources.push(resource);
    }
    return await f(...resources as unknown as Resources<ResourceAcquires>);
  } finally {
    releases.reverse();
    for (const release of releases) {
      await release();
    }
  }
}

So most of the updates to the PK codebase should be doable, but the final DBTransaction update would require refactoring the locking before transaction to be done within the transaction.

As for deadlock detection, we would consider that a programmer error when discovered, so when deadlock is discovered, an exception is thrown as normal. Users can retry of course. The PK application should not crash in this instance however.

This will be fixed when merging #366 before #326 rebases on top.

Pessimistic shouldn't be needed. Working on optimistic instead. It's alot more flexible.

Snapshot Isolation based OCC transactions should be backwards compatible with the existing usage of DBTransaction in EFS.

The main difference is the possibility of ErrorDBTransactionConflict exception, and the need to handle write-skews.

In EFS, it will continue to use locks because an OCC transaction can be converted to a PCC transaction as long as locks are used.

In EFS, it's API demands PCC behaviour, therefore it will continue to use locks, even if it updates to the new SI transactions. Thus the SI implementation will be backwards compatible. Also it's usage of locking should mean that write-skews cannot occur.

However if upgrading to the SI implementation results in EFS throwing ErrorDBTransactionConflict, then this is an indication of a concurrency bug in EFS because its usage of locks should prevent any write conflicts. Thus it should be fixed such that ErrorDBTransactionConflict cannot ever be thrown in EFS.

One happy change is the expectation that the reads will now be consistent entirely with get and iterator. This means that there's no need to ensure you create an iterator up front to get consistent reads. One can iterate on level path and perform get on other key paths without worries. This behaviour is also backwards compatible of course, since there's no place where we are expecting inconsistent reads in EFS, we have always used the multi-iterator pattern to maintain consistent reads.

The situation is different in PK, as soon as it upgrades to SI transactions, it will basically drop all usages of locking with respect to the DB. However it may preserve locking in situations where write-skew may occur. Write skew occurs when one transaction writes, and another transaction reads, and some consistency rule is broken. See:

A variety of solutions are possible: materialize the conflict, use read locks... etc.

In the long term, we may upgrade the transaction from SI to SSI (serializable snapshot isolation) which was a recent invention from 2008, and this will even prevent write-skews, and thus all DB locks can be completely dropped.

Now when a conflict occurs, we may decide to auto-retry. However this is complicated by other side-effects that may occur. Only if at least one of these is true:

Side-effects are idempotent
Side-effects are noops
Side-effects are compensated

Can you do an auto-retry.

Auto-retries should not be done when the action should be changed due a change in state. What "should" means depends on the usability of the program.

So there's an "roadmap" for the transaction development:

First introduce SI transactions which are backwards compatible
Secondly bring back opt-in key-locking into SI transactions that enable PCC transactional behaviour, this means PCC locks currently used can be dropped, but deadlock detection becomes important
Thirdly introduce SSI, so that write-skew handling code can be dropped

The second and third phases do not block our testnet deployment. They just improve our software model, reduce future bugs, and reduce entropy in our code.

@tegefaulkes

@tegefaulkes

With the new DB integration, there are 2 places where locking will be necessary to ensure serial counter updates:

notifications
- message count - this is a cardinal number, it is incremented on receive and decremented on delete
sigchain
- sequence number - this is an ordinal number, this is incremented on each new claim entered into the sigchain

To deal with these, we need to add locking before starting the transaction, and only do this as part of the public methods. If these 2 properties may be via a public method, then we should be using a RWLockWriter, if these 2 properties are only written to from public methods, then a Lock suffices.

The DB has no knowledge about these locks atm, so they occur outside the transaction as properties on the Sigchain and NotificationManager.

When acquiring locks for these transactions do it in this order:

withF([this.lock.write(), this.db.transaction()], async ([, tran]) => {
  // use tran
});

It is important to acquire the lock prior to the transaction to avoid building up resources to hold the transaction while waiting for the lock.

Note that when the DB gains the ability to lock things internal to the transaction, that is PCC control, this can be replaced with just:

withF([this.db.transaction()], async ([tran]) => {
  await tran.lock('counter');
  await tran.get('counter');
});

The API hasn't been fully worked out for PCC locking, it's possible locking can be integrated directly into get, put, and del operations. And we still have to figure out re-entrant locking and deadlock detection. So for now PK will just use locks as discussed above without expecting the DB supporting locking.

Even when PCC is used, ErrorDBTransactionConflict can still occur, that's expected if a write-set conflict occurs.

Still to do is to identify where write-skews may occur.

@tegefaulkes

Currently the iterator still doesn't support keyAsBuffer: false and valueAsBuffer: false, this is held up in the SI PR: MatrixAI/js-db#18. I may be able to extract that out and cherry pick to master to release a minor version. Until then, you have to continue using dbUtils.deserialize. @tegefaulkes

Expanded the spec with details from the PR.

The current staging of js-db MatrixAI/js-db#38 has the new DBTransaction and the usage of rocksdb. It's still got some build issues to solve before it is ready. That update will end up resulting in @matrixai/db at 5.0.0. This also brings in a new update to @matrixai/async-locks and @matrixai/logger. These changes are somewhat breaking, so it should be done together. First by applying it to EFS, and then to PK. Similar to what we did before with the DB update.

For EFS, the update should focus on dealing with:

The default consistency model is SI now, so we get ErrorDBTransactionConflict. Need to run tests to see if this occurs. The EFS must use PCC locking feature (either its own locks or using DBTransaction's own locks) to prevent any transaction conflicts from occurring. It must abstract over it.

For PK, the update should focus on dealing with:

PK now bubbles up ErrorDBTransactionConflict to the CLI, the user must then retry their work if it is conflicting with another call.
Some of those calls should then apply PCC locking using the DBTransaction lock to serialise operations
Replace all locks controlling DB transaction and counter racing issues with a combination of PCC locking on tran.lock and getForUpdate

We should also add benchmarks to identify slowness, I think the rocksdb is a bit slower in normal gets/puts, but the iterator and transaction implementation should be alot faster since it's using the native C++ without additional JS abstraction.

The PR to js-polykey should also solve #244.

Because lots of methods will now be transactional with an optional transaction, they will all need variants of something like this:

  public async pushTask(task, tran?: DBTransaction): Promise<void> {
    if (tran == null) {
      return this.db.withTransactionF(
        (tran) => this.pushTask.apply(this, [...arguments, tran])
      );
    }
    // Do the work
  }

Ideally we could abstract even the calling itself more... but arguments.callee is not available under strict mode.

Navigation Menu

Repository navigation

Fine Grained Concurrency Control Standardisation #294

Specification

Additional Context

Tasks

31 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Fine Grained Concurrency Control Standardisation #294

Description

Specification

Additional Context

Tasks

Activity

CMCDragonkai commented on Dec 28, 2021

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

CMCDragonkai commented on Jan 17, 2022

31 remaining items

CMCDragonkai commented on May 1, 2022

CMCDragonkai commented on May 1, 2022

CMCDragonkai commented on May 4, 2022

CMCDragonkai commented on May 4, 2022

CMCDragonkai commented on May 20, 2022

CMCDragonkai commented on May 20, 2022

tegefaulkes commented on May 23, 2022

CMCDragonkai commented on Jul 1, 2022

CMCDragonkai commented on Jul 31, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions