Here at Opendoor we have a microservice architecture. That is, our product is provided by multiple services running on the backend. Generally this works well, but it also introduces some challenges. For example, it makes it challenging to run integration tests, or go through customer flows during development.

It’s a problem that many tech companies face: How do you make it easy to test changes as the company and software architecture grows in complexity? Some companies will hire a QA team. This is an excellent way to prevent issues from reaching customers, but QA engineers need an environment in which to test. The company may adopt a release train so QA can test a large batch of changes before releasing them. There’s a downside though, as this can slow development. If an engineer misses the release window, they have to wait for the next one. At other companies engineers can release independently and test in a shared staging environment, but this can lead to conflicts, things breaking, and also slow velocity. There are many ways to approach the problem, and various levels of investment that can be made to solve it. But every company with a growing software system will have to address it at some point.

At Opendoor, we set out to make it easy for engineers to test complicated changes independently, and early in the development lifecycle, which ultimately increases velocity. We’ve further enabled testing by our cross-functional partners like product management or design. Reducing the burden of testing allows our engineers to focus more on creating quality products for our customers. Continue reading to learn how we implemented QA environments to enable this and more.

The Problem

Testing in a microservices world can be challenging. We’re big proponents of the testing pyramid, so we use unit tests as much as possible. However, some changes are hard to test with unit tests alone. For example: when making changes across multiple services, when making major changes (like a recent major upgrade of our Rails version), or when making changes to a service configuration. There are going to be times when you just want more confidence than unit tests alone give you.

We ran into some obstacles when it came to testing these kinds of changes:

• Some tests require multiple services running. It can be hard to know how to run all these services, and it can turn a developer’s laptop into a space heater!
• In order to test, you need realistic data. While we have realistic data in our staging environment, tests can potentially mutate that data and “corrupt” it for other tests — meaning someone ran a test that left some data in an unexpected or broken state.
• Production environments differ from local testing in networking, configuration, user data, etc.
• Those outside of the development team like QA teams, designers, or product managers found it basically impossible to test backend changes before we actually merge them.

So, we created QA environments to solve these problems.

QA Environments

QA environments are essentially mini, isolated versions of staging. But instead of running every service in each QA environment, you can run just the services you need. And instead of there only being one environment, as with staging, you can have as many QA environments as you like, on demand. Each can have a different version of each service, and each service in them can have its own independent database.

More concretely, a QA environment is a collection of pods, services, ingresses, and other resources in Kubernetes, that collectively work together to create a group of services that can communicate with each other. We’ll go into more detail on this later.

From a developer’s point of view, whenever they create a pull request (PR), they can also create a QA environment associated with it to test their changes in an environment similar to production. They specify what services they want to deploy in the environment along with the PR for the changes they want (or even multiple PRs, since not all services are in the same git repository).

The QA Concierge (QAC 🦆)

Creating a QA environment has several steps, and we want to automate this. Hence, we created an internal service called QAC (pronounced “quack”) to facilitate it. QAC has a UI, and also an API that can be called from continuous integration (CI). Hence, users can go into the UI to create an environment for themselves, or CI can create an environment automatically to run tests.

QAC also plays a part in request routing, which we’ll talk about later when we get to another supporting service, QARP. We’ll describe how QAC works in detail in a bit. But first, we need some background about our tech stack.

Tech Stack

Here’s our tech stack at a high level, as far as it’s relevant to this article.

We deploy our services with Kubernetes using Helm. We build Docker images in CI for each service. We have a staging environment that we deploy to once code has been merged into the main branch. We run some automated integration tests in staging before deploying to production.

Generally, all external dependencies for a service are configured via environment variables, roughly following Twelve-Factor principles: For example, each service with a database stores the URL in an environment variable, usually called DB_URL. Similarly, if service A calls service B, then service A will have the hostname of service B’s load balancer in an environment variable, usually called SERVICE_B_HOST. Storing configuration in environment variables is awesome because it makes it easy to deploy the service in different environments without updating the code or Docker image. This will be crucial later. Environment variables are configured as part of the Helm chart, and each environment (production, staging, and QA) will be able to set these separately.

Some of our services use Kafka. Some use Redis for background jobs (e.g., Sidekiq in Rails, or Celery in Python). These are also configured via environment variables.

We have realistic data in our staging databases. We run a weekly ETL that copies data from production to staging, and scrubs email addresses and other sensitive data. This is important because it allows realistic testing data in staging. Unfortunately, it introduces the possibility of temporarily corrupting staging data as well.

For frontend code, we build frontend assets (minified JS and CSS) and upload them to a content delivery network (CDN). Requests from the frontends get routed to an AWS load balancer via DNS. These then get routed to the correct internal service via NGINX ingresses we have running in Kubernetes. The routing at the NGINX level is generally based on the URL path or subdomain. In practice, most frontend requests end up going to our GraphQL service, which runs in Kubernetes like everything else. The GraphQL service then routes to other backend services. Here’s a diagram to make it more clear.

This is our tech stack in a nutshell. Now let’s dive into the details of how we implemented QA environments!

How QA Environments Work

Let’s list out all the steps involved in the lifecycle of a QA environment. We can then go into them more in detail.

User Actions

1. First, a developer makes one or more PRs for some changes.
2. If the developer wants a QA environment to test their changes, they go into the QAC UI. There, they can create an environment and tell QAC what services to deploy.
3. For each service the developer wants to deploy, they provide a link to the PR with any changes, or they can say to deploy the service off the main branch instead.

QA Deployment

1. Once the user has specified the services, if the user requested independent databases for any of them, QAC will start the process to provision them. If the user didn’t request independent databases, then the default is for the services in QA to connect to the staging database.
2. Once databases are provisioned (if requested), QAC will load the Helm charts for each service. It has a simple plugin model for finding and loading Helm charts, to make it easy to support different types of services (e.g., all services written in Go are handled with the same plugin, as they all follow the same conventions).
3. Since all our services are configured via environment vars, QAC will update the environment vars in the Kubernetes resources (rendered from the Helm chart) as needed to run the service in QA.
4. QAC also does some other processing, like adding labels to all Kubernetes resources to indicate which environment they’re in (each QA environment has a numeric ID). It also adds node selectors and tolerations so QA services run on dedicated Kubernetes nodes (we don’t want them competing for production resources).
5. If the user requested independent databases, QAC also inserts the new URLs for them into the environment. It also runs any migrations for the service. How to run migrations differs by service, which QAC again solves via a plugin model. We’ll discuss that more below. Each migration ultimately results in a Kubernetes Job that gets applied and waited upon.
6. Once the Kubernetes resources are ready, QAC simply applies them in Kubernetes.

Running in QA

1. Now that the QA services are running in Kubernetes, we need to get requests to them. This is done by setting two cookies in the user’s session. One is used for canary routing (described below), and the other includes the numeric environment ID. The QAC UI has a button that will generate and set these cookies when clicked. This makes it easy for anyone, not just the developer, to “enter” a QA environment at the click of a button.
2. For each of our services running in staging, we’ve set up an NGINX canary ingress. The canary ingresses are deployed alongside the normal ingress for each service. They’re identical to the normal ingress, except they include an annotation with a cookie name. This causes NGINX to check if that cookie exists, and if so, route to a different backend. Otherwise it will route to the normal ingress backend (which would be the staging service).
3. When the cookie is set, the canary ingress routes it to a custom reverse proxy we built, called QARP (QA Reverse Proxy). This is a Caddy server with a custom reverse proxy module, making the code we need to maintain pretty minimal.
4. When QARP gets a request, it will extract the QA environment ID from the cookie. Additionally it extracts the backend service name from a header that gets added by the service’s ingress. It then calls QAC’s API to check if the given backend service is running in the QA environment matching the ID. If so, QARP will forward the request to the QA service by changing the host to the local cluster address. If not, it forwards the request on as-is to staging. This setup allows us to route to either staging or a particular QA environment based solely on some cookies developers can easily set.

That’s a lot to take in, so here’s a simplified diagram to show the above flow:

Now that we’ve listed out the steps at a high level, let’s go into more detail about some of them.

The QAC UI

To make it easy for developers to create QA environments, we made a UI. The home screen lists out all the active environments, with the name of who created them.

Clicking on an environment will take you to the details page, which we’ll describe next. You’ll also note an auto-cleanup time for each environment. To avoid wasting resources, each environment will automatically delete a week after creation. There’s a button on the details page to extend the auto-deletion if you need it for longer. The last thing you can do on the homepage is to create a new environment. It will ask you for a name, and then take you to the details page for it.

Here’s what the details page for an environment looks like.

On the details page, you can see which services are deployed in the environment (initially none), or select which services you’d like to deploy. We have a dropdown for which services are available, which makes the UI easier to use. You select the service, and then enter the PR URL for the changes you want to apply. Technically we support deploying off a branch or with a given Docker image, but these are mostly used for debugging by core developers. The one exception is deploying a service on the main branch. This is useful if you haven’t made any changes to the service, but need it in your environment. Lastly, you can also check a box to get an independent database.

Once you select all your services, there’s a button to deploy them. At this point you sit back and relax while they deploy. Once they’ve deployed, the UI will show a list of pods with their respective Kubernetes status (e.g., “Ready”), and links to Splunk logs for the pod.

You can also set cookies to “enter” your environment as described above, as well as delete the environment altogether once you’re done using it.

Note that although QAC has a UI, it also has a well-defined API. This is important because we designed it to be used by both developers and CI. CI will use the API to automate running integration tests in QA environments. This avoids race conditions and data pollution that you can get by running pre-merge integration tests in staging.

Provisioning Databases

The user can request an independent database for their service running in QA. This enables testing migrations, or running tests that mutate data without corrupting staging. Tests in CI especially benefit from this to avoid race conditions and flakiness from mutating the same objects.

To create these independent databases we use Aurora. Because we use Amazon RDS for all our databases, Aurora makes it easy to create relatively fast clones of them. We run a job every weekend that makes snapshots of our production databases, and then runs transformations to scrub sensitive data like emails. We then take a second snapshot of this and create an Aurora cluster and database instance from it. At the same time we also delete any old clusters. This is all very slow, so needs to be done offline, prior to when a developer directs QAC to create a database clone. When QAC needs an independent database, it finds the cluster for a given service, and “restores” the cluster, which creates a new one, and creates a database instance from it. This is “relatively” fast — taking about 10 minutes — though we hope to make it faster in the future (see Alternative Designs at the end of this article).

N.B. Aurora databases might count towards RDS quotas in your account, so be careful with this approach.

Rendering Helm Charts

All our services define their Kubernetes resources via Helm. These resources define what gets deployed, along with load balancers, etc. QAC needs to modify these resources in order to inject independent database URLs, other service hostnames, labels, etc. The Helm charts are a template for Kubernetes resources, and the template parameters are different for each environment (e.g., QA, staging, production).

For staging and production, we deploy via CI. That is, CI will call Helm to deploy the service. For QA, QAC will do this (although there’s an alternative we considered that I’ll describe below). QAC doesn’t use Helm to deploy directly because it needs to modify the resources before deploying. Hence it runs helm template to generate the templated YAML resources, which it can parse and patch.

Generating the resources differs slightly depending on the service. Most of our services are written in either Go, Python or JavaScript (node), with one major service being written in Ruby. Each of these is slightly different to deploy, so QAC has a plugin system. It will detect the type of service being deployed, and has handlers for each to generate the resources. This is easy to extend for any future additional cases (we’re using the generic procedure pattern from the excellent book Software Design for Flexibility). The handler basically returns two things: 1) the Kubernetes resources for deployment, and 2) the Kubernetes resources for running database migrations. The latter is typically a Kubernetes Job that runs the command to run migrations.

Patching Kubernetes Resources

Once QAC has generated the Kubernetes resources from the Helm chart, it needs to make some modifications.

First, QAC makes sure every resource has a unique name in Kubernetes, so there are no conflicts. Then it adds a qa_env label to every resource, where the value is the numeric environment ID. This makes it easy to search for all the resources belonging to an environment. E.g., deleting an environment is mostly just running kubectl delete -l qa_env=N for each resource type.

QAC then adds nodeSelector and tolerations to the deployment specs. This is so pods run on nodes dedicated to QA. This is an implementation detail that depends on how the Kubernetes cluster is set up. But in general, QA services should run on dedicated nodes, and not compete for resources with staging or production.

Finally, QAC performs the most complicated modifications: patching environment variables. We do this via variables in the Helm chart that QAC interpolates. I’ll describe the two most important ones.

First is ${qa_db:STAGING_DB}. QAC will parse the values of all environment variables and look for this string (generally it looks for anything of the form ${qa_XYZ:STRING}). In this variable, STAGING_DB is the URL of the staging database. It’s used as the default if the user has not requested an independent database for this service. In that case the variable will simply resolve to this substring. If the user has requested an independent database, however, then QAC will replace this variable with the URL to the newly provisioned database.

The other is ${qa_service:STAGING_HOST}. For example, you might have ${qa_service:user-service}. The value depends on whether the service (in the example, user-service), is running in the current QA environment or not. If it is, then the variable will be replaced with the hostname of the Kubernetes Service for the QA service. If not, then the variable will be replaced with the staging hostname. QAC can determine whether or not the given service is running in the current QA environment by looking at all the Kubernetes Service resources in that environment to see if the name exists.

Finally, QAC also processes Kubernetes Ingresses. It performs variable substitution in ingress hostnames, similarly to patching environments. The main variable that’s used in this case is ${qa_id}, which resolves to the numeric environment ID. This allows hostnames to be unique per environment. Actually, they must be, otherwise a QA environment would try to use the same hostname as another, or even worse, a staging or production hostname. In fact, to avoid these dangerous collisions, QAC will remove any Ingress resources in which the hostname doesn’t include the string qa-N (N here being the environment ID).

Applying Migrations and Deployment

Once the Kubernetes resources have been patched, they can be applied. Each service actually has two sets of Kubernetes resources: one for running database migrations, and one for deploying the service. QAC applies the migrations only if the user requested an independent database. We want to be sure that QAC never accidentally runs migrations against the staging database, as that could break it for other developers. To prevent this QAC ensures that the ${qa_db} variable was used somewhere in the Kubernetes resources (both migration and deployment). This prevents errors where someone didn’t set up their Helm chart for QA correctly, and hard-coded the staging DB instead of the QA variable.

The migrations are applied first, and QAC will wait for them to finish (the migrations must be a Kubernetes Job that can be waited for). Then it applies the deployment resources. If all goes well, then the QA environment is successfully deployed!

Routing Requests to QA Environments with QARP 🐟

To “enter” a QA environment, the user sets two cookies (the QAC UI provides a button to make this easy):

• qa=always
• qa_env=<env_id> (this is actually a JWT to provide security against non-Opendoor employees setting these cookies)

The request gets sent to an AWS load balancer (via a CNAME record), which sends it into our Kubernetes cluster. There, an NGINX controller will pick it up based on Ingresses we set up. Each Ingress has a matching canary ingress, which is defined by the following two annotations:

nginx.ingress.kubernetes.io/canary: "true"
nginx.ingress.kubernetes.io/canary-by-cookie: "qa"

The way this works is that we have a normal ingress rule that routes to a backend service, and also a corresponding canary ingress. For example, we have a normal ingress that matches

host: athena.opendoor.com
path: /

and sends the request to our GraphQL server. We also have a canary ingress, which is identical, except that it has the above two annotations, and sends the request to a special backend service called QARP.

The normal ingress also sets a header with the name of the normal backend service to which it would send the request. This also applies when the request is routed to QARP.

These two ingresses are easy to keep in sync because they’re part of our standard Helm template.

These canary ingresses ensure that any requests with a qa=always header are routed to our QA Reverse Proxy (or QARP, pronounced “carp”). QARP is a Caddy instance with a custom module. Caddy allows custom code to run dynamically on each request as a “matcher”. It will route the request to one of two destinations depending on whether the request matches what the module is looking for. The module calls QAC with the QA environment ID (which QARP gets from the qa_env cookie), and the backend service name (which the ingress set in a header). QAC can quickly look up whether that backend is running in the given environment, and return a boolean response. QARP can then route the request to the QA backend if it exists or on to staging if not. The QA backends have predictable names (basically service-name-qa-N), so QARP can easily construct them.

Note that requests for purely frontend assets (JS and CSS) don’t go through Kubernetes. We store these in S3. We also have a way to use PR-specific frontend assets that pair with, but are a different implementation from, QA environments. These are called deploy previews and you can read the deep dive about them in another blog post.

Keeping Environments Up-To-Date

Deploying some services when a QA environment is created is all well and good, but we need to keep it up to date. Since each service in the environment is associated with a PR (or the main branch), keeping them up to date means redeploying when new commits are pushed to those PRs (or main branch). I mentioned above that services could also run off an arbitrary branch, but this is mostly for debugging purposes, and automatically redeploying these services is not supported.

We leverage our existing CI system for this. As commits are pushed, the CI jobs run. We simply need to add a CI job to call QAC to tell it to redeploy.

Cleaning Up Environments

We noticed that developers often forget to delete their environments, which ends up wasting resources. Hence we have two ways to help with this. First, when all the PRs associated with an environment are closed (merged or otherwise), the environment is deleted. Second, we delete environments automatically after one week, regardless of whether the associated PRs were closed. This second approach is because developers sometimes make PRs just for testing, and forget to close them. However, we realize sometimes developers do need environments longer than one week, so we also allow developers to postpone the auto-deletion time, or opt out entirely.

Deleting environments that are over a week old is pretty straightforward. We have a job that runs on a timer (hourly), and looks for open environments that are past their auto-delete time. Deleting environments when all PRs close is a little tougher, since we don’t have CI jobs that run in this case. To deal with that we set up a GitHub webhook so we can get notifications whenever PRs are closed.

Alternative Designs

Independent Databases

There’s an alternative to using Aurora to clone databases that we considered. The idea is to run Postgres on an EC2 instance with a btrfs or ZFS filesystem. The idea here is that you can copy data from an RDS database to a Postgres server on EC2 using Amazon DMS. Then turn that server off, we only need the data files on disk. When we want a new independent database, we can use the copy-on-write (CoW) feature of btrfs or ZFS to make a copy of the database files, and start a new instance of Postgres, on a new port, using this copied data. Because this is CoW, it’s extremely fast and storage efficient. Even for a ~10TB database, it only takes a few milliseconds. And the amount of inserts and updates we do for testing typically only takes an additional few kilobytes.

We did a proof of concept of this, and it appears to work perfectly. However, the team decided that using Aurora was probably a better thing to start with because it’s an off-the-shelf solution and more engineers on the team were comfortable with it. Either will work, but if we were doing this again we would go with the CoW implementation. We had to completely refactor QAC to support creating Aurora instances, because it takes long enough that everything needs to be done in a background task. Plus adding 10 minutes to environment spin up is quite significant. Later we discovered postgres.ai, which basically does exactly what’s described above, so that would be worth investigating as well.

Deploying

QAC deploys environments by rendering Helm charts, making changes, and applying the resulting Kubernetes resources. There’s a bit of overlap with our CI/CD system here, which also renders Helm charts and applies them. Hence, another approach we thought about was to let CI/CD do all the Helm / deployment logic, and then set up a Kubernetes mutating webhook to change the resources just before they get applied.

This is elegant in theory, because QAC doesn’t need to know how to render Helm charts. However, QAC still needs to know what other services are running in the same QA environment as the one being deployed (it needs to know this to resolve ${qa_service} variables). The way it knows this is by rendering the Helm charts and looking at Service resources. Hence, it would need to render Helm charts anyway. The team was also less familiar with Kubernetes webhooks, so we abandoned this idea. It might be a better way to do it if QAC had some other way to know which services were in an environment (e.g., if all services were named in a particular consistent pattern so QAC could infer it).

Learning Experiences

We learned a few interesting things by working on this project:

• Standardization is leverage. The more consistent your infrastructure is, the higher leverage you get by writing tooling for it. Luckily, almost all our services use Helm and are deployed to Kubernetes. If some services used a different tool, and some were deployed to, say, bare metal EC2, GCP, or Heroku, then more and more code would be needed to support those services.
• Running tests in CI is important. We built QA environments initially for manual testing, but once complete, the main request from our developers has been to support integration and smoke testing in CI. Automated tests that run on every PR can catch edge cases that developers could miss during manual testing. You should strive to automate as much as possible for developers to speed up their workflow and release stable code on a quicker cadence.
• Storing configuration in environment variables is important. This makes it really easy to deploy the same Docker image in different environments. E.g., we have a Rails app that stored gRPC service hostnames in a YAML file. This is much messier to deal with, because QAC would need to have knowledge about how that specific application is written to modify the hostnames if those gRPC services were running in the same QA environment. (We just ended up moving these hostnames into environment variables to solve this.)

Conclusion

QA environments are non-trivial. Three engineers (Nathan Shelly, Gordon Koo, and myself) spent about six months tackling tricky Helm templating, solving ingress routing, modifying pipelines, setting up multiple new services, etc. When built thoughtfully, though, the final solution can be fairly robust and easy to extend.

The initial work to set this up pays off when it allows developers to test their pull requests before merging in a way they never could previously. Designers, product managers and QA teams can now interact with changes before they go live to customers. Automated tests can avoid flaky failures from mutation race conditions with another test. It’s possible now to have a safe, independent environment to debug a tricky issue that doesn’t show up locally without risking breaking staging for other devs. QA environments give developers confidence in the important things: releasing faster with fewer bugs.

We hope you found this article useful and helpful if you’d like to build this kind of infrastructure yourself. If you’d like to work with us on this kind of project here at Opendoor, we are hiring!

Deep Dive: Testing a Microservice Architecture with QA Environments was originally published in Open House on Medium, where people are continuing the conversation by highlighting and responding to this story.

Open source software is critical to us here at Opendoor. That’s why we engage with the community through upstream feature development, strive to open source our own projects, and make financial contributions. This article describes some of the ways we’ve developed to give back to the open source community:

• Contributing code to open source projects
• Funding open source
• Open sourcing our own projects

Contributing Code to Open Source

Like many companies, Opendoor leans heavily on open source software to power its business. If we think of Opendoor’s engineering work as a pyramid, our business logic is the tip, the base includes large projects like web servers, databases, operating systems, compilers, etc., and the mortar is smaller projects that often just do one specific thing but make our lives easier.

Sometimes there are bugs in the base or the mortar, or features we’d like to have. Whenever this happens, we like to develop fixes and share those. We can’t always do that, of course, so sometimes we might just report the issues to the maintainers and develop a workaround. But we know that many maintainers are volunteers who are hard-pressed to make the fixes themselves. That’s why we like to contribute fixes when we can.

As an example, one of our data engineers, Graham Place, added a feature we need to the Snowflake Terraform provider. (You can read more about that on his blog post about Terraforming Snowflake as well.)

Funding Open Source

It’s naive to take open source software for granted. Indeed, as mentioned above, open source software undergirds much of what Opendoor does. For example, all our production code runs on Linux. Our compilers and interpreters are all open source. Our machine learning and data pipelines are all built on top of open source software, too. If not for open source software, our business would need to expend significant resources to develop our own software. There are smaller projects as well, which would take our engineers days, weeks or months to reimplement if they weren’t available as open source. These are just a few examples to show the massive impact open source has on our business, and our dependence on it.

Many smaller projects are maintained by individuals who have full time jobs. They’re mostly time constrained. The best way to help out with these projects is to contribute code. It’s often easier to do on small projects than big ones. However, most people don’t. It’s easy for maintainers of small projects to burn out from requests, but little reward for their work beyond building something useful.

But sometimes contributing code isn’t enough to help maintainers. For large projects in particular, maintainers often have costs associated with hosting, legal issues, or engaging bug bounty hunters. It’s also often hard to contribute significant bug fixes or features to larger projects, due to the complexity of ramping up.

That’s why we also like to fund open source. Opendoor’s policy is to donate $5,000 each quarter to an open source project we use. Funding these projects helps keep maintainers motivated and can speed up improvements and bug fixes. We’d like to fix every bug we find, or contribute every feature we need, but unfortunately that isn’t realistic. We also want to show appreciation to those projects that we depend on every day that don’t need any code changes. Giving money is the simplest way to show appreciation and help out.

Here’s how we decide who’ll receive the funds each quarter. (Note: Our process is greatly informed by Indeed’s process, as well as Microsoft’s and Saleforce’s and a handful of others.

To be eligible, the open source project must:

• Be used by Opendoor or one of its subsidiaries
• Use an approved license
• Have an approved mechanism for receiving funds
• The mechanism must be approved by our finance team; any credit card processing mechanism, for example, will probably be approved.
• Not be owned by an Opendoor employee

Our engineers have one week per quarter to nominate eligible open source projects. The engineers then vote, and we make a $5,000 donation to the top pick. Note: We don’t discriminate against smaller or larger projects. We encourage the engineers to vote for the project that can use the money best.

Who We’ve Funded

This is a new policy for us, and we’re excited about it. In the first quarter of 2021, we gave $5,000 to PostgreSQL, which is our database of choice.

Many of our engineers voted for PostgreSQL. One of our Analytics Leads, Rachid Belaid, wrote a short memo explaining why:

PostgreSQL has been a key technology to help Opendoor become a multibillion dollar company that operates in 30+ markets. PostgreSQL usage grew with us.

PostgreSQL was our first data warehouse. In the early days of Opendoor, we had few services and separate databases. Analytics was always a critical part of how we make decisions. With our services using PostgreSQL, it was easy to move a copy of our data in a centralized PostgreSQL instance we used to run analytics. It was stretching what PostgreSQL was made for, but it allowed us to get started quickly, at low cost and build a solid analytical culture. We outgrew our PostgreSQL instance after a few years and moved to a solution more optimized for data warehousing (currently Snowflake).

PostgreSQL is great for geospatial data. Running a company in the real estate business requires a lot of geospatial processing. To be able to make an accurate decision, we depend on a lot of features surrounding the house. PostgreSQL with PostGIS has been a huge part of our pricing or eligibility decision making. For example, every time we detect that a home is close to a flood zone or a highway, we use this to adjust our decision. This is all powered by PostgreSQL.

PostgreSQL helped us move our data while breaking up our monolith. Opendoor started as a few monoliths. As the company grew, we decided to create some separation of concerns and increase our overall architecture stability. When we broke down our monoliths into smaller services, we needed to migrate data to preserve history. Luckily, the PostgreSQL foreign data wrapper allowed us to backfill data from one database to another.

We look forward to many more funding awards such as this.

Open Sourcing Our Own Projects

Ideally, we’d like to open source any non-business-specific code we write. This is hard to do when you’re trying to move quickly. It often takes a lot of effort to separate the business parts and write code in a way that’s generic enough for others to use. That said, we try.

For example, we open-sourced our RETS client (a standard data format for real estate data from and MLS). Most recently, we open-sourced pggen. The easiest way to browse our open sourced code is via our public Github repos (and also here).

Interested in joining our team? Check out some of our open roles, Software Engineer, Sr. Software Engineer (backend), Sr. Software Engineer (full stack), Sr. Software Engineer (front end)
Want to learn more about working at Opendoor? Check out our Design blog and recent Opendoor news + more employee spotlights.

Open Source at Opendoor was originally published in Open House on Medium, where people are continuing the conversation by highlighting and responding to this story.

At Opendoor we have quite a few Python services. Originally they were spread across several Git repos, which caused some issues I will describe shortly. To eliminate these issues, we decided to put all our new Python services in a single Git repo, although the services remain independent. This article explains what worked well for us, including repo organization, dependency management, code sharing, and CI/CD.

Background

First, it’s worth mentioning our original Python services setup and what issues we encountered with it. Originally, we had several Git repos containing Python services and libraries. Generally, libraries were in separate repos from the services that relied on them. They were packaged as wheel files and pushed to an internal package repository — essentially an internal PyPI — where services could then pip install them. While most of these services were in their own Git repos, one repo had grown rather large and contained several services.

We ran into several issues with this setup:

• It was cumbersome to update libraries. Both the library’s and the service’s repos required their own sequentially deployed PRs, so engineers needed to merge the library change first, wait for the package to be published to our internal package repository, and bump the version in their service.
• It was difficult to test library changes. It was basically impossible to test that a library change didn’t break any services or other libraries that used it. An engineer could, in theory, track down every service that used the library and run all the tests, but practically speaking, nobody has time for that.
• Because of the difficulty of changing libraries, engineers wouldn’t abstract their code into libraries. Instead, they’d put all their code into their services, and if somebody else needed similar code, they would often copy and paste it.
• The repo with several services became disorganized as people tried to share code. We inadvertently created cyclical dependencies, lost visibility into code ownership, and misunderstood what code was meant to be shared. Premature sharing of code sometimes led to abstractions breaking or team disputes over how to abstract it.
• Search-ability was low. Python code searches required Github search, which isn’t nearly as convenient as searching in an IDE.
• Every repo had its own linting and formatting configuration, which made it more difficult for developers to navigate and contribute across repos.

To avoid these issues, we decided to put all our new Python services in a single Git repo.

Monorepo Structure

Jumping directly to our solution, let’s start with an overview of how we organize our projects, libraries, and tools in the monorepo:

py
├── projects  # Each project contains code for a service and/or ETL
│   ├── project1
│   │   ├── Dockerfile
│   │   ├── pyproject.toml  # Each project has its own dependencies
│   │   ├── project1/       # Project code (Python modules) go here
│   │   └── tests/
│   └── project2...
├── lib  # Each lib is a Python package that you can install using poetry (or pip)
│   ├── lib1
│   │   ├── pyproject.toml  # Each lib specifies its dependencies
│   │   ├── opendoor/lib1/  # All internal packages are in the opendoor namespace 
│   │   └── tests/
│   └── lib2...
└── tools
    ├── pippy  # Our service generator
    ├── pyfmt  # Code formatter to be used across all Python code
    ├── ci/    # Common CI/CD infrastructure
    └── other tools...

Projects cannot import any code from other projects, eliminating import cycles, unintended sharing, and keeps the code organized. Code intended to be shared needs to be put in an internal library. Each project also has its own CI/CD pipeline, although the pipelines are all based on a common template to keep them from diverging. When a PR is created in a service, it runs that service’s tests. When the PR is merged, it builds that service’s Docker image and deploys it to our Kubernetes cluster. If a PR spans multiple services, then each included service’s CI/CD pipelines will run.

As for libraries, one major improvement over our old system is that if a PR is made in a library, then the tests for all services and other libraries that use it will run in CI. You can’t merge library changes until all the tests pass. This is only possible because all the code is in a single repo. This makes it much easier to update libraries. I’ll get back to how we do this in more detail later.

Our tools directory has our service generator (named pippy), which uses cookiecutter to generate services from a standard template. It’s basically a command line wizard that asks what the service name is, whether it needs a database, what Slack channel to send related notifications to, etc. E.g., if your service needs a database, pippy will generate a Terraform script to create one and run migrations in the deployment pipeline. It also generates the CI/CD resources needed, which I’ll get a bit more into below. The tools directory also contains common tools like pyfmt, our formatter (basically a script that runs isort and black).

This structure eliminated some of the most basic issues we’d encountered but, at the same time, triggered new strategic decisions, specifically around how we manage dependencies.

Dependency Management

This is where things get really interesting. The following two points were quite a divergence from our previous system, and required a lot of thought and testing:

• We use poetry instead of pip for package management.
• We use “editable” installs for libraries.

Let’s start with the first point. poetry is a modern dependency management tool for Python that provides a number of benefits over pip:

• poetry does complete constraint satisfaction on dependency versions, unlike pip which happily installs packages that violate version constraints (this is changing soon though).
• poetry generates a lock file, so we can ensure that everybody tests with the same versions of dependencies that we run in production. If you have a constraint like foo>=1.0 in your requirements.txt, then when you install dependencies, you might get different versions locally from CI or production. Lock files solve this by allowing foo>=1.0 as a requirement, but it will get pinned until someone runs poetry update.
• poetry maintains a Python standard pyproject.toml file with direct dependencies and a separate poetry.lock file with dependencies of dependencies. The respective requirements.txt files from pip can get bloated easily. Often people do pip freeze > requirements.txt, which generates a list of every package version installed in your Python environment. The problem with this is that it includes dependencies of dependencies, so your requirements appear larger than they should be. It could also include packages you just happened to install, but aren’t required for your project.
• Another problem with requirements.txt is that it’s only used for development. When packaging a wheel file, dependencies must be specified in setup.py. This discrepancy is hard to manage.
• Lastly, poetry has some other features above what pip provides, such as improved integration with virtual environments and nudges towards best practices. It’s also more intuitive to developers familiar with other package managers (like yarn).

The second interesting choice we made was to use editable installs for libraries. Using poetry, this is done with “path” dependencies: poetry add ../../lib/grpc. When we install an internal library this way, everything generally works the same as if we installed it from a package repository — we can import from it, and its dependencies get installed — but it also links back to the local library directory. If you edit the library locally, there’s now no need to reinstall it, solving the problem of library changes being difficult. You can test the library and service changes locally in a very natural way as well as push and test your changes in the same PR.

When you make a PR including a library change, CI will also run the tests for all other code that uses that library. The way we accomplish that is as follows. The CI task looks at what files have changed in a PR. It then filters that down to which libraries have changed. It then looks at the poetry.lock file for each service and library (including those not in the PR) to see if it includes a changed library. Since poetry.lock includes recursive dependencies, this also identifies when a changed library is a dependency of a dependency. It then runs the tests for any service or library affected by the PR.

Another benefit of editable installs is that internal library versions will always be up to date. This can greatly reduce support costs. E.g., if the team that owns, say, our gRPC framework library wants to update it, they need to make sure they do it in a non-breaking way, or fix services as they go. Every service will use the same version. At other companies I’ve seen the scenario where libraries were versioned, so teams would make breaking changes to them. Because dedicated time was needed to fix the unavoidable update problems, services wouldn’t update quickly (or sometimes ever), leading to services using many different versions of the same library, some quite stale. This increased support costs for the team owning the library, as they had to help with multiple versions, and it slowed down development overall.

poetry can also build and publish wheel files. So we still publish our internal libraries to our internal package repository. That way they can be installed with pip in other repos that we haven’t moved into our monorepo yet. In that case, they are versioned. There’s more detail on this in this comment.

CI/CD

As mentioned before, each service and library has its own CI/CD pipeline. The tests are triggered when a file in the service or library is directly changed in a PR, or when a library it depends on is changed in a PR, but the services themselves are only deployed if a file in the service is changed (i.e., we don’t automatically redeploy services if only an internal library changes).

All the CI/CD pipeline code and configuration is shared across libraries and services as a single template. Each library and service defines a YAML file with values that populate the template. This allows us to make improvements to the pipelines across all services at once.

Libraries

All our libraries use namespace packaging, which simply means that they’re separately installable but share an opendoor package prefix (e.g., opendoor.grpc for our gRPC framework). Some notable libraries include:

• A gRPC framework. This includes interceptors for automatically logging service requests, latency metrics, and capturing exceptions to send to Sentry.
• A Kafka framework.
• Postgres utilities.
• Protobufs. This is basically all the Python types and stubs automatically generated by our protocol buffer schemas. This makes it easy to install this lib and use it to make RPCs to other services. E.g., from opendoor.protobuf.foo.foo_pb2 import FooRequest and from opendoor.protobuf.foo.foo_pb2_grpc import FooStub.
• S3 utilities.
• Testing utilities.
• We have other more niche libraries as well, such as for ML.

Lessons Learned

All told, our Python monorepo has felt like a huge success. It’s much more organized. Updating and testing libraries is much better. It’s also been much easier to consolidate CI/CD pipelines to make global improvements.

That said, there have been some pain points:

• Python developers familiar with pip had to get acquainted with poetry. While we rolled poetry out on a single service first to fix some major pain points before rolling it out more widely, it’s never easy to learn new tools when you’re trying to get things done quickly.
• We bet on poetry early on, before the 1.0 release. While it’s generally been stable, we occasionally ran into issues on the bleeding edge release. It was a tough choice to tradeoff the stability of pip with the more modern features of poetry, but we felt it was headed in the right direction quickly enough.
• Some other opensource tools aren’t adapted well to monorepos. E.g., linters are intended to be run on one project, in one virtual environment, at a time. If you try to run, say, pylint project1 project2, where those each have their own virtual envs, it won’t work correctly. Hence we had to write tooling around many of these tools to make sure tools always work as expected.
• Likewise, many CI/CD systems aren’t setup to handle monorepos, so you’ll need to invest in some tooling to get it working. Similarly, to build Dockerfiles optimized for layer caching, we needed extra tooling. So basically, if you have a monorepo, expect to invest in tooling around it.
• We lowered the bar for writing libraries so much that it’s important to keep an eye on these and make sure the code is tested, high quality, and should actually be part of a library. For that reason we have a group of Python reviewers for shared code (this isn’t a formal team within the company, just code reviewers).
• As I mentioned, although I’d love to say all our Python code is in our monorepo, there’s still some code outside of it. We moved almost all of the single-service repos into the monorepo, but repos that were doing “unusual” things (multi-service, for example), we left out. This hasn’t been an issue, but it is hard to actually migrate all of our code to a consistent structure.

I think our monorepo setup should work very well for almost any small to medium sized companies using Python. It might even work well for huge companies! We currently have about a dozen internal libraries and two dozen services in our monorepo, and I think it could scale to at least 10x that. I hope this has been helpful to other teams who are thinking about how to organize their Python code. As always, we’re looking for passionate and thoughtful developers if you’re interested in working with us.

Our Python Monorepo was originally published in Open House on Medium, where people are continuing the conversation by highlighting and responding to this story.

Hence, I started getting more interested in actually understanding what neural networks are doing, and hopefully building up an intuition about how to use them better.

As a short aside, I feel that neural networks are becoming very popular because they can solve a lot of problems that we don’t have good alternative solutions for (image and speech recognition, etc.). Because of that, there’s a lot of hype and some people seem to think they they can solve anything. This isn’t true, and I think part of the problem is that when you don’t understand what something is actually doing, it becomes natural to attribute almost mystical properties to it. So I think it’s important to dispel the idea that neural networks are somehow magical things that can solve any problem or are better than any other way of doing anything. Let’s begin!

First, I’m not assuming anyone reading this has much machine learning or neural network background, but I must start somewhere. So I want to start with a linear regression since I think many people are familiar with the concept. Here’s an example:

Hopefully everyone is somewhat familiar with this concept. We have some data points, and we want a line that captures a trend. Good enough. There are some old and very well understood algorithms to find this line (read the linear regression section of any stats book). The equation of this (or any line) can be generalized as follows (if you aren’t comfortable with mathematical symbolism, that’s fine, just skip the mathematical expressions):

I’d like to talk about classification rather than regression though, since I think it’s a bit more intuitive for this article. The idea is much the same, except instead of finding a line that goes through some data points, we want to find a line that separates two sets of data points from different classes (or categories). Here’s an example:

The equation is very similar, we simply replace the equality with an inequality:

Instead of finding a line where the data points are on the line, we find a line where the data points are on one side of the line.

Linear separability is a very useful tool. E.g., if the red data points in the above image represent, say, some attribute of diseased cells, and the green data points represent those same attributes in healthy cells, then medical researchers could use the classifier to see if a drug is making diseased cells healthy.

The problem is that it’s often not that simple. For example, let’s say our data points looked more like this:

This is impossible to separate with a line, hence no linear classifier will do a good job.

However, for some cases we can be clever and solve the problem. This example is one such case. Since we notice that the data points roughly form circles, and the centers of the circles are at (0, 0), we can replace each data point with its distance from (0, 0). The green points will have a distance of roughly 0.9, while the red points have a distance of roughly 1.8. Hence, the distances are linearly separable:

In other words, we transform the original data with the following function, and then classify y:

But what if we can’t figure out how to transform the data? E.g., this one isn’t so simple:

We could probably think of some transformation, but in real world data it’s much more complicated. First, real world data typically has more than two dimensions, so you can’t easily visualize it, which makes it harder to guess transformations. Second, real world data is often just messier, so guessing a transformation would be incredibly difficult and ultimately probably wrong anyway. Finding these transformations automatically with algorithms is the essence of neural networks (and also many other machine learning techniques).

You’ve likely seen a diagram of a neural network that shows “layers” of neurons, like this:

When learning the basics on neural networks, we learn that each “neuron” (each circle in the diagram), is a linear function of the other neuron outputs going into it. Essentially, each neuron is a linear function, just like the linear regression we started with:

Yes, there is a non-linearity after it, but let’s ignore that for now.

Here’s an important concept. The outputs of the final hidden layer are (ideally) linearly separable. The output layer is simply a linear function, so if the neural network is working perfectly (i.e., classifying with 100% accuracy), then the inputs to the output layer are linearly separable. (It’s true that often the output layer has a non-linearity such as a sigmoid or softmax, but this simply scales the output, it doesn’t add classifying power. It’s there to make the error easier to minimize.)

So said differently, all the hidden layers do is transform the input so that it’s linearly separable to the final output layer. Training a neural network is basically finding a transformation, like the distance-from-zero one, just a much more messy and complicated one.

In order to really start building intuition, we can see how this works in our very small neural network from the diagram above. Note that the input layer has two neurons, which means the input is two-dimensional. This was chosen so we can visualize the data. We’ll choose the “moon” shaped data from above.

The hidden layer has three neurons. Remember, each neuron is a linear function. In this case, each linear function has two inputs. This means that we can draw these lines to visualize them. When I trained this network on the moons data, here are the lines that the network “discovered” for the three hidden neurons:

Ok, let’s talk about those non-linearities now, because they are important. We need them because if you compose two or more linear functions together, you get another linear function. In other words, if each neuron were purely a linear function of its inputs, then the entire neural network would end up being a big, overly complicated linear function.

In this network I’m using a “ReLU” non-linearity, which is simply max{0,y}. The way you can think about this is by looking at one of the lines in the plot above. The ReLU will set one side of the line to zero. The other side of the line will be positive and increasing linearly as you move away from the line. So try mentally “shading” one side of each line in the plot above, and you’ll start to see how the red dots fall within the shaded area (or the green dot depending on whether you mentally shaded above or below each line).

Now, what happens in the output of the hidden layer, is that the shaded areas get summed up resulting in positive output, while the non-shaded zero areas result in zero (they also get summed, but 0+0=0). Hence, you get red=positive and green=0. In other words, just like in the distance-from-zero example, we’ve transformed the data to be linearly separable.

If you’re like me, this might be helpful for building intuition for what neural networks are doing, but the more important part is building intuition for how to use them. For example, using this small neural network example, we can see how using a ReLU vs. sigmoid (or tanh) as a non-linearity can make a difference. Near the lines, there wouldn’t be much difference, but far from the lines the sigmoid (and tanh) plateau. Hence, intuitively the ReLU can have greater influence far away from zero. If your data is very spread out spatially, you might be able to fit it with fewer neurons by using ReLU (this depends on the data, but it’s just one way to think about it). There are other benefits of ReLUs, but this is something that might not be obvious without visualizing how the network works.

Another example is dropout. I’ll leave this one up to you for now. How might you visualize the effect of dropout in this small neural network? What about collinearity of neurons? I might write about these in the future, but hopefully this has sparked some interest in thinking about them yourself.

Before I finish, I’ll mention that you can also watch small neural networks train, which can also build intuition. Here’s a time lapse of the above network training. (Note that this is a different training run than the one that generated the lines above, so the lines are different.) It’s interesting to watch a network train many different times, to see how the initial randomness affects them.

The first plot shows the lines formed by each hidden layer neuron, as explained above. The second plot shows the “decision boundary”. What that means is that it shows the dividing “line” (which is not straight, so should be more properly called a contour) where the network decides that one side is one class (e.g., green), and the other side is the other class. This is formed more or less by looking at where the output of the hidden layer is zero. The third plot shows the transformation that the network learns. In other words, it shows how the input data gets transformed by the hidden layer. You can see that the hidden layer learns to transform the input so that it’s linearly separable.

I hope you’ve found this interesting and that it helps you build some intuition about neural networks and the variations you can choose with them. I’ll post code for the visualizations below, so you can explore more on your own if you’d like.

Learning from Small Neural Networks was originally published in Make Computer Science Fun Again on Medium, where people are continuing the conversation by highlighting and responding to this story.

This article was originally part of Remix’s series on the software engineering problems they face. In this installment, Dan Hipschman walks through bus driver scheduling and a simplified approach to solving it using integer programming.

I studied NP-Hardness in school but never tackled any problems in real life. Until now.

At Remix, I finally encountered NP-Hardness, adding a powerful new tool called integer programming to my tool belt. This is an intro to integer programming for engineers who haven’t used it. The goal is for you to start thinking about some ways you can use integer programming and wanting to learn more.

The Bus Driver Scheduling Problem

Let’s start with a motivating example. At Remix we improve public transportation, especially bus systems. Have you ever wondered how bus drivers coordinate their lunch breaks? Or if you aren’t on the bus that often, maybe you’ve wondered how flight attendants and pilots fly around the world and end up back home, which is a similar problem. We’re going to solve the problem of scheduling bus driver shifts in this post. I’m going to include working code, so for the full experience, please break out your shell and editor to follow along.

Let’s frame the problem. Say we have four bus routes, called A, B, C, and D. Let’s assume that each route takes an hour to complete. They’re loops, so they start and end in the same place. Each route has one bus running on it from 9 AM until 9 PM. Finally, the routes all converge at the same point every hour on the hour, so it would be easy for drivers to switch shifts and take their lunch breaks at that location. I drew some demo routes that all converge in the top right of the map to make this clear.

Since our bus service runs from 9 AM until 9 PM, and each route takes an hour to complete, we’ll have 12 full trips for each route (48 total trips). Let’s represent each trip as a tuple: (route_name, hour_of_day). Let’s write a function to generate these. Don’t worry if you don’t know Python, we’ll keep it simple.

Here’s our resulting 48 trips:

>>> generate_trips('ABCD', 9, 12 + 9)
[('A', 9), ('A', 10), ('A', 11), ('A', 12), ('A', 13), ('A', 14), ('A', 15), ('A', 16), ('A', 17), ('A', 18), ('A', 19), ('A', 20), ('A', 21), ('B', 9), ('B', 10), ('B', 11), ('B', 12), ('B', 13), ('B', 14), ('B', 15), ('B', 16), ('B', 17), ('B', 18), ('B', 19), ('B', 20), ('B', 21), ('C', 9), ('C', 10), ('C', 11), ('C', 12), ('C', 13), ('C', 14), ('C', 15), ('C', 16), ('C', 17), ('C', 18), ('C', 19), ('C', 20), ('C', 21), ('D', 9), ('D', 10), ('D', 11), ('D', 12), ('D', 13), ('D', 14), ('D', 15), ('D', 16), ('D', 17), ('D', 18), ('D', 19), ('D', 20), ('D', 21)]

The driver scheduling problem is that we have some work that needs to be done, and we need to assign it to drivers. In other words, we want to come up with a set of duties for the bus drivers, where a duty is simply a list of trips the need to drive. Every trip must be part of exactly one driver’s duty. Let’s further assume we have some rules from payroll:

• Each duty over four hours should allow the driver to have a break
• Drivers get paid for each hour they work, but not for breaks
• They get a minimum pay of eight hours for coming into work (known as guaranteed pay)
• They get 1.5x pay for each hour they work over eight hours (overtime pay)

We’d like not only to determine a set of duties, but the payroll department would like us to minimize driving costs. How do we do this? Well, as you might have guessed, we use integer programming… somehow. But first let me explain what integer programming is.

What Is Integer Programming Anyway?

As a precursor to integer programming, I’m going to define linear programming. Linear programs are mathematical models and there are algorithms to solve them. Let’s start with a linear expression. This is called the objective function:

The goal of linear programming is to minimize some objective function. By “some” objective function, I mean that n and the a’s are all known for a particular problem. E.g., 3 * x1 + 14 * x2.

Now, of course, if that was all there was to it, we could just set all the x to zero. However, linear programs are also allowed to have one or more constraints. Constraints are each simply another linear expression, set less than or equal to zero. Note that the coefficients of the x’s can be different than the objective, and there can be a constant term as well. E.g.,

And so on. There can be as many constraints as you like. Note that some factors in the constraints could be zero, effectively meaning that not every variable needs to be in every constraint.

Equality is allowed, using a sort of “trick” which you can verify. The following:

is equivalent to:

OK, so given the objective and the constraints, the goal of linear programming is to minimize the objective.

Let’s Jump Into a Shell

Let’s make this concrete and jump into a shell. We can install and use a Python integer programming solver library to demonstrate all this (it also solves linear programs). The Python package is called Pulp. Here’s a demo:

$ pip install pulp
$ python
>>> from pulp import *
>>> x1 = LpVariable('x1')
>>> p = LpProblem('p', LpMinimize)
>>> p += x1
>>> p.solve()
1
>>> LpStatus
{0: 'Not Solved', 1: 'Optimal', -2: 'Unbounded', -1: 'Infeasible', -3: 'Undefined'}
>>> x1.value()
0.0

Let’s walk through this line by line.

$ pip install pulp

This simply installs pulp. If you’re not in a virtualenv, you might need to use sudo.

>>> from pulp import *

This imports Pulp. I’m going to be lazy and import everything into the global namespace using *. Everything in Pulp starts with “Lp” or “lp” so it should be clear what came from the module.

>>> x1 = LpVariable('x1')

This creates a variable. The argument is the name, which is arbitrary (just make it unique if you create more than one variable).

>>> p = LpProblem('p', LpMinimize)

This creates a problem, which is Pulp’s way of keeping pieces of the linear program together. The first argument is another arbitrary name. The second is LpMinimize because the default is to maximize the objective. (Minimizing and maximizing are mathematically equivalent — multiply the objective by -1 — so linear programming can do both).

We’ll “add” the objective function with the following syntax (Pulp uses a lot of operator overloading):

>>> p += x1

Hence our objective function is as follows:

Not very exciting, but let’s see what happens.

>>> p.solve()
1
>>> LpStatus
{0: 'Not Solved', 1: 'Optimal', -2: 'Unbounded', -1: 'Infeasible', -3: 'Undefined'}

The solve function returns a status. The different statuses are described in LpStatus. In this case, Pulp is telling us it found an optimal solution to the problem. After calling solve, the variables will have their value set to whatever minimizes the objective. So let’s inspect:

>>> x1.value()
0.0

Pulp tells us that the assigning 0 to x1 minimizes the objective (remember that all the variables are nonnegative). In this case the problem was trivial.

So let’s add a constraint:

>>> p += x1 >= 1
>>> p.solve()
1
>>> x1.value()
1.0

This adds a constraint that x1 >= 1, and then re-solves. Obviously the minimal value of x1 is now 1, since 0 is not allowed by the constraint. Now our complete linear program is:

Progress! We’ve learned how to write and solve linear programs using Pulp.

Solving the Driver Scheduling Problem

Let’s move on to integer programming, and how it gets us closer to solving our driver scheduling problem.

An integer program is exactly the same as a linear program, with the additional constraint that all x are integers. I.e,

Without getting into theory, I’ll just mention that solving integer programs is an NP-hard problem. However, there are algorithms that can often solve them much faster than brute force.

Pulp can also solve integer programs, which I’ll show you in a bit. But first, let’s discuss the high level approach to how integer programs will solve our original driver scheduling problem. We’ll solve our problem by modeling it as a weighted set partitioning problem. This image gives an intuitive idea of the problem:

The idea is that we have a set of items, represented by the points in the lefthand image above. We also have a set of sets, each represented by a squiggly loop in the left image. In this case, for example, there are seven sets (trust me, since counting them is probably bad for your eyes). The set partitioning problem is to find the smallest number of sets that contain all the items (points), without any overlap between sets (hence a “partition”). Every point must be in one and exactly one set. The solution to the problem above is shown on the righthand side.

The weighted set partitioning problem is when we assign a cost to each set. Then, instead of minimizing the number of sets, we minimize the sum of the values of the sets we choose. You can see that if we set all the weights to one, we get the original set partitioning problem.

Set partitioning is NP-complete (both weighted and unweighted). However, we can use integer programming to solve it optimally. NP-complete doesn’t mean that problems are always slow to solve. It only means that we can construct degenerates cases that cause any general algorithm to run slowly some of the time. At least, to the best of our knowledge (unless someone proves P=NP). Integer programs can often be solved relatively quickly.

In our problem, the dots in the set partitioning diagram are trips a bus takes from its origin to its destination (our tuples), and the sets are potential driver duties. In other words, each duty is a set of trips that a driver could potentially do. We’ll assign a weight to those sets using the driver pay rules we defined above (overtime, guarantee pay, etc.). When we solve the weighted set partitioning problem, we’ll get the set of duties that cover all the trips and minimize the sum of individual drivers’ costs. This is exactly what we want.

So here’s how we’ll do it. Each potential duty will be a variable (an x) in our integer program. We’ll further constrain all the x to be between zero and one. Since they’re integers, this actually restricts them to be exactly zero or one. The idea behind this is that a particular x will be one in the solution if the solver decides that using the duty is part of the optimal solution, and zero if the duty is discarded as not being part of the optimal solution.

The coefficient of each x is the cost of that duty in terms of driver pay.

Hence our integer program looks like this (let’s use p for pay instead of the a’s we were using above):

This means we have n potential duties. Each p is the driver pay (hence payroll cost) of the duty. We want Pulp to choose some x’s to be zero and some to be one. By doing this, our objective function will turn into the sum of the payments we have to make. And we want to minimize this.

Of course, as is, there are no constraints that some x need to be selected (set to one) at all. Hence, Pulp will helpfully set all x to zero to minimize the objective. What constraints do we need to add?

Well, every trip needs to be in exactly one duty. So we can add a constraint for every trip, so that the x’s corresponding to the duties that trip appears in sum up to 1. For example, we might have a constraint like this:

This assumes for simplicity’s sake that the first five x’s correspond to the duties containing trip ('A', 9). Likewise, we’d have a constraint like this for every other trip.

These constraints say that for a given trip, exactly one duty must include it. No more, no less.

Time to Write Some Code!

OK, so we’re ready to write some code to solve our problem! Well, we’re close! But there’s one more hitch. Where are we going to get all the possible duties from? Generating every possible duty explodes exponentially with the number of trips. Hence, for now, we’ll randomly generate duties, and see what happens.

We already have code written above to generate the set of trips. Let’s write a function to randomly generate some duties from those trips. We’ll make sure that we don’t generate a duty with multiple trips that occur at the same time.

So let’s write it like this:

• We’ll randomly choose the number of trips in the duty
• Then we’ll randomly choose the hours for those trips
• Then we’ll randomly choose the routes for each trip

Here’s the fully functioning code to generate trips and duties (extending the code above):

When I run this, here’s what I get:

$ ./duty_generation.py
[[('A', 14), ('A', 18)],
 [('A', 9), ('B', 11), ('B', 12), ('D', 14), ('A', 15), ('A', 16), ('D', 18)],
 [('C', 17), ('B', 18)],
 [('C', 18)],
 [('B', 9), ('C', 11), ('A', 16), ('B', 18), ('D', 19), ('C', 20)]]

Great! Now let’s write a function that tells us how much each duty costs:

And here’s what the output looks like when I run it (I actually ran it a few times to get an interesting mix of costs):

[(1000000.0,
  [('C', 9),
   ('A', 10),
   ('C', 11),
   ('C', 12),
   ('B', 13),
   ('A', 14),
   ('B', 15),
   ('C', 16),
   ('A', 17),
   ('C', 18),
   ('B', 19),
   ('B', 20)]),
 (8, [('B', 12), ('A', 13), ('C', 17)]),
 (8, [('B', 11), ('D', 13), ('D', 14), ('A', 16), ('A', 17), ('C', 19)]),
 (8, [('C', 16)]),
 (11.0,
  [('C', 10),
   ('A', 11),
   ('C', 12),
   ('D', 13),
   ('C', 14),
   ('D', 15),
   ('A', 16),
   ('A', 18),
   ('B', 19),
   ('C', 20)])]

The Fun Part

OK! Now for the really fun part, solving the problem! Here’s the code. Recall the Pulp code we wrote above, as we’re building on top of it.

Here’s the complete runnable code.

Let’s run it and see what happens. The output will be fairly long because I’m asking Pulp to print a representation of the problem. I’ll truncate some repetitive parts to make it shorter:

driver_scheduling:
MINIMIZE
12.5*x1 + 8*x10 + 8*x11 + 8*x12 + 8*x13 + 8*x14 + 8*x15 + 8*x16 + 8*x17 + 8*x18 + 8*x19 + 9.5*x2 + 8*x20 + 8*x21 + 8*x22 + 8*x23 + 8*x24 + 8*x25 + 8*x26 + 8*x27 + 8*x28 + 8*x29 + 8*x3 + 8*x30 + 8*x31 + 8*x32 + 8*x33 + 8*x34 + 8*x35 + 8*x36 + 8*x37 + 8*x38 + 8*x39 + 1000000.0*x4 + 8*x40 + 8*x41 + 8*x42 + 8*x43 + 8*x44 + 8*x45 + 8*x46 + 8*x47 + 8*x48 + 8*x49 + 11.0*x5 + 8*x50 + 8*x51 + 8*x52 + 8*x53 + 8*x6 + 8*x7 + 8*x8 + 8*x9 + 0.0
SUBJECT TO
_C1: x7 = 1

_C2: x33 = 1

_C3: x1 + x45 = 1

_C4: x14 + x2 + x5 = 1

_C5: x1 + x20 + x4 = 1

...

_C47: x25 + x4 = 1

_C48: x24 = 1

VARIABLES
0 <= x1 <= 1 Integer
...
0 <= x9 <= 1 Integer

Optimal
Cost: 239.5
[[('B', 9),
  ('B', 10),
  ('B', 11),
  ('D', 12),
  ('D', 13),
  ('D', 14),
  ('D', 16),
  ('B', 17),
  ('D', 18),
  ('D', 19),
  ('B', 20)],
 [('D', 10),
  ('C', 11),
  ('B', 13),
  ('B', 14),
  ('D', 15),
  ('C', 16),
  ('A', 17),
  ('B', 18),
  ('A', 19),
  ('D', 20)],
 [('A', 9)],
 [('A', 10)],
 [('A', 11)],
 [('A', 12)],
 [('A', 13)],
 [('A', 14)],
 [('A', 15)],
 [('A', 16)],
 [('A', 18)],
 [('A', 20)],
 [('B', 12)],
 [('B', 15)],
 [('B', 16)],
 [('B', 19)],
 [('C', 9)],
 [('C', 10)],
 [('C', 12)],
 [('C', 13)],
 [('C', 14)],
 [('C', 15)],
 [('C', 17)],
 [('C', 18)],
 [('C', 19)],
 [('C', 20)],
 [('D', 9)],
 [('D', 11)],
 [('D', 17)]]

So for all our hard work, we have a solution! Hooray! But it’s a pretty crummy one. Most drivers do one trip, get paid the minimum of 8 hours, and go home. Well, it’s good for them, but payroll won’t be happy. This is because we’re only generating 5 duties, of course. Let’s increase that to 100 duties. And let’s also time how long it takes. Here’s the result (without Pulp output this time):

Optimal
Cost: 120
[[('A', 9), ('C', 11), ('D', 13), ('A', 14), ('D', 15)],
 [('A', 10), ('D', 11), ('C', 13), ('A', 16), ('B', 18), ('D', 19)],
 [('C', 17)],
 [('D', 14), ('C', 15), ('D', 16), ('D', 17), ('A', 19)],
 [('C', 9), ('B', 10), ('D', 18), ('C', 19), ('A', 20)],
 [('B', 11), ('C', 14), ('C', 16), ('A', 18), ('B', 19), ('B', 20)],
 [('D', 10), ('A', 12), ('A', 13), ('B', 16), ('A', 17), ('C', 18), ('C', 20)],
 [('D', 9), ('C', 10), ('D', 12), ('B', 13), ('B', 17), ('D', 20)],
 [('A', 11)],
 [('A', 15)],
 [('B', 9)],
 [('B', 12)],
 [('B', 14)],
 [('B', 15)],
 [('C', 12)]]

real 0m1.297s
user 0m0.110s
sys 0m0.000s

That’s much better! The cost is almost half! But it’s still not great. Let’s generate 1000 duties.

Optimal
Cost: 70.0
[[('C', 9), ('C', 11), ('C', 12), ('A', 15), ('C', 18), ('A', 19)],
 [('A', 10), ('A', 11), ('D', 12), ('A', 13), ('A', 16), ('D', 18), ('C', 20)],
 [('A', 9),
  ('C', 10),
  ('A', 12),
  ('C', 13),
  ('B', 14),
  ('D', 15),
  ('D', 16),
  ('C', 17),
  ('B', 19)],
 [('D', 10),
  ('B', 12),
  ('B', 13),
  ('A', 14),
  ('B', 16),
  ('A', 17),
  ('B', 18),
  ('C', 19),
  ('B', 20)],
 [('B', 9),
  ('B', 10),
  ('B', 11),
  ('D', 13),
  ('D', 14),
  ('B', 15),
  ('C', 16),
  ('B', 17),
  ('A', 18),
  ('D', 19)],
 [('D', 9), ('D', 11), ('C', 14), ('D', 17), ('A', 20)],
 [('D', 20)],
 [('C', 15)]]

real 4m41.586s
user 3m11.270s
sys 0m0.990s

Phew, that’s much better. But also much slower! Well, we are solving an NP-complete problem after all. In practice, we could speed this up by generating duties more cleverly. E.g., there’s no reason for drivers to jump back and forth between routes all the time. If we limited that, we could generate more “good” duties, while ignoring “bad” duties without passing them to the solver.

There are also much more advanced techniques to speed up and improve results, but the intent of this article is to whet your appetite.

Integer Programming as a Flexible Framework

So that’s it! We’ve used integer programming to solve our problem. And we’ve saved the effort of thinking up an algorithm for this specific problem, which would probably be either slow, or suboptimal, or both. Integer programming also gives us a very flexible framework for making changes. E.g., if we can customize the cost function to penalize some duties (like those that switch routes too often because that’s confusing). When the problem gets more complicated, such as routes ending in different locations, or trips starting and ending at different times, integer programming can handle that really easily. If you don’t want something to happen you can either just add a severe penalty (like we did with the driver break rule), or add a constraint.

There are many other interesting classes of problems that can be solved using integer programming as well. Since solving an integer program is NP-hard, it can in fact be used to solve many NP and NP-complete problems (as long as you can model it as an integer program without exponential growth). This is a very powerful tool, because it’s often much easier and effective to model an NP or NP-complete problem as an integer program than it is to write an algorithm to solve it. You can also solve polynomial time algorithms using integer programming, and this is still often useful as a first cut solution, and it often turns out to be fast enough.

To name just a few other examples of problems that integer programming is well suited to solve:

• Transportation problems (such as package delivery, or resource delivery such as energy distribution)
• Warehouse and container packing problems
• Matching problems (such as what stock brokerages do to match buyers with sellers, or scheduling which sports teams play each other)
• Map coloring

By the way, Pulp is a Python wrapper around back end solvers written in C. By default it uses CBC, which is an open source solver. There are commercial solvers as well. These are often used for harder problems in industry because they can be much faster. One well-known commercial solver is called Gurobi, and they have many example usages of integer programming. I encourage you to look through some Pulp case studies as well.

I hope you’ve found this interesting! Please comment or share this if you did. We’re planning to write another post going into more depth, so follow us if you’re interested.

Want to work on these types of problems? Remix is hiring!

An Intro to Integer Programming for Engineers: Simplified Bus Scheduling was originally published in Make Computer Science Fun Again on Medium, where people are continuing the conversation by highlighting and responding to this story.