Entity Component Systems: Performance isn't the only benefit

Many companies, like Unity and Apple are using Entity Component Systems (ECS) to make games because having tightly packed data leads to cache efficiency and great performance. ECS isn’t just great for performance though: it leads to good code-decoupling, easy composition, and lends itself to TDD and automated testing.

Entity Component Systems are Easy to Compose

In the standard Object Oriented Programming (OOP) approach to writing games, you often create extremely complex and deep inheritance trees; a Player class might inherit from a SceneObject, and that SceneObject might inherit from a Transform class, and that Transform class might rely on a PlayerManager class to even be instantiated. This can be quite complex to understand and write tests for.

In ECS this is modeled by using composition. The entity (E) is the ID of an entity, components (C) are data associated with that entity, and then systems (S) operate on and modify groups of components. You then build up functionality by adding multiple components to an entity, and creating systems that look for groups of components.

Example pseudocode:

PositionComponent {
  x, y, z
}

WindComponent {
  //No data - just used as a tag
}

WindSystem {
  update() {
    world.each(position: PositionComponent, wind: WindComponent) {
      position.x++;
    }
  }
}

//Add entities to the world
playerEntity = world.addEntity(PositionComponent());
enemyEntity = world.addEntity(PositionComponent(), WindComponent());

//Add systems
world.addSystem(WindSystem());

while(true) {
  //Update all the systems each frame
  world.systems(system) {
    system.update();
  }
}

In this example code above the enemy entity will continuously move every frame while the player entity will not. This is because the WindSystem is looking for entities that have both a PositionComponent and a WindComponent. The great part about using composition is it's easy to add and remove functionality from entities.

So, if something happened that caused us to want the player to be affected by wind as well, we could simply add the WindComponent to the player entity.

Example pseudocode:

world.addComponent(playerEntity, WindComponent());

We can also make the system itself slightly more complex by removing the WindComponent if a component reaches the side of the screen.

Example pseudocode:

WindSystem {
  update() {
    world.each(position: PositionComponent, wind: WindComponent) {
      if (position.x > 100) {
        world.removeComponent(wind)
      } else {
        position.x++;
      }
    }
  }
}

These examples are slightly simplified, however even real systems tend to be small and focused because they only have one job to perform. This makes them easy to understand and reason about.

Entity Component Systems are Easy to Test

ECS also helps when it comes to automated testing. In OOP our class might have a model, animation, and all sorts of other data attached to it that we don’t necessarily want to load for every test. Whereas with composition we can just create the components and systems we are currently testing.

  • Example tests that we could write for our WindSystem include:
  • Entities with PositionComponent and WindComponent move the expected amount per update
  • Entities without the WindComponent don't move
  • Entities lose the WindComponent after x > 100

These tests are easy to write and fast to run since they don’t load or run any unnecessary logic.

Example pseudocode:

test(‘Entities without the WindComponent dont move’) {
  position = PositionComponent();
  world.addEntity(position);
  world.addSystem(WindSystem());

  startingPosition = position;
  world.update();
  expect(position == startingPosition);
}

Conclusion

ECS has a lot of benefits outside of performance that can really help create better code that is easier to reason about and modify. We’ve started using it at ClassDojo for some projects and are really enjoying it.

Does this sound like a better way to create games? Come join us in ClassDojo Engineering, we’re hiring!

    Software developers need to prioritize bugs when they are discovered, and most do this with an ordered priority scheme. Tracking tools like Jira provide a column on each ticket, and many organizations use numbers, such as P1, P2, P3, P4, and P5. Some even adopt a P0 as an indicator that there are some bugs that have an even higher priority than P1. Often there will be criteria for each of them, for example “all issues preventing users from logging in are P1.”

    These systems are good at ranking issues against each other, but don’t on their own communicate what to do with the bugs themselves. When should they get worked on? How important are they to my current work? Just like the criteria for getting assigned a priority, companies define the response to the priority: “Drop everything for a P1” vs “We won’t fix a P5.”

    At ClassDojo, we’ve found a few problems with systems like this:

    • Despite defined criteria, there’s lots of debate around the categorization: “Is this really a P3 or more of a P4?”
    • Despite defined criteria for work, there’s lots of debate around prioritization: “It’s a P1, but let’s finish the current set of work before we fix it, instead of doing it now.”
    • There’s a never-ending backlog of items that someone periodically goes through and deletes because either they’ve grown stale, or we don’t know if they are still valid, or we decide they aren't important enough to work on.

    So how did we address this problem? We came up with a bug categorization system called P-NOW, P-NEXT, P-NEVER. Here’s how it works:

    • P-NOW represents something that is urgent to fix. These are critical issues that are impacting huge numbers of users, or critical features. The whole application being down is obviously a P-NOW, but so is something like not being able to log in on Android, or a critical security vulnerability, or a data privacy problem
    • P-NEXT represents all other bugs that we agree to fix. If this is something that has a real impact on people, it’s a P-NEXT
    • P-NEVER is everything we won’t fix. We’re honest about it up front, there’s no need to pretend we’ll get to the P5s when we’re done with the P4s, because that’s not going to happen before the bug report itself is invalid.

    So with those criteria, how do we prioritize this work? It’s right in the name. P-NOW means stop everything and work on this bug. It means wake the team up in the middle of the night, get people in on the weekend, keep asking for help until someone is able to fix it.

    It also means once it is fixed we have a postmortem, and as part of the postmortem we find a way to make sure a bug or outage like this never happens again. Nobody likes being woken up for work, and it’s inhumane to keep expecting people on call to do this work. The results of this postmortem are all categorized as P-NEXT issues.

    P-NEXT issues are worked on as soon as we’re done with our current task. They go at the top of the prioritized queue, and whenever we’re done with our work, we take on the oldest P-NEXT. In this way we work through all of the bugs that we intend to fix now. This is an extension of our definition of done. The work that we released previously had a defect, so we need to fix that defect before we move on to new work.

    Lots of people will be screaming about how you’ll never get anything new done, or how non-pragmatic this is. Remember, P-NEXT doesn’t mean we fix every bug. We are just going to take the ones we don’t intend to fix and categorize them as a P-NEVER.

    When do we work on P-NEVER issues? Never! Well, not exactly. We don’t put them on a board, and we don’t track them in a backlog. We don’t want to maintain an inventory of things we don’t intend to work on. That inventory takes away from our focus on higher priorities and it requires someone to periodically look through the list.

    But, if a one-off issue starts to pop up again then we rethink our decision. This is fine, and with our P-NEXT policy of cutting to the top of the line, it results in these bugs being fixed earlier than they would have otherwise.

    But maybe people are still screaming that they’ve correctly categorized their P-NEXT issues and there are still too many to get anything done. This system is a great way to drive quality improvements in your code and process. When you prioritize all the bugs you are going to fix first, and then work to fix them, you’re working towards a zero-defect policy.

    Does this sound like a better way to prioritize? Come join us in ClassDojo Engineering, we’re hiring!

      You may have read our post from a few years ago implementing a rolling-window rate limiter, where we talked about the implementation of our sliding log rate limiter. That approach has been working well since then, but with increases in traffic, we recently found ourselves rebuilding the rate limiter to improve performance. With some relatively small changes, we were able to improve our redis CPU usage by 40x!

      Our requirements haven't really changed too much since that last post. We still want a rolling window. And we still need a distributed solution, which means we're sticking with redis. The final requirement from last time was having a minimum distance between requests; turns out, this hasn't been important for us. However, if that's something you need, do stay tuned until the end!

      The Trouble with Sets

      The challenge with our rate limiting approach (you can find the details in our previous post) was mainly caused by the expensive set operations that we were doing in redis: zrange and zadd have a time complexity of O(log(n)), which isn't bad, but zremrangebyscore is O(log(N) + M)! This operation removes M number of items from a sorted set, and in our case, we were using it to remove all request records from greater than one interval ago. So, as a user's request rate gets higher, M will get higher as well ... and instead of protecting us, the rate limiter could actually assist a single IP address in executing a successful DoS attack! As it was, our monitoring alerted us before that, but it still resulted in requests queuing up and timing out in our API and upstream in HAProxy.

      The nice thing about the sorted-set-based rate limiting is that it has very "high resolution" rate limiting: it's actually tracking request timestamps, and so we can know exactly how many requests have happened in the given time interval. This means that we can know that, say, it's been exactly one interval since your last request, and let your new request go through. However, due to these performance issues, we decided to go with an approach that optimizes performance, while accepting a lower resolution result.

      Sliding Windows

      The solution we've switched to is called a sliding window, or sliding counter, algorithm. Instead of storing a sorted set in redis with a rateId key, we're storing simple integers in redis with a rateId-interval key.

      The rateId is some way to identify or bucket the actions we're trying to limit. If it's a global rate limit, that might be the client IP address. If it's resource specific, it might be both the client IP address and the path, like 1.2.3.4:/api/widgets for example.

      In our new approach, here's what happens when a request occurs:

      1. Based on the request, we can determine two keys: 1.2.3.4:/api/widgets-T0 for the previous interval and 1.2.3.4:/api/widgets-T1 for the current interval.
      2. We GET the 1.2.3.4:/api/widgets-T0 from redis (if it does not exist, we will default to 0).
      3. We INCR the 1.2.3.4:/api/widgets-T1 from redis (if it does not exist, redis will default to 0, then increment it, and then return 1).
      4. We sum these two counts together, multiplying the previous count by a weight. For example, if we're 42% of the way through the current interval, we'll multiply the previous count by 100% - 42% = 58%, or 0.58. The result is the estimate of the number of actions taken by that user in the last interval.

      Essentially, we're using the previous and current interval counts to create a "synthetic" interval. And you can see how this is lower-resolution: we don't know the exact time of past requests, only the interval. This means that a user may have to wait up to 2 whole intervals to be able to max out in new requests.

      For example, let's say your limit is 100 requests per 1 minute. And let's say a user made 100 requests in the first 0.25 minutes of an interval, then stopped, and didn't make another request for 1 minute. At 1.25 minutes (0.25 minutes into the second interval) our previous interval count will be 100, and our current interval count will be 1 (because we just incremented it for the current request). So our "number of actions taken in the last interval" will be 1 + (0.75*100) or 76. We would only allow the user to make 24 more requests (and the current one would succeed, so 25 in total).

      If the user waited until the 1.75 minutes, the math would be 1 + (0.25*100) and we would allow 74 (plus the 1 current) requests.

      T0                              T1                              T2
      |---|---:-------:-------:-------|-------:-------:-------:-------|
          |                                   |               | 
       100 reqs                            25 reqs allowed    75 reqs allowed
      

      Of course, this low resolution can work against us as well. Let's say those initial 100 requests had come in right at the end of the first interval, say, at 0.99 minutes. At 1.25 minutes (only ~16 seconds later), we'd still allow 25 requests.

      Is that acceptable? Well, depends on your infrastructure and application. But, there is a way to tweak this.

      Tweaking the Resolution

      Notice that this produces the lowest possible resolution for a sliding window approach, because we track one counter per interval; this is why our practical interval is twice as long as we actually configure.

      We could improve the resolution here by tracking multiple counters per interval. For example, If your limit is 100 requests per 1 minute, you could track intervals of 30 seconds in redis. Then, for a given request, you'll get the current interval (n) and the previous two intervals (n-1 and n-2), and weight the n-2 count in the same way. Try this math with the first example above, and you'll see that at 1.25 minutes, we would allow 50 requests instead of just 25.

      Or, in our second example, if those 100 request came in at 0.99 minutes, we would still be blocking all requests at 1.25 minutes.

      Basically, the smaller your interval counter, the higher the resolution of your result. It'd be pretty simple to parameterize that counter size to allow custom resolutions per endpoint, client, and so on.

      What about minimum distance?

      One feature that our previous rate limiter supported—which we dropped here—is enforcing a minimum amount of time between two individual requests from the same client. Since we're no longer tracking timestamps for individual requests, we can't really support that.

      Or can we?

      Actually, it's pretty simple: just add a second limit! For example, a given endpoint might have limits of 100 requests per minute, and 2 requests per second. By configuring both of these, we can ensure a particular cadence of requests from a given client.

      Performance Wins

      The performance improvement that we've seen in our redis usage has been pretty amazing. In our staging environment tests (using jmeter), we consistently see ~1% Engine CPU Utilization with the new rate limiter, where the old one sees ~40% with the same load.

      It's not hard to see why. GET and INCR are O(1) operations in redis, and will remain fast no matter how much traffic we're seeing.

      Performance improvements almost always come with a compromise: sometimes, that's increased complexity or a reduced feature set. In this case, we were willing to sacrifice some accuracy in order to keep our response times snappy, even under load.

        Newer posts
        Older posts