This story is about the technical challenges we faced and what we learned at HeatTransformers when rewriting our event-sourcing patterns to improve read performance by orders of magnitude.

Introduction

To explain what "The Real Deal" is and why it was necessary for us, we need to start by describing what event-sourcing is and how we used to implement it in our system.

What is Event-Sourcing

Event Sourcing is an architectural design pattern where changes that occur in a domain are immutably stored as events in an append-only log.
This provides a business with richer data as each change that occurs within the domain is stored as a sequence of events which can be replayed in the order they occurred.

We use TypeScript, MongoDB, and Prisma ORM on our backend. Our main entity in the system which represents the state of a deal with a client is called (surprise) Deal. Each Deal contains some events as a nested list. These are all the changes that happened to this Deal since its creation.

To get the most recent state of the Deal we accumulate all of the Deal's events and apply them one-by-one using MongoDB aggregation.

But before we dive into how Deal is structured, let's clear a few things. Deal is a view on another model called DealEventStream in Prisma schema. This Deal view is constructed using an aggregation on DealEventStream.

For example, here is DealEventStream:

{
  "_id": {
    "$oid": "678e4097ce850d2ecda12345"
  },
  "zohoDealId": "12345000012345678",
  "events": [
    {
      "_id": {
        "$oid": "678e4097635ed21a39c12345"
      },
      "type": "configure",
      "data": {
        "heatPumpInstallationType": "HYBRID",
        "gasConsumption": 10
      },
      "timestamp": {
        "$date": "2025-01-20T12:24:55.906Z"
      }
    },
    {
      "_id": {
        "$oid": "678fb322d4f72271d6712345"
      },
      "type": "configure",
      "data": {
        "gasConsumption": 123
      },
      "userId": {
        "$oid": "672a0ce8e74ed63a49812345"
      },
      "timestamp": {
        "$date": "2025-01-21T14:45:54.381Z"
      }
    }
  ]
}

And here is Deal view on this model:

{
 "_id": {
    "$oid": "678e4097ce850d2ecda12345"
  },
  "zohoDealId": "12345000012345678",
  "config": {
    "heatPumpInstallationType": "HYBRID",
    "gasConsumption": 123
  },
  "events": [...]
}

Notice how events are aggregated in the config nested object. The gasConsumption is 10 in the first event, but it is overwritten as 123 by the second event. And heatPumpInstallationType is HYBRID in config since it is the only such key between two events. There could be more events, and they would be applied the same way to construct the final view.

There are also fields outside of config, e.g. zohoDealId which is the id of the entity in our CRM. We do not event-source those fields for the performance reasons described below.

Old Aggregation

I will hide the simplified old MongoDB aggregation that we used to construct Deal view from DealEventStream documents under a spoiler, since it is not as important to the main story. But if you are curious, take a look. It is not easy to read even in this simplified form.

export const dealViewPipeline = [
  {
    $addFields: {
      configEvents: {
        $filter: {
          input: '$events',
          as: 'item',
          cond: {
            $in: ['$$item.type', ['configure-power', 'configure']],
          },
        },
      },
      zohoSync: {
        $ifNull: [
          {
            $getField: {
              field: 'data',
              input: {
                $mergeObjects: {
                  $filter: {
                    input: '$events',
                    as: 'item',
                    cond: {
                      $eq: ['$$item.type', 'sync-to-zoho'],
                    },
                  },
                },
              },
            },
          },
          {},
        ],
      },
    },
  },
  {
    $addFields: {
      updatedAt: {
        $cond: {
          if: {
            $eq: [
              {
                $size: '$events',
              },
              0,
            ],
          },
          then: '$createdAt',
          else: {
            $last: '$events.timestamp',
          },
        },
      },
      revision: {
        $size: '$events',
      },
      config: {
        $reduce: {
          input: {
            $map: {
              as: 'event',
              in: '$$event.data',
              input: '$configEvents',
            },
          },
          initialValue: initialArrayValuesInDealConfig,
          in: {
            $mergeObjects: ['$$value', '$$this'],
          },
        },
      },
      configRevision: {
        $size: '$configEvents',
      },
    },
  },
  {
    $unset: ['configEvents'],
  },
];

Slow Performance

Do you notice the downside of this approach? When we need to read the latest state of some Deal we must iterate every Deal's event, which is slow. How slow? Well, for less than 80k Deals with around 2 million events in total, the execution time was 7923 ms.

Every time we filter Deals by some field on Deal config, MongoDB needs to aggregate every DealEventStream into Deal, check that field, and then return the result. And of course, you cannot easily index aggregated fields in the config.

// Takes a lot of time
await prisma.deal.find({ where: { 'config.gasConsumption': 123 }});  

For our new upcoming projects we needed the high read performance, therefore the old aggregation did not suit us. That is our motivation for the Real Deal.

Can we do better? Yes, definitely.

New Event-Sourcing Solution

What if we store the latest state of every Deal instead of aggregating it on every read? Then reads should be blazingly fast and writes just a bit negligibly slower.

In the new version of event sourcing our Deal will be a model, not a view. We will call it NewDeal so as not to confuse it with the previous view. We also introduce a new model NewDealEvent, which will contain all the events that happened to the instances of NewDeal.

Why writes in NewDeal will be a bit slower then? Because for every update of NewDeal we will need to create a NewDealEvent document of type "UPDATE". This will rebuild some indexes on NewDealEvent but overall it is still a fast operation. The concrete benchmarks of NewDeal will be at the end of the article.  

So we have a vision of the new system, but how do we migrate 80k Deals with 2M+ events to a new system without losing any data and disrupting the work? We went forward with a shadowing approach.

Shadowing

The idea behind shadowing is that we first create NewDeal and NewDealEvent collections in production and fill them with data. Then we enable writing in them alongside DealEventStream and closely monitor any errors that occur during the shadowing period. So for any DealEventStream create or update, the corresponding create or update happens to NewDeal. This gives us a chance to find bugs in the new approach and fix them before fully moving to NewDeal.

await prisma.dealEventStream.update({
  where: {
    id: deal.id,
  },
  data: {
    partnerCampaignId: campaign.id,
  },
});

// Temporary shadowing for Real Deal
try {
  await prisma.newDeal.updateEntityAndCreateEvent({
    where: { id: deal.id },
    data: {
      partnerCampaignId: campaign.id,
    },
  });
} catch (error) {
  const sentryError = new SentryError('RealDeal shadowing error', 500, {
    category: 'technical',
    originalError: error,
    level: 'error',
    data: {
      prismaDealId: deal.id,
      partnerCampaignId: campaign.id,
    },
  });

  Sentry.withScope((scope) => {
    sentryError.enrichSentryScope(scope);
    Sentry.captureException(sentryError);
  });
}

If anything bad happens during try-catch, we will see the error in Sentry and can quickly act upon it.

We found multiple bugs in our implementation during that phase and fixed them. For example, one bug was with transactional logic on creating and updating NewDeal. More in the next sections.

The next step is to change reading from Deal to NewDeal. Important to have a backup plan to roll this change back in case there is a critical issue. At this point the migration to NewDeal is almost finished. What's left is to backup and delete old Deal data, and rename NewDeal to Deal.

Conversion of Deals into NewDeals

To proceed with the shadowing, we need to fill NewDeal and NewDealEvent with the data first. We created a special script for this that can be run at any time on any db. We did not go for the usual database migration because we want the ability to easily re-run the script.

In this script, we need to aggregate old DealEventStreams into Deals, create NewDeals from these. Then, for each Deal create NewDealEvents. The problem is there are too many deals and events to do that in one batch; such a query would fail. The solution is to split deals and events into several batches and create data batch by batch.

The following is our initial attempt at creating deals and events. This code snippet shows the processing of one batch of 5000 deals. Can you spot the problem with this?

const BATCH_SIZE = 5000;

const newDealsPromise = prisma.newDeal.createMany({
  data: newDealsToCreate,
});

const newDealEventsBatches: NewDealEvent[][] = [];
for (let i = 0; i < newDealEventsToCreate.length; i += BATCH_SIZE) {
  newDealEventsBatches.push(newDealEventsToCreate.slice(i, i + BATCH_SIZE));
}

const newDealEventsPromises = newDealEventsBatches.map(batch =>
  prisma.newDealEvent.createMany({ data: batch })
);

await Promise.all([newDealsPromise, ...newDealEventsPromises]);

The problem is, of course, the last line. Promise.all will start a lot of connections to MongoDB at the same time. Each of these connections will try to insert a lot of entities. This can easily bring down a MongoDB cluster and make it unresponsive. This is exactly what happened to us. 🙂

We have an M10 MongoDB cluster in Atlas Cloud with auto-scaling turned on. When the cluster CPU usage reaches around 90% for 20 minutes, it starts the auto-scaling process. This works well on constant loads without spikes, but in our case, we had a costly operation that created a lot of connections to the database. So the script triggered auto-scaling, which further exacerbated the situation, and the database became unavailable.

Some deal batches were actually processed in time, but we had several big batches that caused the problem. There were at most 366k events in one of these batches, splitting them in chunks of 5k would mean at most 73 promises. These 73 promises took all of the cluster's resources.

Big shoutout to the MongoDB support team. We reached out, and they quickly resolved the issue by restarting the cluster. We then proceeded to improve the script.

Here is our final attempt:

let batchIndex = 0;

while (true) {
  const deals = await prisma.deal.findMany({
    take: BATCH_SIZE,
    ...(cursor ? { cursor: { id: cursor }, skip: 1 } : {}),
    orderBy: { id: 'asc' },
  });

  if (deals.length === 0) break;

  const newDealsToCreate = deals.map((deal) => convertDealToNewDeal(deal));
  const newDealEventsToCreate = deals.flatMap((deal) =>
    convertDealToDealEvents2(deal)
  );

  cursor = deals[deals.length - 1].id;
  batchIndex += 1;

  const newDealEventsBatches: any[] = [];
  for (let i = 0; i < newDealEventsToCreate.length; i += EVENTS_BATCH_SIZE) {
    newDealEventsBatches.push(
      newDealEventsToCreate.slice(i, i + EVENTS_BATCH_SIZE)
    );
  }

  try {
    await prisma.newDeal.createMany({
      data: newDealsToCreate,
    });
    for (const newDealEventsBatch of newDealEventsBatches) {
      await prisma.newDealEvent.createMany({ data: newDealEventsBatch });
    }
  } catch (error) {
    console.error('Error creating newDeal and newDealEvent entities:', error);
    errors.push({
      batchIndex,
      failedDealIds: deals.map((deal) => deal.id),
      error: {
        message: error.message,
        stack: error.stack,
      },
    });
  }
}

This is the correct way to process batched data in MongoDB. We make a paginated call to fetch deals using a cursor. A cursor here is just an ID of the last deal in the batch. Then we split the deal events in batches and await inserting them sequentially. No multiple simultaneous DB connections this time.

We try/catch here and later store the result to JSON file to make sure we keep track of every failed batch so we can re-run the script for that batch if necessary.

Worked like a charm.

Prisma Extensions

Now that we have the data in the MongoDB, time to do some operations on it. Each NewDeal creation should also create a NewDealEvent. And updates should create events too. We need to ensure the atomicity of these operations. That is when there is an error during deal creation, no event should be created, and vice versa. To ensure this, we need to do this in a transaction.

However, transactions in Prisma are not "traditional" in that sense. If you try to use prisma.$transaction to update some documents in MongoDB, it will work. But if there is a second transaction trying to update the same rows while the first is not finished, the second transaction will fail with a write conflict error. That was the complication mentioned above that we found during the write shadowing period.

But Prisma saves the day with nested queries. Nester queries are a way of creating an associated entity in one go, along with the main entity. Perfect for our goal of creating both NewDeal and NewDealEvent.

Prisma allows you to write custom extension methods for its models, which is exactly the feature that we need. We decided to use it and write our own methods that atomically create NewDeal and NewDealEvent, update NewDeal and create an event, and so on.

Creating the Extensions with Nested Queries

export type NewDealUncheckedCreateArgs = Omit<Prisma.NewDealCreateArgs, 'data'> & {
  data: Prisma.NewDealUncheckedCreateInput;
};

export function createDealExtension(prisma: PrismaClient) {
  return {
    model: {
      newDeal: {
        /**
         * This method creates a new NewDeal entity and a corresponding NewDealEvent of type CREATE.
         */
        async createEntityAndEvent(
          args: NewDealUncheckedCreateArgs,
          options?: { userId?: string }
        ) {
          return await prisma.newDeal.create({
            ...args,
            data: {
              ...args.data,
              newDealEvents: {
                create: {
                  type: NewDealEventType.CREATE,
                  fieldChanges: args.data as InputJsonValue,
                  userId: options?.userId,
                },
              },
            },
          });
        },
        // ... other methods
      },
    },
  };
}

Notice NewDealUncheckedCreateArgs type that contains the modified data property. That is to disallow developers from using nested queries in createEntityAndEvent function calls. For example, code like this would be disallowed by the type-checker:

await prisma.newDeal.createEntityAndEvent({
  data: {
    contact: {
      type: 'HWP',
      create: {
        name: 'New contact',
        ...
      },
      ...
    },
  },
});

That is to ensure developers do not create new entities in this query. That would mess up ContactEvents structure by creating a Contact entity without ContactEvent. Instead, here it is encouraged to create Contact separately and pass its id like that:

const { id } = await prisma.contact.createEntityAndEvent(...);
await prisma.newDeal.createEntityAndEvent({
  data: {
    type: 'HWP',
    contactId: id,
    ...
  },
});

Usage of Extensions

The interface of the extensions is specifically very close to the corresponding create, update and other methods of original prisma.newDeal. So it is easy to use:

await prisma.newDeal.createEntityAndEvent({
  name: 'New Deal',
  type: 'HWP', // Stands for hybrid heatpump (warmtepomp in Dutch)
  ... other fields,
});

Performance Before and After

Now we can delete the old aggregation, Deal view, and DealEventStream collections, leaving only NewDeal and NewDealEvents collections. Of course, for cleanliness sake they will be renamed to Deal and DealEvents later.

The same query that took 8 seconds now takes 204 milliseconds on new collections (39x improvement):

// Really fast now
await prisma.newDeal.find({ where: { gasConsumption: 123 }});

Key Takeaways

Aggregating entity state on every read is slow

The better approach is to store the latest state of the entity, and reconstruct previous version from events on demand.

Be careful with Promise.all calls when doing batch operation in MongoDB

This can bring database down quite easily spamming a lot of connections.

Have a safe "shadowing" period during big architectural changes.

Do not do everything in one commit; gradually move to new architecture step-by-step. Have a backup plan to go back one step during dangerous transitions. Often validate consistency of your data while you are between steps.

I would like to share with you my settings for git in iTerm2.

You can use git status, git add ., git commit -m "", git pull, git push, git switch main, git switch master and git switch develop just by clicking one of these cuties.

Configuration is pretty straightforward, but it can take some time to figure out the first time you try it. So here is a little guide.

Open Profiles -> Open profiles -> Choose a profile -> Edit profiles -> Keys.

Then choose Add Touch Bar Item, label it git status, choose action Send text with vim special characters. Then write git status\n in the bottom field.

Repeat for every other git command you want. For git commit write git commit -m ""\u0002 in the bottom field. This will send the text git commit -m "" to the console and then send a left arrow so the cursor is inside the quotes. Then you can write the commit message and press Enter.

Then choose View -> Customize Touch Bar... and drag new commands to the touch bar.

That is all! Hope you find it useful.

In this post we are going to explore integer partitions and its Ferrer (Young) diagram properties and introduce integer partition lattice. Also we are going to explore graphical integer partitions (for which there exists a graph), their position in a lattice and threshold graphs which correspond to maximal graphical partitions. Kohnert's criterion is used to determine if a partition is graphical and in edge cases maximal (corresponding to threshold graph). The C++ library which is based on the material discussed in this post includes algorithms that find threshold graph from specified graph, maximal graphical integer partition from specified graphical partition, shortest maximizing chain and other. These algorithms use increasing edge rotation for graphs.

Integer partitions

What is integer partition? The definition is extremely simple: it is sum of numbers resulting in an integer: \( 10 = 1+3+6\)

You can also write it down as a descending sequence of numbers \( (6, 3 , 1)\). So for arbitrary integer n its integer partition is:

\[ (a_1, a_2, a_3, ..., a_k), where  n = a_1 + a_2 + a_3 + ... + a_k  and  a_1 \geq a_2 \geq a_3 \geq ... \geq a_k\]

Ferrers or Young diagram for integer partition is a sequence of columns consisting of blocks, where first column corresponds to \(a_1\), second to \(a_2\) and so on.

An ascending block movement is an operation which transforms one valid integer partition into another in a specific way:

\[ (a_1, ..., a_i + 1, ..., a_j - 1, ..., a_k), where  a_1 \geq a_2 \geq a_3 \geq ... \geq a_k  and  i < j \]

For example: \( (6, 3, 1) \rightarrow (7, 3) \)

A basic ascending block movement is that which cannot be split into two or more ascending block movements. The block movement above was not basic as it can be split in two ascending block movements: \((6, 3, 1) \rightarrow (6, 4) \rightarrow (7, 3)\). An example of a basic block movement is: \( (2, 1, 1, 1) \rightarrow (2, 2, 1) \):

Note that moving the fourth block to the third position is impossible since it would give us invalid integer partition \( (2, 1, 2, 1) \). It is invalid because \( a_2 = 1 < a_3 = 2 \). Obviously, the same way we can define descending basic block movement. I will skip definition for brevity.

Now let's define partial order on the integer partitions set. Let \( \lambda_1 \) and \( \lambda_2 \) be integer partitions for some number \( n \).

\[ \lambda_1 \leq \lambda_2 \Leftrightarrow \exists m_1, ..., m_k: m_1(\lambda_1) = a_2, m_2(a_2) = a_3, ..., m_k(a_k) = \lambda_2 \]

where \( m_1, ..., m_k \) – basic ascending block movements and \(a_2, ..., a_k \) – valid integer partitions of \( n \). This partially ordered set will also be a natural partition lattice for \(n\) which we will call \(NPL(n)\).

The green marked elements are called maximal graphical partitions, which will be described in details later. If we define an operation of adding the block in the end like this:

\[ (a_1, a_2, ..., a_k) \longrightarrow (a_1, a_2, ...,a_k, 1) \]

And extend operator \(\leq\) like this:

\[ \lambda_1 \leq \lambda_2 \Leftrightarrow \exists f_1, ..., f_k: f_1(\lambda_1) = a_2, f_2(a_2) = a_3, ..., f_k(a_k) = \lambda_2 \]

where \(\lambda_1\) and \(\lambda_2\) are integer partitions for some integers \(n\) and \(m\),  \(f_1...f_k\) each is either ascending basic block movement or block addition to the right side and \(a_2...a_k\) are valid integer partitions.

Then we get natural partition lattice for all integers (\(NPL\)):

Now let's explore some properties of Ferrer's diagrams of integer partitions:

The largest square of blocks contained in a Ferrer's diagram is called "Durfee square".

The top row of the Durfee square and above is called "head" and is denoted as \(hd(\lambda)\) of the integer partition.

The blocks to the right of the Durfee square are called "conjugate tail". This is denoted as \(tl^{\ast}(\lambda)\).

A conjugate integer partition is a partition that you get if you mirror the original partition across bottom-left to top-right diagonal. Conjugate to \(\lambda = (6, 3 , 1, 1)\) would be \(\lambda^{\ast} = (4, 2, 2, 1, 1, 1)\). And the tail of the \(\lambda = (6, 3 , 1, 1)\) then would be \((2)\). In other words \(tl(\lambda) = (2)\).

We call the partition graphical if there exists graph \(G\) such that \((v_1, v_2, ..., v_k)\) is a valid integer partition where \(v_i\) are degrees of vertices of \(G\) and \(v_1 \geq v_2 \geq ... \geq v_k\). The most interesting fact is probably the Kohnert's criterion and its consequences.

Kohnert's criterion

An even integer partition \(\lambda\) is graphical if and only if \(hd(\lambda) \leq tl(\lambda)\).

Also, \(\lambda\) is called maximal graphical partition if \(hd(\lambda) = tl(\lambda)\). Scroll up to \(NPL(10)\) and look at the highlighted partitions: they are all maximal graphical.

Threshold graphs

By definition a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:

1. Addition of a single isolated vertex to the graph.
2. Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.

Let's define simple operations on graphs called edge rotations:

A triple of vertices \(A, B, C\) in a graph \(G = <V, E>\) such that \(AB \in E\) and     \(BC \not\in E\) is called increasing (or lifting) if \(deg(A) \leq deg(C)\) and decreasing (or lowering) if \(deg(A) \geq 2 + deg(C)\).

If there is no increasing edge rotation in graph \(G\) it comes out that \(G\) is a threshold graph. If we consider integer partition corresponding to G we will find out that it is maximal graphical.

In the example above the head of the integer partition is equal to its tail therefore it is maximal graphical and corresponds to the threshold graph.

Algorithm

The question rises whether we can transform a given graph into a threshold graph using increasing edge rotations, and if we can what is the shortest sequence of such transformations.

It comes out we can always do that because increasing edge rotation always corresponds to ascending block movement and transforms given graphical partition into greater (in the lattice).

Using simple breadth first search (BFS) and increasing edge rotation we can find every shortest transformation sequence that converts our graph into a threshold graph.

You can find implementation of this algorithm and others in this C++ threshold graph and integer partition library.

References

1. On maximal graphical partitions that are the nearest to a given graphical partition (in russian language) - V. A. Baransky, T. A. Senchonok
2. On threshold graphs and implementation of graphical partitions (in russian language) - V. A. Baransky, T. A. Senchonok
3. On natural number partition lattice (2015) (in russian language) - V. A. Baransky, T. A. Senchonok, T. A. Koroleva
4. On lattice of partitions of all natural numbers (2016) (in russian language) - V. A. Baransky, T. A. Senchonok, T. A. Koroleva
5. New algorithm of generation of graphical sequences (2016) (in russian language) - V. A. Baransky, T. A. Senchonok, T. I. Nadymova
6. On maximal graphical partitions (2017) (in russian language) - V. A. Baransky, T. A. Senchonok
7. Natural numbers partitions and chromatic uniqueness of graphs (2008) (in russian language) - T. A. Koroleva
8. Graphical sequences and their generation algorithms (2016) (in russian language) - T. I. Nadymova

Wikipedia: Threshold graph, Integer partition, Lattices as partially ordered sets

I write this post to inform you that this blog is not dead :) I now have 2 side-projects which we will talk about in this blog later.

First one is my unfinished master's degree work on graphical integer partitions and threshold graphs. Here is little spoiler (natural partition lattice for number 10):

Second one is basically semi-automatic problem generator for the game of Go. It uses fuego as it's engine and tries to generate a game tree using minimax algorithm. Then you can upload this file to goproblems.com and it will work.

That's all for now folks. See you soon!

Follow telegram channel for updates: t.me/refruity_xyz

Originally I planned to write about WASI (that's why LLVM logo is in background). It is system interface for WebAssembly. Basically a means to run wasm files without browser and give them access to system stuff. But it turned out that it was kind of boring topic to write about. Just use wasmtime (which I could not compile) or wasmer (which I ran successfully with two commands) and execute wasm files if you desire so.

But today we are going to explore the paths of AssemblyScript and WebAssembly. We are going to learn how to compile TypeScript into WebAssembly and also compare performance of compiled JavaScript and WebAssembly by implementing Game of Life.  We will use Ubuntu 18.04 as our OS and webpack as our module bundler.

tl;dr here is codepen with examples:

Run the pen and you will see that WebAssembly gives around 60 FPS, whereas JS gives only 32 FPS. You can also click and drag to add extra chaos to the field.

Alright, back to the tutorial. Let's start with dependencies. You can install latest node using nvm. Then initialize new repo by adding package.json:

{
  "name": "assemblyscript-game-of-life",
  "version": "1.0.0",
  "description": "",
  "main": "src/index.js",
  "scripts": {
    "start": "webpack-dev-server",
    "build": "npm run asbuild && webpack-cli",
    "asbuild": "asc assembly/index.ts -b compiled/gameoflife.wasm --validate --optimize --importMemory --use Math=JSMath"
  },
  "license": "ISC",
  "devDependencies": {
    "assemblyscript": "github:AssemblyScript/assemblyscript",
    "copy-webpack-plugin": "^5.0.4",
    "wasm-loader": "^1.3.0",
    "webpack": "^4.38.0",
    "webpack-cli": "^3.3.6",
    "webpack-dev-server": "^3.7.2"
  },
  "dependencies": {}
}

Here we see start script which is used for developing the application, it opens webpack-dev-server on port 9000. Also we see two build scripts, first is build and it tells webpack to compile it's bundle.js, second is asbuild which tells AssemblyScript to compile ts file into wasm file. Let's stop for a minute on the second script. It has couple of arguments. Interesting ones are importMemory and use Math. Former will allow us to import memory object and use it inside and outside wasm file, latter is needed to import Math object.

Now you can run npm install to install dependencies. Create files assembly/index.ts and src/index.ts. Also create following webpack.config.js:

const path = require('path');
const CopyWebpackPlugin = require('copy-webpack-plugin');

module.exports = {
  entry: './src/index.js',
  devtool: 'source-map',
  resolve: {
    extensions: [ '.js' ]
  },
  module: {
    defaultRules: [
      {
        type: "javascript/auto",
        resolve: {}
      },
      {
        test: /\.json$/i,
        type: "json"
      }
    ],
    rules: [
      {
        test: /\.wasm$/,
        use: 'wasm-loader'
      }
    ],
  },
  output: {
    filename: 'bundle.js',
    path: path.resolve(__dirname, 'dist')
  },
  plugins: [
    new CopyWebpackPlugin([{ from: path.resolve(__dirname, 'index.html'), to: path.resolve(__dirname, 'dist') }])
  ],
  devServer: {
    contentBase: path.join(__dirname, 'dist'),
    compress: true,
    port: 9000
  }
};

defaultRules is shamelessly copy-pasted from this github issue. I have no idea how that works but that's not the point. The point is: we can now import wasm files!

But let's start simple. Create index.html:

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8">
    <title>Game of Life</title>
  </head>
  <body>
  <script type="text/javascript" src="bundle.js"></script>
  </body>
</html>

In src/index.js write:

import GameOfLife from '../compiled/gameoflife.wasm'

async function start() {
  const memory = new WebAssembly.Memory({ initial: 256 })
  const importObject = {
    env: {
      abort: () => {},
      memory
    },
    imports: { f }
  }

  const game = await GameOfLife(importObject)
  const { add } = game.instance.exports

  function f(x) {
    console.log('f', x)
  }

  console.log(add(12, 30))
}

start()

To be sure, f is a bad name for a function. But on each step of building this project it helped me so much that it grew on me and I don't want to change it now. Now for assembly/index.ts:

@external('imports', 'f')
declare function f(x: i32): void

f(1)

export function add(x: i32, y: i32): i32 {
  return x + y
}

The moment of truth: run npm run asbuild, then npm start and open localhost:9000 in your favorite (not IE) browser. Open developers tools (F12 in chrome) and look at the result.

The reason this result is important is that we were able to use core mechanics like import function f from js to wasm and run that function, export and run function add from wasm and also load wasm file using wasm-loader.

Do you like modules? I do! Let's extract index.js as a separate GameOfLifeWebAssembly.js module. Create a new file with:

import GameOfLife from '../compiled/gameoflife.wasm'

export default async () => {
  const memory = new WebAssembly.Memory({ initial: 256 })
  const importObject = {
    env: {
      abort: () => {},
      memory
    },
    imports: { f }
  }

  const game = await GameOfLife(importObject)
  const { add } = game.instance.exports

  function f(x) {
    console.log('f', x)
  }

  return { add }
}

And also introduce Main module in index.js:

import GameOfLifeWebAssembly from './GameOfLifeWebAssembly'

async function Main() {
  const game = await GameOfLifeWebAssembly()
  console.log(game.add(12, 30))
}

window.addEventListener('load', Main)

You can run the application again to make sure it produces the same output as before the refactoring. Now add a canvas to your index.html <body>:

<canvas id="canvas"></canvas>

We will need this canvas to display alive and dead cells. 1 cell = 1 pixel on the canvas. Some js code will be needed to display Uint32Array on the canvas. In your index.js:

  const width = 100
  const height = 100

  const canvas = document.getElementById('canvas')
  canvas.width  = width
  canvas.height = height

  const context = canvas.getContext('2d')
  const imageData = context.createImageData(width, height)
  const imageDataView = new Uint32Array(imageData.data.buffer)

  imageDataView[0] = 0xFF000000

  context.putImageData(imageData, 0, 0)

We create new ImageData and set first value to 0xFF000000. uint32 stands for 32 bit unsigned integer. Unsigned means that first bit does not indicate its sign, so every uint32 ranges from 0 to 2^32 - 1 = 4294967295. Each uint32 in array represents a pixel on the canvas and is in format ABGR which stands for Alpha, Blue, Green, Red. Alpha channel is the transparency of the color, where 0xFF means opaque. To sum it up we get an opaque black pixel. Open localhost:9000 and look at the black pixel in the top left of your screen.

Calling external js functions from wasm is slower than writing and reading shared memory. From js side we will need a memory view in GameOfLifeWebAssembly.js:

const memory = new WebAssembly.Memory({ initial: 256 })
const memoryView = new Uint32Array(memory.buffer)
...
return { memoryView }

From wasm side we will need functions store<u32> and load<u32> in index.ts:

@external('imports', 'width')
declare const WIDTH: i32

@external('imports', 'height')
declare const HEIGHT: i32

@external('imports', 'f')
declare function f(x: i32): void

const BLACK = 0xFF000000
const WHITE = 0

function set(x: i32, y: i32): void {
  store<u32>(toPointer(x, y), BLACK)
}

function toPointer(x: i32, y: i32): i32 {
  return (y * WIDTH + x) * 4
}

set(0, 0)
set(0, 1)

Don't forget to import width and height. Also in index.js we will need to copy data from shared memory to canvas. To do this try:

  const imageDataView = new Uint32Array(imageData.data.buffer)

  imageDataView.set(game.memoryView.slice(0, width * height))

  context.putImageData(imageData, 0, 0)

Now open localhost:9000 and look carefully. You should be able to spot 2 black pixels in the top left corner.

Now grab index.ts from my github repo, modify GameOfLifeWebAssembly.js like that:

import GameOfLife from '../compiled/gameoflife.wasm'

export default async (width, height) => {
  const memory = new WebAssembly.Memory({ initial: 256 })
  const memoryView = new Uint32Array(memory.buffer)
  const importObject = {
    env: {
      abort: () => {},
      memory
    },
    imports: { f, width, height },
    Math
  }

  const game = await GameOfLife(importObject)

  console.log(game)
  const { randomize, step } = game.instance.exports

  function f(x) {
    console.log('f', x)
  }

  return { randomize, step, memoryView }
}

To add game loop we will need requestAnimationFrame function. In index.js:

  game.randomize()

  function cycle() {
    game.step()
    imageDataView.set(game.memoryView.slice(0, width * height))
    context.putImageData(imageData, 0, 0)
    requestAnimationFrame(cycle)
  }

  cycle()

Run npm run build. Voila! You have 100x100 working Game of Life on localhost:9000.

Also to further address performance questions, I added a simple benchmark in my repo. I make game's step couple of times on randomized board and measure milliseconds it takes to complete. Results are:

JS takes twice as much time as WebAssembly to calculate. This benchmark is representative because rendering on canvas is identical for JS and WebAssembly code.

Final version with JS/WebAssembly comparison and also painting feature is available on my github.

Fun fact: before @inline-ing some functions in wasm its FPS was comparatively lower than FPS of JS code.

Important note: official AssemblyScript repository has Game of Life already implemented. Here is their source code. I learned some mechanics by reading this code. There are other tutorials that helped.

P.S. Look at this cool demo with simulation of the wave equation.

Bots provide a lot of versatility to discord. You can automate certain tasks using them. For example, imagine a server where voice channels correspond to games. Our bot will join user's voice channel when user starts playing a game and ask him if he wants to be transferred to the right channel. We will be using node version 8.10.0, Google speech recognition, ffmpeg and discord.js. You can install node 8.10.0 using nvm. Also I recommend using latest Ubuntu OS.

First things first, we want discord API token. There are some tutorials on the Internet on how to get it. Also you will need to add your discord bot user to your discord server. Then create a file named config.json and paste your API token there:

{
  "discordApiToken": "your-token-here"
}

Then create package.json file and add dependencies:

{
  "name": "myawesomebot",
  "version": "1.0.0",
  "description": "Discord bot with speech recognition",
  "main": "index.js",
  "scripts": {
    "start": "node index.js"
  },
  "dependencies": {
    "@google-cloud/speech": "^2.1.1",
    "discord.js": "https://github.com/discordjs/discord.js.git#123713305ad5a6aa1e5205a53713494009740aef",
    "node-opus": "^0.3.1"
  },
  "license": "ISC"
}

Create index.js file:

const Discord = require('discord.js')
const config = require('./config')

const discordClient = new Discord.Client()

discordClient.on('ready', () => {
  console.log(`Logged in as ${discordClient.user.tag}!`)
})

discordClient.login(config.discordApiToken)

Now we want to test if our bot is set up correctly. Run npm install and npm start and look in your console. There should be message starting with Logged in as and the bot should come online in your discord server. Congratulations! You wrote your first discord bot. But now this bot does nothing so let's add some functionality. To do this we will need to learn about async functions which will helps us reduce nesting and make our code prettier:

discordClient.on('presenceUpdate', async (oldPresence, newPresence) => {
  console.log('New Presence:', newPresence)

  const member = newPresence.member
  const presence = newPresence
  const memberVoiceChannel = member.voice.channel

  if (!presence || !presence.activity || !presence.activity.name || !memberVoiceChannel) {
    return
  }

  const connection = await memberVoiceChannel.join()

  connection.on('speaking', (user, speaking) => {
    if (speaking) {
      console.log(`I'm listening to ${user.username}`)
    } else {
      console.log(`I stopped listening to ${user.username}`)
    }
  })
})

Now try joining a voice channel and then starting a game. The bot should join you and log your presence which includes the name of the game. Also it should detect when you are speaking.

So far so good. Time for some real speech recognition. To do this we will need Google speech API credentials (read the first item in "before you begin" section). Save your credentials in google-credentials.json file in your project folder. After that you can either use dotenv or start your app with

GOOGLE_APPLICATION_CREDENTIALS="[PATH]" npm start

where [PATH] is a full path to your google-credentials.json file.

If you use dotenv then create .env file

GOOGLE_APPLICATION_CREDENTIALS="google-credentials.json"

in your project folder after installing the package and then add  

require('dotenv').config()

at the start of your index.js.

Nice. Now let's try recognizing your beautiful voice. To do this we need one more thing. Discord.js function createPCMStream creates a 16-bit signed PCM, stereo 48KHz stream, but Google speech recognition takes mono input, i.e. 1 channel. So we have to convert 2 channel stream to 1 channel stream. We achieve it by creating a transform stream:

const { Transform } = require('stream')

function convertBufferTo1Channel(buffer) {
  const convertedBuffer = Buffer.alloc(buffer.length / 2)

  for (let i = 0; i < convertedBuffer.length / 2; i++) {
    const uint16 = buffer.readUInt16LE(i * 4)
    convertedBuffer.writeUInt16LE(uint16, i * 2)
  }

  return convertedBuffer
}

class ConvertTo1ChannelStream extends Transform {
  constructor(source, options) {
    super(options)
  }

  _transform(data, encoding, next) {
    next(null, convertBufferTo1Channel(data))
  }
}

We are ready to implement voice recognition:

const googleSpeech = require('@google-cloud/speech')

const googleSpeechClient = new googleSpeech.SpeechClient()

discordClient.on('presenceUpdate', async (oldPresence, newPresence) => {
  console.log('New Presence:', newPresence)

  const member = newPresence.member
  const presence = newPresence
  const memberVoiceChannel = member.voice.channel

  if (!presence || !presence.activity || !presence.activity.name || !memberVoiceChannel) {
    return
  }

  const connection = await memberVoiceChannel.join()
  const receiver = connection.receiver

  connection.on('speaking', (user, speaking) => {
    if (!speaking) {
      return
    }

    console.log(`I'm listening to ${user.username}`)

    // this creates a 16-bit signed PCM, stereo 48KHz stream
    const audioStream = receiver.createStream(user, { mode: 'pcm' })
    const requestConfig = {
      encoding: 'LINEAR16',
      sampleRateHertz: 48000,
      languageCode: 'en-US'
    }
    const request = {
      config: requestConfig
    }
    const recognizeStream = googleSpeechClient
      .streamingRecognize(request)
      .on('error', console.error)
      .on('data', response => {
        const transcription = response.results
          .map(result => result.alternatives[0].transcript)
          .join('\n')
          .toLowerCase()
        console.log(`Transcription: ${transcription}`)
      })

    const convertTo1ChannelStream = new ConvertTo1ChannelStream()

    audioStream.pipe(convertTo1ChannelStream).pipe(recognizeStream)

    audioStream.on('end', async () => {
      console.log('audioStream end')
    })
  })
})

Start the bot, join voice channel, start any game and then say something in English. You should see transcription of your words in console. For now we will only be needing words "yes" and "no" to command our bot.

Note here: it may now seem that the bot doesn't hear you and doesn't recognize your words. In this github issue they say that discord had (or has) a bug that doesn't allow for bots to listen to you until you've played any sound. So just proceed with the tutorial, we will implement playing sounds before recognition.

The bot is silent right now, we need it to ask user a question:

async function playFile(connection, filePath) {
  return new Promise((resolve, reject) => {
    const dispatcher = connection.play(filePath)
    dispatcher.setVolume(1)
    dispatcher.on('start', () => {
      console.log('Playing')
    })
    dispatcher.on('end', () => {
      resolve()
    })
    dispatcher.on('error', (error) => {
      console.error(error)
      reject(error)
    })
  })
}
...
  const connection = await memberVoiceChannel.join()
  const receiver = connection.receiver

  await playFile(connection, 'wrongChannelEn.mp3')

  connection.on('speaking', (user, speaking) => {
...

You can download wrongChannelEn.mp3 or record your own voice line. If the audio is not playing for you then it is probably because of the missing ffmpeg binaries. You can download them here for your system. This link is for Ubuntu x64. Decompress them and put ffmpeg file in your Path, e.g. /usr/bin folder.

The last step is to create a mapping between games and channels and to tell our bot to transfer people to the right channel on "yes". To copy the voice channel ID use earlier guide. Since I'm using Ubuntu, I will use "Mines" as the game for this demonstration.

const GamesAndChannels = {
  Mines: '[VoiceChannelID]'
}

discordClient.on('presenceUpdate', async (oldMember, newMember) => {
  const memberVoiceChannel = newMember.voiceChannel
  
  if (!newMember.presence || !newMember.presence.game || !memberVoiceChannel) {
    return
  }

  const channelId = GamesAndChannels[newMember.presence.game]
  
  if (!channelId) {
    return
  }
  
  const connection = await memberVoiceChannel.join()
  const receiver = connection.createReceiver()

  await playFile(connection, 'wrongChannelEn.mp3')

  setTimeout(() => {
    memberVoiceChannel.leave()
  }, 30000)

  connection.on('speaking', (user, speaking) => {
    if (!speaking) {
      return
    }

    console.log(`I'm listening to ${user.username}`)

    // this creates a 16-bit signed PCM, stereo 48KHz stream
    const audioStream = receiver.createPCMStream(user)
    const requestConfig = {
      encoding: 'LINEAR16',
      sampleRateHertz: 48000,
      languageCode: 'en-US'
    }
    const request = {
      config: requestConfig
    }
    const recognizeStream = googleSpeechClient
      .streamingRecognize(request)
      .on('error', console.error)
      .on('data', response => {
        const transcription = response.results
          .map(result => result.alternatives[0].transcript)
          .join('\n')
          .toLowerCase()
        console.log(`Transcription: ${transcription}`)

        if (transcription === 'yes') {
          connection.channel.members.array().forEach(member => {
            if (member.user.id !== discordClient.user.id) {
              console.log(`Moving member ${member.displayName} to channel ${channelId}`)
              member.edit({ channel: channelId }).catch(console.error)
              memberVoiceChannel.leave()
            }
          })
        } else if (transcription === 'no') {
          memberVoiceChannel.leave()
        }
      })

    const convertTo1ChannelStream = new ConvertTo1ChannelStream()

    audioStream.pipe(convertTo1ChannelStream).pipe(recognizeStream)

    audioStream.on('end', async () => {
      console.log('audioStream end')
    })
  })
})

Done. Now join a wrong voice channel (not with the ID you specified earlier), fire up "Mines" and tell the bot "yes". You (and your buddies in the voice channel) should be transferred to the voice channel with the specified ID. If you tell the bot "no", it just leaves the voice channel with sadness on his metal face. Final version of the code is available via this gist.

In this tutorial I demonstrated a simplified version of EzBot, a bot we developed specifically for our discord server. It is open source and is under ISC license (use however you want). You can find it on my github. It requires MongoDB, has useful commands, internationalization (only EN/RU currently), sends new users welcome messages and also has a feature to assign people their roles using emote dashboard. This project was created in collaboration with my friend MrPhoenix.

UPDATE 26.11.2019: Because of some breaking change in Discord API stuff in the article stopped working. There is pull request that solves the problems, but we need to update to latest discord.js (master branch). I will rewrite the article when this pull request is merged. I updated the mentioned gist for now though.

UPDATE 07.01.2020 Pull request was merged. Now you can use main branch of discord.js to make it work. I rewrote the article to comply to new API introduced in the main branch of discord.js

UPDATE 04.03.2022 Discord will shut off API versions 6 and 7, so RIP discord.js v11 & v12. I will update this article or write a new one to show the new ways of discord.js.