Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Integrate js-contexts and js-async-cancellable #21

Closed
CMCDragonkai opened this issue Sep 4, 2022 · 14 comments · Fixed by #26
Closed

Integrate js-contexts and js-async-cancellable #21

CMCDragonkai opened this issue Sep 4, 2022 · 14 comments · Fixed by #26
Assignees
Labels
development Standard development r&d:polykey:supporting activity Supporting core activity

Comments

@CMCDragonkai
Copy link
Member

CMCDragonkai commented Sep 4, 2022

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

Tasks

  1. ...
  2. ...
  3. ...
@CMCDragonkai CMCDragonkai added the development Standard development label Sep 4, 2022
@CMCDragonkai CMCDragonkai changed the title Integrate js-async-cancellable and return PromiseCancellable Integrate js-async-cancellable and return PromiseCancellable and take @cancellable and @timed contexts Sep 4, 2022
@CMCDragonkai
Copy link
Member Author

CMCDragonkai commented Sep 4, 2022

This will require the Timer to also be abstracted out, possibly as js-timer.

But being able to take context decorators will be difficult, as that relies on a shared weakmap. Was investigating how to do this in a way where different libraries can work. That is where async-cancellable can export @cancellable and timer can export @timed, and it is possible to share the same weakmap.

This could be done by having a "factory" function produce the timed and cancellable decorators. Users can then use the factory. Libraries can maintain their own shared weakmap. And in fact each library can have their own weakmap, they don't need to coordinate. It's only necessary for a single package when using their decorators to all use the same weakmap.

But what about the @context decorator? The factory function can produce it and it can be duplicated in each library exporting the relevant decorators. They all do the same thing. So a library can pick which one they want to use when using multiple contexts. This avoids having one central package just picking all the possible decorators. Instead it's just a general pattern that one can abide by.

That would mean both js-timer and js-async-cancellable and js-db would "implement" the same context decorator interface. But this interface doesn't have a package, it's just reimplemented everywhere.

@CMCDragonkai
Copy link
Member Author

The js-timer already exist now.

One issue is the existence of timedCancellable which combines the 2 together more efficiently. It's not really clear whether this should go into timed or async-cancellable.

Anyway, it seems that it would require a js-contexts library to maintain this together. It could be a site of future development of all sorts of AOP like tracing and what not.

However it's also possible that the decorators aren't appropriate pattern to use here.

The reason is:

  1. Lock.lock returns ResourceAcquire<Lock>
  2. Existing methods take a raw timeout number
  3. The existence of withG isn't taken into account

So basically:

  1. The ContextTimed should be able to take { timer: 100 | Timer, signal: AbortSignal }, to allow raw timeouts to occur. This does affect how it works.
  2. To maintain backwards compat, one could also just keep taking the raw timeout to convert, but it seems clunky, so it would need to change.
const pC = lock.waitForUnlock({ timer, signal })
pC.cancel();

const pC = lock.waitForUnlock({ timer: new Timer(100) })
pC.cancel();

const pC = lock.waitForUnlock({ timer: 100 })
pC.cancel();

const pC = lock.waitForUnlock(100)
pC.cancel();

The withF and withG would take context parameter first. This has the problem of withG being an async generator, and we don't know what to do with that yet. See the discussion starting here: MatrixAI/Polykey#297 (comment). It requires more R&D.

Finally ResourceAcquire would have to change, right now it says it returns a promise... but it actually gives back a function returning PromiseCancellable...

So it's fairly large change set to deal with this.

Also should we also handle raw numbers for the timer as a quick way of specifying that you want a new timer? I think these 2 are equivalent.

await f({ timer: new Timer(1000) });
await f({ timer: 100 });

@CMCDragonkai
Copy link
Member Author

@tegefaulkes the issue here is what is relevant specifies how we should deal with locking and abortion signals.

In the future, it will be easy enough to just do lock.lock(ctx), but for now you should maintain the same behaviour of racing, so that when it becomes available, it's an easy enough replacement if you are already doing promise race.

@CMCDragonkai
Copy link
Member Author

For our own usage, the easiest thing would to be have just js-contexts as a package that centralises all the context decorators, functions and also the shared weakmap.

Right now I need the js-quic package to also have a @timedCancellable decorator, so it's probably time to do this.

@CMCDragonkai
Copy link
Member Author

The repo is now available: https://github.com/MatrixAI/js-contexts.

We won't bother with putting context functions into these repos.

However this issue is still alive because the locking functions should be able to take the ctx types later.

@CMCDragonkai
Copy link
Member Author

CMCDragonkai commented Jun 4, 2023

Any development of the ctx integration here should also consider the deadlock problem and deadlock detection. MatrixAI/js-db#39

Basically deadlock detection should be developed in consideration of all these libraries:

  • js-async-locks
  • js-contexts
  • js-async-monitor
  • js-db

The js-async-monitor is an experiment in generalising js-async-init to a generic monitor. The js-async-init probably won't be built on top of js-async-monitor, since it's too specific. But more flexible representations of js-async-monitor is useful when we want to create concurrent objects in JavaScript and model concurrency control through method calls. In fact by doing this, we sort of take back control of the event loop, we can then control the sequencing of atomic operations in each method call. This is especially useful when we cannot control the who/what/where will be calling these methods (they could be called from different event handlers from different parts of the application who have no knowledge of each other).

Eventually we would have a pretty good DSL for expressing all sorts of concurrent operations.

Note that locking implies pessimistic concurrency control. Another alternative is just to try and rollback... that's what we have in DBTransaction, with snapshot isolation. But this also requires alot more machinery.

@CMCDragonkai CMCDragonkai changed the title Integrate js-async-cancellable and return PromiseCancellable and take @cancellable and @timed contexts Integrate js-contexts and js-async-cancellable Jun 4, 2023
@CMCDragonkai
Copy link
Member Author

CMCDragonkai commented Jun 4, 2023

See this comment MatrixAI/js-quic#26 (comment).

It implies that if we were to add @locked as another method decorator AND higher order function to js-contexts, then we would not even bother ever using js-async-monitor, since it would be far more flexible.

class X {
  public f(ctx?: ContextLocked): Promise<void>;
  @locked()
  public async f(@context ctx: ContextLocked): Promise<void> {
    await ctx.locks.lock('some key');
  }
}

There is some difference though. AsyncMonitor would enforce that calling the function would automatically lock. Whereas js-contexts simply adds the ContextLocked, you may choose not to even use it and nothing would lock at all.

But the js-contexts version would be more flexible, since you get re-entrancy. It's not as declarative though.

However if you added parameters to the @locked decorator... you could technically provide some default behaviour.

class X {
  public f(ctx?: ContextLocked): Promise<void>;
  @locked('some key')
  public async f(@context ctx: ContextLocked): Promise<void> {
    // Locking the same key, so it's re-entrant, it's fine
    await ctx.locks.lock('some key');
  }
}

Furthermore, we would want to just use LockBox<RWLockWriter> for the most flexibility.

One could say that @locked() by default locks nothing. But by adding a key like @locked('some-key') it does in fact automatically lock.

Furthermore since it's a lockbox, we can pass a MultiLockRequest. Thus you can do multiple keys and multiple locks.

But if we specialise to RWLockWriter, we only need the keys and locking parameters.

class X {
  public f(ctx?: ContextLocked): Promise<void>;
  @locked('some key', 1230)
  public async f(@context ctx: ContextLocked): Promise<void> {
    // Locking the same key, so it's re-entrant, it's fine
    await ctx.locks.lock('some key');
  }
}

If we do such a thing, then js-async-monitor or AsyncMonitor is unnecessary...

@CMCDragonkai
Copy link
Member Author

Of course another question is how does ContextTimed work with a ContextLocked?

Do you end up propagating anything in the ContextTimed directly into the ctx.locks.lock call? Or is it automatic?

await ctx.locks.lock('some key', ctx);

I think it makes sense to be automatically used. Thus any ContextTimed & ContextLocked would end up with timer and signal being automatically utilised in ctx.locks.lock.

@CMCDragonkai
Copy link
Member Author

CMCDragonkai commented Jun 4, 2023

Therefore ctx.locks cannot just be a LockBox, it has to be more specialised wrapper around LockBox<RWLockWriter>.

Perhaps AsyncMonitor can therefore be that object... so that ctx.locks is actually ctx.monitor.

More appropriately called ContextMonitored.

At the same time, such a thing Monitor would probably be better suited to just be inside this project. It would just be another class inside async-locks.

Basically this would mean factoring out the re-entrancy and future-possible deadlock detection into a Monitor class in js-async-locks. And then have js-contexts support ContextMonitored...

class Monitor { }
type ContextMonitored
ctx.monitor
ctx.monitor.lock('some-key')
ctx.monitor.lock(['some-key', 1200], ['another-key', 400'])

There was some limitation in signature ambiguity... but it can probably be resolved.

@CMCDragonkai
Copy link
Member Author

Anyway that means js-async-monitor is not necessary. We just create a new Monitor class here.

Also we cannot use js-contexts in this package. We have to reimplement a lower level version of supporting signals and timers directly here. This is because js-contexts depends on js-async-locks. And that would result in a circular dependency which apparently npm doesn't support.

So in this case, we just need repeat some code...

@CMCDragonkai
Copy link
Member Author

CMCDragonkai commented Jun 4, 2023

As explained here MatrixAI/js-quic#26 (comment).

It's not sufficient to just create a new lock, because there's no shared context between the locks. This then relies on the shared context that exists in this decorator system.

The problem is that there has to be a "shared" point of synchronisation between different decorators.

In the case of js-contexts, that's about sharing something between the parameter decorator @context and the method decorator @timed, @cancellable, @timedCancellable. In js-async-monitor this was facilitated through a class decorator @AsyncMonitor (same with js-async-init using @StartStop... etc).

I think the idea was to avoid needing to use a class decorator to provide that shared point... but then, maybe that's not such a bad idea. We could use a @Context class decorator to provide that.

There would then be @context and @Context, and then any usage of @monitored would be able to share a default lock.


Actually I realise that I actually solved the above problem already with the const contexts = new WeakMap<object, number>();.

I just need to expand the weak map with const contexts = new WeakMap<object, { ... }>();.

This then obviates the need to have a class decorator. Which is far more elegant.

Then a shared lock can be made possible on the target... by using the same weakmap, the first very first call using @monitor will set a special default RWLockWriter or LockBox...

This is crazy metaprogramming, but it would end up being pretty cool.

@CMCDragonkai
Copy link
Member Author

Ok it's a bit complicated than that. Going back over DBTransaction, we actually need:

  1. A shared LockBox across all the decorators of a certain class instance. If we want to go beyond 1 class instance, we would need to share the context even more... like in js-db with the DB vs DBTransaction.
  2. Then for each "context" it has to have its own map of the keys that it is locking.

Therefore we could use the const contexts = new WeakMap<object, { ... }>(); to create a shared LockBox for the target being decorated (the class).

Then for each @monitored, decorator, it has to then create a new map of the keys being locked.

In DBTransaction that is this _locks property:

  protected _locks: Map<
    string,
    {
      lock: RWLockWriter;
      type: 'read' | 'write';
      release: ResourceRelease;
    }
  > = new Map();

@CMCDragonkai
Copy link
Member Author

There was a discussion about re-entrancy.

Suppose you had:

class X {

  f(ctx?: Partial<ContextMonitored & ContextTimed>): Promise<void>;
  @monitored()
  async f(@context ctx: ContextMonitored & ContextTimed) {
    await ctx.monitor.lock('a', 'b');
    await this.g(ctx);
  }

  g(ctx?: Partial<ContextMonitored>): Promise<void>;
  @monitored()
  async g(@context ctx: ContextMonitored) {
    await ctx.monitor.lock('b', 'a');
  }

}

const x = new X();

const ctx = createCtx();

await Promise.all([
  x.f(ctx),
  x.g(ctx),
]);

Suppose the ctx created outside already had a locked. This would mean that if the lock monitor locks was just doing ctx.monitor.lock('a'), then f and g would run and interleave, there would be no mutual exclusion.

Of course the solution to recover mutual exclusion in that scenario is to add an additional key, that being of b. Therefore mutual exclusion is recovered even when f and g was called with the same context with a locked.

Note that even if we didn't lock b as well, this doesn't go against the principles of mutual exclusion. The a represents a "point of synchronisation". Therefore if a is locked, then you are already in that point of synchronisation, it is therefore up to the programmer to ensure that consistency is maintained in this scenario.

Remember locks are always "lower level" constructs compared to SI/SSI.

@CMCDragonkai
Copy link
Member Author

Released as 4.0.0. Published 4.0.0 of js-async-locks, this brings in Monitor, and the the ability to use ctx ,most things should work as normal, but there may be slight timing issues if there's code that relies on it, we will be testing integration of 4.0.0 for js-async-locks and updating to 1.1.1 for any usage js-timer.

Much more difficult than expected to get all this into the system, but now it's ready to be used by all downstream systems including js-contexts.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
development Standard development r&d:polykey:supporting activity Supporting core activity
Development

Successfully merging a pull request may close this issue.

1 participant