search

MatrixAI / js-db

Key-Value DB for TypeScript and JavaScript Applications
https://polykey.com
Apache License 2.0
5 stars 0 forks source link

Deadlock Detection #39

Closed CMCDragonkai closed 1 year ago

CMCDragonkai commented 2 years ago

Specification

With the usage of the LockBox, we should be able to do deadlock detection. Right now we have a map in each DBTransaction called locks. This records the locks that each transaction holds.

We can have a global map of pending locks, that is keys that transactions want to lock.

When a transaction tries to lock any set of keys, it checks this global map to see if any of the other transactions want a lock on any of the keys that itself owns. It can do this by iterating over all the keys it already owns. Doing this every single time we acquire any kind of lock does seem kind of inefficient. As the number of locks grow for a given transaction, the longer it takes to check the locks it already holds is currently desired by others. One way to get around this is to only trigger deadlock detection after certain time passes, because most of the time there should not be any deadlocks.

If a lock request has a timeout, then it is exempt from the pending locks. This is up for debate, basically if a lock request has a timeout, then it will eventually timeout, so technically it won't deadlock.

Additional context

Tasks

  1. Bring in the deadlock detection system from Monitor.ts in js-async-locks
  2. Integrate Monitor into DBTransaction, we can imagine that DBTransaction can extend the Monitor, or Monitor can be an encapsulated property. An encapsulated property is probably better.
  3. Better error handling, when the Monitor throws an error due to deadlock, we can provide extra information about the DBTransaction that is causing the error... it may require some level of tracking information in the pending locks, perhaps a backlink to the transaction object.
CMCDragonkai commented 1 year ago

Deadlock detection was discussed in https://github.com/MatrixAI/js-async-monitor/issues/1.

If it is solved, it could be applied to https://github.com/MatrixAI/js-async-monitor.

Or more generally to https://github.com/MatrixAI/js-async-locks.

It seems there would be a combination of js-contexts and js-async-locks to enable such a thing.

However DBTransaction would still be its own thing.

CMCDragonkai commented 1 year ago

This has been achieved in https://github.com/MatrixAI/js-async-locks/pull/26. That can be brought into here to actually make it work. The cycle detection ended up being quite easy, but it does require the DB.ts to keep track of pending map.

I'll have it first applied to js-contexts first and then we can see.

CMCDragonkai commented 1 year ago

This was applied directly into DBTransaction. I believe it should work fine. I'll release this as 5.2.0 of js-db.