Integrate Worker Manager into DB for parallel decryption/encryption

[CMCDragonkai]

Specification

• The WorkerManager is intended to parallelize our encryption and decryption operations
• The DB is where all the encryption and decryption is currently done
• Integrate WorkerManager into DB similar to how WorkerManager is integrated into EFS
• If this is not done, every time anything gets encrypted or decrypted, it's going to block the main loop since now everything gets put into the same DB.

Using ArrayBuffer to avoid copying between main thread and worker threads:

┌───────────────────────┐
│      Main Thread      │
│                       │
│     ┌───────────┐     │
│     │Node Buffer│     │
│     └─────┬─────┘     │          ┌────────────────────────┐
│           │           │          │                        │
│     Slice │ Copy      │          │      Worker Thread     │
│           │           │          │                        │
│  ┌────────▼────────┐  │ Transfer │  ┌──────────────────┐  │
│  │Input ArrayBuffer├──┼──────────┼──►                  │  │
│  └─────────────────┘  │          │  └─────────┬────────┘  │
│                       │          │            │           │
│                       │          │    Compute │           │
│                       │          │            │           │
│  ┌─────────────────┐  │          │  ┌─────────▼────────┐  │
│  │                 ◄──┼──────────┼──┤Output ArrayBuffer│  │
│  └─────────────────┘  │ Transfer │  └──────────────────┘  │
│                       │          │                        │
│                       │          │                        │
└───────────────────────┘          └────────────────────────┘

Additional context

• https://gitlab.com/MatrixAI/Engineering/Polykey/js-encryptedfs/-/merge_requests/46#note_627240053
• https://gitlab.com/MatrixAI/Engineering/Polykey/js-encryptedfs/-/merge_requests/46#note_628464321
• What is the correct way to ensure zero copy of an ArrayBuffer and the ability to transfer back to the main thread (without reassignment) andywer/threads.js#385
• Using the types TransferDescriptor in typescript andywer/threads.js#348
• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/SharedArrayBuffer - shared array buffers is also a possibility that potentially enable COW-like behaviour, but let's stick with what we know first

Note that it turns out we cannot do a proper buffer transfer with Node buffers. The Node .buffer is never detached. Keys always have to be copied, but it is possible to optimize in the future if we use ArrayBuffer instead of Node Buffer. This can be an optimization for the future.

Examples of EFS functions to do this:

  /**
   * Encrypt plaintext to ciphertext
   * When the WorkerManager is available, it will use it
   * However when it is not available, the encryption will use the main thread CPU
   * This is a CPU-intensive operation, not IO-intensive
   */
  protected async encrypt(plainText: Buffer): Promise<Buffer> {
    let cipherText: Buffer;
    if (this.workerManager) {
      cipherText = await this.workerManager.call(
        async w => {
          const [cipherBuf, cipherOffset, cipherLength]= await w.encryptWithKey(
            Transfer(this.key.buffer),
            this.key.byteOffset,
            this.key.byteLength,
            // @ts-ignore
            Transfer(plainText.buffer),
            plainText.byteOffset,
            plainText.byteLength
          );
          return Buffer.from(cipherBuf, cipherOffset, cipherLength);
        }
      );
    } else {
      cipherText = utils.encryptWithKey(this.key, plainText);
    }
    return cipherText;
  }

  protected encryptSync(plainText: Buffer): Buffer {
    return utils.encryptWithKey(this.key, plainText);
  }

  /**
   * Decrypt ciphertext to plaintext
   * When the WorkerManager is available, it will use it
   * However when it is not available, the decryption will use the main thread CPU
   * This is a CPU-intensive operation, not IO-intensive
   */
  protected async decrypt(cipherText: Buffer): Promise<Buffer|undefined> {
    let plainText: Buffer | undefined;
    if (this.workerManager) {
      plainText = await this.workerManager.call(
        async w => {
          const decrypted = await w.decryptWithKey(
            Transfer(this.key.buffer),
            this.key.byteOffset,
            this.key.byteLength,
            // @ts-ignore
            Transfer(cipherText.buffer),
            cipherText.byteOffset,
            cipherText.byteLength
          );
          if (decrypted != null) {
            return Buffer.from(decrypted[0], decrypted[1], decrypted[2]);
          } else {
            return;
          }
        }
      );
    } else {
      plainText = utils.decryptWithKey(this.key, cipherText);
    }
    return plainText;
  }

  protected decryptSync(cipherText: Buffer): Buffer | undefined {
    return utils.decryptWithKey(this.key, cipherText);
  }

Tasks

1. Inject WorkerManager as a dependency into DB class with setWorkerManager:

   public setWorkerManager(workerManager: WorkerManager) {
     this.workerManager = workerManager;
   }
   
   public unsetWorkerManager() {
     delete this.workerManager;
   }

2. Change serializeEncrypt and unserializeDecrypt to be asynchronous methods. There is no need to have synchronous versions, they are always used in an asynchronous way. These methods must then check if the worker manager is available, if yes, it should pass these buffers into the worker related functions.
3. Add the relevant methods in the js-encryptedfs workers. They can do the serialize and unserialize functions too.
4. To optimize this, a speical version of batch ops can be done where multiple entries are encrypted in one go. This will reduce the amount of time spent in communicating to the threads considering that we have to copy Node buffers anyway.
5. Change to using the proper buffer transfer pattern as demonstrated by EFS.
6. Change keys domain to use the buffer transfer instead of transfering by binary strings. This should be faster to copy anyway (although this needs some benchmarking).

Related to #209. The overhead of copying to the threads and back can become quite significant I reckon. And we might want to investigate ways of using ArrayBuffer where we can, or whether copying buffer plus offset and length is better than just turning them into strings and copying.

[CMCDragonkai]

Some things I realised.

The DB serialize and deserialize should be extracted out of the encryption and decryption.

This is because you are transferring data to the workers, you have to serialize and deserialize all the time, and you might as well do it in the main thread.

The serialisation and deserialisation can be made more efficient in these ways:

1. Change the encrypt and decrypt utility functions to use ArrayBuffer. This can be done with node-forge or node crypto (both should support ArrayBuffer).
2. If there is need to convert between strings (such as binary strings) to ArrayBuffer, this is doable with just TextEncoder and TextDecoder as shown in https://stackoverflow.com/questions/6965107/converting-between-strings-and-arraybuffers
3. If there is need to convert between Node Buffer and ArrayBuffer, it is necessary to slice from the Node buffer pool (because otherwise the entire array buffer would be copied).
4. The serialisation that uses JSON right now is only needed situations where the data itself is:
   1. Not a string
   2. Not a bytes of some form (Node buffer, ArrayBuffer)

One of the problems is that we won't know whether we are dealing with JSON or if we are dealing with strings or buffers. We know that at the end it is converted to bytes by leveldown. And I believe leveljs uses Node buffers, and we would preserve this to avoid another binary encoding/decoding being done by leveljs.

So therefore it up the reader/writer to know whether they should be using JSON for a given level. In other cases, the raw bytes should be used instead. This can help in the case where EFS is storing blocks of bufffers.

Once we finally start using array buffers. It's possible for us to copy the key array buffer (not transfer it), while transferring the plain text array buffer to be encrypted by the threads, and having the worker transfer us the decrypted plain text array buffer or the encrypted cipher text array buffer.

All of this should be done with a proper benchmark suite to see if we get performance improvements.

[CMCDragonkai]

Note that the underlying data is always ArrayBuffer. There are ArrayBufferView types which view the underlying data in different ways. The most flexible one is DataView. We shouldn't really need this all that much since we never change the way we are looking at the data.

[CMCDragonkai]

Changing node-forge for node-crypto is a large operation. And that might involve changing to support ED25519 keys since node-forge still doesn't have it. It will impact how this is done for mobile devices later.

[CMCDragonkai]

To achieve this. We should standardize on the usage of DB between js-polykey and EFS. The new DB is being developed in EFS and so changes to it should eventually be ported to polykey.

The worker manager integration requires more tests, requires benchmarking reports produced in the repos themselves, and to be done by our CI/CD. Remember CI/CD will only have 1 or 2 CPU cores, and should be the benchmark we work towards.

The tests/db need worker manager related tests.

We also should eliminate the excessive copying going on, but we won't be able to use Node buffers for this reason.

This is why when we are transferring data into worker, we will have to copy any data from a Node Buffer to a new ArrayBuffer, but when bringing ArrayBuffer back from the worker, we can directly do a transfer as per the upstream instructions. So going from main to worker is still a copy, but at least not a copy of the entire node buffer. But going from worker back to main is a direct pointer transfer of an ArrayBuffer.

[CMCDragonkai]

Expanding on this with regards to EFS:

This is why when we are transferring data into worker, we will have to copy any data from a Node Buffer to a new ArrayBuffer, but when bringing ArrayBuffer back from the worker, we can directly do a transfer as per the upstream instructions. So going from main to worker is still a copy, but at least not a copy of the entire node buffer. But going from worker back to main is a direct pointer transfer of an ArrayBuffer.

There are 2 major constraints:

• In EFS, the external API has to support Node Buffers in order to satisfy the FS interface.
• When using Transfer on a raw ArrayBuffer this transfers the ownership of the buffer to the separate thread and it cannot be used anywhere else in the origin thread. This behaviour is not consistent with how buffers are expected to work when passed into EFS. And it probably introduces complexities into the API if we were to expect this to be the case for DB even in PK. The ideal situation would be a sort of COW architecture for these buffers but this isn't supported yet (as far as I know when I prototyped this)

Therefore this means:

• We can only feasibly use ArrayBuffer on the returned buffer. This way the worker thread is transferring ownership of the buffer to the main thread. And this is safe.
  • In the case of EFS, this would be wrapped into a Node Buffer object with return Buffer.from(decrypted[0], decrypted[1], decrypted[2]);. EFS makes use of Node buffers extensively.
  • PK may be able get away with using ArrayBuffer directly, but this requires expansion to other types of data stored in PK including strings and JSON
• On the input buffer, we would have to "slice" and copy from the input buffer to create a new ArrayBuffer and transfer that into the worker.

PK DB requires some additional thought regarding string and JSON types, and whether that means first serialising them (the serialisation process) should turn it straight into an ArrayBuffer to avoid an intermediate Node Buffer.

So the whole architecture may look like:

┌───────────────────────┐
│      Main Thread      │
│                       │
│     ┌───────────┐     │
│     │Node Buffer│     │
│     └─────┬─────┘     │          ┌────────────────────────┐
│           │           │          │                        │
│     Slice │ Copy      │          │      Worker Thread     │
│           │           │          │                        │
│  ┌────────▼────────┐  │ Transfer │  ┌──────────────────┐  │
│  │Input ArrayBuffer├──┼──────────┼──►                  │  │
│  └─────────────────┘  │          │  └─────────┬────────┘  │
│                       │          │            │           │
│                       │          │    Compute │           │
│                       │          │            │           │
│  ┌─────────────────┐  │          │  ┌─────────▼────────┐  │
│  │                 ◄──┼──────────┼──┤Output ArrayBuffer│  │
│  └─────────────────┘  │ Transfer │  └──────────────────┘  │
│                       │          │                        │
│                       │          │                        │
└───────────────────────┘          └────────────────────────┘

[CMCDragonkai]

This is now being done in js-workers. This will then be usable by both EFS and PK.

[CMCDragonkai]

The @matrixai/workers package is now capable of doing the above. All examples have been worked out in that repository, we also have benchmarks there to address #209. However these issues are not finished until this is integrated into both EFS and PK.

So first to integrate it into EFS first, then similar benchmarking procedures can be applied there too @tegefaulkes @scottmmorris. The benches directory ported over to EFS.

Note that some changes are needed for package.json for npm run bench and npm run docs and npm run lintfix, and also changes to tsconfig.json and tsconfig.build.json to include the benches code there. As well as some changes to .npmignore. All of that should go into TypeScript-Demo-Lib as well.

[CMCDragonkai]

• I'm using ES2020 to match the outputs we expect to use in EFS and PK.
• The EFS workers/will only have efsWorker.ts and efsWorkerModule.ts, the other things are all supplied by @matrixai/workers. The efsWorker.ts is still the script we are using.
• The efsWorkerModule.ts doesn't have to inherit from anything from @matrixai/workers or even extend the upstream workerModule, those functions won't matter here.
• Because EFS should have its own crypto related functionality, there must not be any namespace conflicts if PK is expecting to inject its own crypto functions. So this requires "namespacing" so we may prefix our worker module methods with efsEncryptWithKey vs pkEncryptWithKey.
• In the future with some work on webcrypto it may be possible to share a "common" crypto implementation with a given interface React Native and Mobile OS (iOS and Android) Compatibility #155.
• The @matrixai/workers can be the location where we can extend functionality to support multithreading on mobile OSes depending on if we use NativeScript or otherwise React Native and Mobile OS (iOS and Android) Compatibility #155.

[CMCDragonkai]

In EFS, we have an opportunity to try and get the encryption and decryption utilities to operate on ArrayBuffer instead of Node Buffers. It's still using node-forge for now.

[CMCDragonkai]

The forge library currently has a couple different types in use:

• binary strings
• forgeUtil.createBuffer creates ByteBuffer from some binary string
• ByteBuffer is just an alias for ByteStringBuffer - there's a todo for it to match the DataBuffer API
• DataBuffer is an experimental ArrayBuffer backed construct - it still says it's experiment, do not use

Right now we have been using binary strings and forgeUtil.createBuffer to convert where functions require it. However this involves a bunch of copying. Especially if we return a wrapped Node Buffer which we would end slice copying into a new ArrayBuffer just to transfer it back to the main thread.

From the code, it looks like ByteBuffer could be used directly if the raw data is ArrayBuffer. Need prototype the encryptWithKey and decryptWithKey utility functions to see if we can use that, or if necessary use the DataBuffer as well.

These hacks should not be needed if we are using WebCrypto, these constructs are all forge's own creations.

[CMCDragonkai]

One problem I realised is that LevelDB doesn't seem to have any support for ArrayBuffer. There were some old discussions about support here Level/abstract-leveldown#2. But this means loading from NodeJS is still going to be a Buffer, so there will be at very least a copy occurring when doing efsDecryptWithKey cause you have to slice copy that into the ArrayBuffer being transferred over to the worker thread.

For optimal architecture, leveldb would have to be changed to support ArrayBuffer directly...

[CMCDragonkai]

Ok I've tried this now with node-forge. There's no point in trying to make the encryption/decryption use ArrayBuffer.

1. The ByteStringBuffer performs a copy/serialisation to string form internally even with ArrayBuffer. There's a TODO to make it support native buffers, but that is not available, and DataBuffer is experimental and the types don't match, and it's also not exported by the latest node forge TypeScript types.
2. This means copying is always done, so we might as well not bother.
3. The new ByteStringBuffer(string) isn't copied, the string is used without copy.

Anyway until we change over to webcrypto, the internal crypto operation does involve a bunch of copying. So we are essentially using ArrayBuffer as a serialisation/deserialisation format between main thread and worker thread, the worker is still doing work against a Node Buffer.

When webcrypto does become available here, then we can change how the crypto works to more efficient.

[CMCDragonkai]

Note that the TextEncoder and TextDecoder trick doesn't work with binary strings that node-forge uses too.

[CMCDragonkai]

1. Abstracted Workers to share Worker code for PK & EFS
2. Supports the core count setting, which speeds up tests, because you don't need to create massive worker pools
   • one test when from 1000ms to 600ms from 8 cores to 1 core
   • this reduces the need to share worker pools thus reducing the possibility of interference errors
3. Supports worker factories, where the worker scripts can be defined relative to the site-location of the worker factory definition
   • necessary to be able to share the WorkerManager code across downstream libraries
   • may have impact on bundling code such as webpack and pkg, this requires testing
4. The @matrixai/workers has demonstration code that shows how to make use of transferred ArrayBuffer to reduce copying overhead
5. Added benchmarks to @matrixai/workers that demonstrate the worker thread overhead costs, which is 1.5ms on Eurocom P7 Pro platform
   • Provides baseline to know what is worth parallelising
6. Integrated @matrixai/workers into EFS DB
   • Could not entirely make use of zero-copy due to crypto library node-forge still making use of binary strings internally
   • Could be optimised further when changing over to webcrypto and sharing crypto utility between EFS and PK
7. Removed unnecessary maybeCallback in EFS DB, this is an artifact from before, the maybeCallback should only be used on EncryptedFS
8. Added tests into EFS DB to test the integration of WorkerManager
9. The EFSWorkerModule and PKWorkerModule will need to have namespaced methods to avoid conflicts
10. Added benchmarks harness to EFS to start benchmarking reports for EFS
11. Pending integration of @matrixai/workers to PK, and the optimisation of the core count
12. Pending integration of benchmarking harness into PK
13. Pending optimisation of batch, where multiple multithreaded calls can be made in parallel rather than waiting for one encryption/decryption call at a time
14. The single usage of WorkerManager in DB isn't that much faster, mainly because of the extra overhead in copying data to the worker threads. In fact for basic get/put/del set of operations, it may become 400ms vs 20 ms. The performance benefit would only come when many operations are being done at the same time. So batch optimisation should be used too, and larger block sizes. This is something we can test with more benchmarking.

[CMCDragonkai]

@tegefaulkes note that with new js-workers, the cores should be set 1 in PK testing.

[CMCDragonkai]

I might move DB out to @matrixai/db so that both can use the same DB. But some features aren't yet used by PK like the transactions.

[CMCDragonkai]

Doing it here. https://github.com/MatrixAI/js-db Once this is done... all pieces should be ready to integrate into EFS and also PK. The new transaction features are available for PK to use as well. The new DB allows direct entry of buffers as the key, this should speed up any usage of lexicographic-integer as keys instead of having to serialise them as strings. Further as it supports the raw parameter used in EFS, where PK is using it to store raw buffers, it should avoid having to do a JSON serialisation. Benchmarks for DB would be moved into js-db out of EFS then.

[CMCDragonkai]

The js-db would have to take a "crypto" interface, and expect EFS and PK to supply those functions as perhaps callbacks. An encryption and decryption function. Right now it would have to work with Node Buffer, but later perhaps support the ArrayBuffer instead.

[CMCDragonkai]

One problem with abstracting the encryption/decryption, is that we now have this sort of interface:

type Crypto = {
  encrypt(key: ArrayBuffer, plainText: ArrayBuffer): ArrayBuffer;
  decrypt(key: ArrayBuffer, cipherText: ArrayBuffer): ArrayBuffer | undefined;
};

I chose ArrayBuffer in order to future proof it for webcrypto and to enable it for Transfer that is used in threadsjs.

This new type works for both WorkerManager and for submitting as a crypto utility object.

However I realised that webcrypto always makes this asynchronous... so the actual utility function will be async:

type Crypto = {
  encrypt(key: ArrayBuffer, plainText: ArrayBuffer): Promise<ArrayBuffer>;
  decrypt(key: ArrayBuffer, cipherText: ArrayBuffer): Promise<ArrayBuffer | undefined>;
};

This can also be implemented in threadsjs as well since it supports asynchronous methods.

Then the expectation is for the constructor of DB to pass this crypto utility belt, and to optionally & dynamically inject WorkerManager with this relevant type. And this enables the ability to share the same crypto routine instance.

[CMCDragonkai]

It is easy to wrap sync code as async code. You just wrap it in Promise.resolve() but not easy to wrap async code as sync code... it requires a sleep and worker thread which is way too much infrastructure in Nodejs.

[CMCDragonkai]

Something very important:

• All Node Buffer are ArrayBuffer
• ArrayBuffer are not Buffer

So you can pass a Node Buffer wherever that expects an ArrayBuffer.

But to make an ArrayBuffer a Buffer it's easy by Buffer.from(ab).

[CMCDragonkai]

The @matrixai/db won't be depending on any crypto functionality. The expectation is that EFS and PK would be supplying these utilities.

In doing so, the crypto functionality is now optional for DB. If it is not passed in, the data won't be encrypted.

However because we want to do some tests of this form, I'm going to be adding example workers and example crypto into the tests code supported by node-forge for now.

[CMCDragonkai]

The @matrixai/db is now released: https://www.npmjs.com/package/@matrixai/db

[CMCDragonkai]

Now integrating it into EFS.

[CMCDragonkai]

This is done in EFS. And with MatrixAI/js-encryptedfs#47 closed and this being done in https://gitlab.com/MatrixAI/Engineering/Polykey/js-polykey/-/merge_requests/205. Then this issue should be closed for now. As there's nothing further to do here.