Aug 5, 2019 - Data structures complexity reference

Quick complexity reference for most common data structures, considering efficient implementations usually available in frameworks class libraries.

Array

Time Complexity:

  Average Worst
Indexing O(1) O(1)
Search O(n) O(n)
Insert O(n) O(n)
Delete O(n) O(n)

Space Complexity: O(n)

Linked List

Time Complexity:

  Average Worst
Indexing O(n) O(n)
Search O(n) O(n)
Insert O(1) O(1)
Delete O(1) O(1)

Space Complexity: O(n)

For both single-linked and doubly-linked lists

Stack

Time Complexity:

  Average Worst
Push O(1) O(1)
Pop O(1) O(1)

Space Complexity: O(n)

Queue

Time Complexity:

  Average Worst
Enqueue O(1) O(1)
Dequeue O(1) O(1)

Space Complexity: O(n)

Hash Table

Time Complexity:

  Average Worst
Search O(1) O(n)
Insert O(1) O(n)
Delete O(1) O(n)

Space Complexity: O(n)

Heap

Time Complexity:

  Average Worst
Heapify O(n) O(n)
Find Max O(1) O(1)
Insert O(log(n)) O(log(n))
Delete O(log(n)) O(log(n))

Space Complexity: O(n)

Binary Search Tree

Time Complexity:

  Average Worst
Indexing O(log(n)) O(n)
Search O(log(n)) O(n)
Insert O(log(n)) O(n)
Delete O(log(n)) O(n)

Space Complexity: O(n)

Self-balancing Binary Search Tree

Time Complexity:

  Average Worst
Indexing O(log(n)) O(log(n))
Search O(log(n)) O(log(n))
Insert O(log(n)) O(log(n))
Delete O(log(n)) O(log(n))

Space Complexity: O(n)

Ex: AVL Tree, Red-Black Tree

Trie

Time Complexity:

  Average Worst
Search O(m) O(m)
Insert O(m) O(m)
Delete O(m) O(m)

Space Complexity: O(m * l)

Where:

  • m is the length of the search string
  • l is the length of the character alphabet

Aug 2, 2019 - A successful deployment model

The deployment is arguably the most critical software development life cycle (SDLC) phase. It takes an application from a battle tested generally stable version to a newer version which introduces new features, improvements and bug fixes. As much as we employ automated tests and set up a staging environment for quality assurance (QA), covering all use cases before deploying to production to make sure an application version is free of defects is unfeasible. Hence, a successful deployment model needs to handle not only software release, but also application monitoring and restoration.

The following sections discusses the deployment process in more detail, proposing a handful of rules for successfully managing risks associated with this process.

Deployable Image

In this context the deployable image is an executable package built from the application’s source code for distribution to test, staging and production environments. Two common formats are:

  • Container image: includes the application’s binaries built from source code, the runtime, system tools, system libraries and settings, everything required for running the application in a virtualization platform.
  • Binary package: includes only the application’s binaries built from source code, usually targeting a pre-determined hosting platform, such as a pre-configured virtual machine running a specific OS version.

Generating the deployable image is the first step of deployment, and as a first rule, you should:

Use the same deployable image for test, staging and production environments

This means that whenever a problem is detected and a code fix is required, the newly generated deployable image validation should start back at the test environment before moving forward through the pipeline. This helps reduce the degree of uncertainty in the deployable image as it goes through each environment, since even rebuilding an application from source code can introduce behavior changes due to different build machine configuration, or accidental package dependencies updates.

System Downtime

From the application user’s perspective deployment should happen seamlessly, without any sudden interruptions or problems. Any amount of downtime can result in loss of confidence in the application and even lead to financial implications. With this in mind, as a second rule, you should:

Update systems without downtime

If you’re adopting container images in your deployment process this becomes a lot easier, since it’s possible to allocate application services containers without much effort, having the new version and old version available side by side, and then switch networking traffic to the new version:

containers-bridge

From here there are two approaches:

  • Hard switch: You simply flip the switch, disconnecting the old version from the network and exposing the entirety of your users to the new version.
  • Canary release: A small set of users is initially exposed to the new version (ex: 5%), and as you become more confident that this version is stable, you gradually increase the percentage of users routed to the new version until reaching 100%.

Canary release is better for mitigating deployment risks, but usually requires more work to set up. Either way, once the new version container is online and healthy, the old version container can be safely removed from the host.

Automated Execution

We humans are prone to error. The more a deployment process rely on manual steps, the riskier it gets. A simple honest mistake in one manual step can be sufficient to bring your application down. For instance, someone could mistakenly apply staging configuration to the production environment, or inadvertently revert the order in which dependable services are deployed, causing them to crash.

Therefore, as a third rule, you should:

Fully automate the deployment process

It shouldn’t take you more than one click to deploy your application. More sophisticated applications even employ continuous deployment, in which a single commit to the main repository’s master branch is enough to trigger an automated deployment to production. However, these applications rely deeply on automation for testing, canary releasing and monitoring.

Monitoring

The main goal of monitoring is to automatically detect problems as soon as possible when they occur, so we can fix them as quickly as possible. Ideally it should be comprehensive enough that we never feel the need to check something manually. Instead, we rely on system administrators being automatically notified when a problem is detected.

Then, as a fourth rule you should:

Set up and rely on automatic monitoring for early problem detection

There are at least two lines of monitoring which are effective for closing the feedback loop in the deployment process: health monitoring and error monitoring.

Health Monitoring

In this line of monitoring we are interested in assuring that our application is performing as expected. First we define a set of system and business metrics that adequately represents the application behaviors. Then we start tracking these metrics, triggering an alert whenever one of them falls outside of its expected operational range.

A few examples of system metrics are:

  • Number of active database connections
  • Web server requests per second
  • Available memory per host machine
  • IOPS per host machine

As for business metrics, a few examples are:

  • User registration rate
  • Number of online users
  • Image upload rate (for media sharing application)
  • Content like rate (for a social application)

Error Monitoring

Errors are continuously occurring in applications, but most of them are known and expected errors, such as authentication token expiration errors, or database query timeout errors. In this line of monitoring we are interested in discovering deviations, or anomalies, from the expected occurrence of application errors, triggering an alert when that happens. An anomaly can be identified as:

  • A significant and unexpected increase (or decrease) in the rate of a known error
  • A consistent manifestation of a new, unexpected, type of error

Monitoring is valuable not only during deployment, but also long after it’s been completed. The faster we are able to identify and solve issues, the less users will be negatively affected by them.

Reversibility

Sooner or later, no matter what, deployment problems will happen, it’s a fact, and if you’re not prepared to handle them quickly, then you’re taking high risks in doing so, depending on good odds favoring you.

As we’ve learned in the previous section monitoring should give us enough information to detect and evaluate problems as they happen. Problems can be manageable, meaning that we can act on them while they’re occurring in the production environment, or they can be showstoppers, meaning that we will need to solve them immediately, bringing the production environment back to a stable state.

Fortunately there’s a straightforward way for dealing with the latter case: reverting the application back to its earlier, stable version. Then, as a fifth rule you should:

Support rollback to earlier application versions

From figure 1 this can be as simple as flipping the switch back to the original container for all hosts, but this only handles the case when there’s a need to revert to the immediately previous version. You’ll have to keep a deployable image rollout history for being able to execute a rollback deployment reverting your application to older versions.

There is a special case to be careful though. As the application evolves, so does the database schema and stored data. If you design the database to evolve while preserving backwards compatibility with earlier application versions, you should be fine. But sometimes this may not possible and we are required to release a version with breaking changes to the database. A strategy to handle this scenario is to incorporate migration scripts to the deployment, one for committing changes to the database, and one for reverting them.


This article is intended to provide guidelines and best practices for helping to reduce risks associated with the deployment process. It takes reasonable effort and time to achieve a matured and reliable deployment process that works for your application, so don’t feel rushed to build a full fledged process right from scratch, but commit yourself to gradually and constantly improve it.

Jul 28, 2019 - Using queues to offload Web API

With the ubiquitous of smartphones and mobile devices a great number of people are getting more and more accustomed to accessing all kinds of digital services remotely, anywhere they feel convenient to do so. The adoption of web APIs to back these digital services is now even more customary, and the performance of web APIs will have a direct impact on user experience (UX).

This article presents a technique for optimizing web APIs by offloading part of its operations to asynchronous queues, resulting in faster response times and improved UX. First we analyze the anatomy of a web API request, then we introduce the structure of a queuing system, and finally we combine both for achieving more efficient execution flows.

Anatomy of a Web API Request

A great deal of backend services are composed of a web API module on top of a database. In this model code is only executed on demand, i.e., whenever the API gets called. There are no background processes executing behind the scenes. It is simple to develop and operations are predictable, easy to follow.

This model can be pushed really far, as long as the API constraints itself to light weight operations with simple interactions. However, if there’s a need to implement more complex and demanding operations sticking to this model will result in longer processing times and degraded performance. The diagrams below helps understand why:

light-web-request

In light weight web API requests calls arrive at the endpoint, are routed to the application, business logic is executed, perhaps fetching or persisting some data, and finally a response is produced and returned to the client. Operations are mostly short in duration and everything runs within the application boundaries.

heavy-web-request

In more complex web API requests a lot more is going on. Secondary web requests may be triggered in response to the primary request, multiple database queries may be required for processing data and more sophisticated algorithms may be executed in the request main thread. As the diagram shows, these operations will last longer and are not limited to the application boundaries.

Naturally, as operations grow in complexity comes the need for an improved application architecture for orchestrating execution flows and preserving general web API consistency.

The Queuing System

A typical queuing system is composed of a message broker program which provides a publisher/subscriber interface for interacting with named message queues. A message queue is a store of published messages, which are consumed in sequential or prioritized order by one or more subscribers. The message broker provides numerous configuration options for handling messages, including:

  • Durability: messages may be stored in memory, written to disk, or committed to a database depending on reliability requirements
  • Routing policies: in scenarios with multiple message brokers these policies define which servers to publish/subscribe messages
  • Message filtering: specific criteria may be applied to determine which messages are available to individual subscribers
  • Purging policies: messages may have an expiration, after which they are automatically purged
  • Acknowledgement notification: the broker may wait an acknowledgement from the subscriber before committing a message queue removal

message-broker

Message queues are a great solution for orchestrating asynchronous communications. In the image above we have three publishers connected to the broker, publishing messages to three different queues. On the other end four subscribers are also connected to the broker consuming messages from these queues. Routing is flexible and performed internally by the broker.

This example is only illustrative, and depending on application requirements we can have several types of relationships between publisher-queue-subscriber. Typically for small scale systems we will see multiple publishers submitting messages to a queue which has a single subscriber consuming it. For larger distributed systems it’s common to have multiple subscribers consuming from the same queue, each one of them potentially running in a different server for higher performance and availability.

Improving Execution Flow

Let’s suppose the sequence diagram from figure 2 represents a social media content “like” operation as follows:

  1. Mobile App sends a Like request providing authenticationToken and contentId parameters
  2. Web API receives the request, parses the parameters and validates the authenticationToken against the Database
  3. Upon successful validation it proceeds to persist a LikeAction entry into the Database, associating it with contentId
  4. Then it fetches information about the content author, and prepares a push notification request
  5. The push notification request is sent to an external cloud notification service for processing
  6. Upon receiving a confirmation from the external service the Web API returns a success response to the Mobile App

Notice that steps 3-6 are great candidates for being processed asynchronously, based on a few observations:

  • The mobile app response is not dependent on the result of these operations
  • A background worker executing these steps can handle execution errors independently

With that in mind we can introduce a Broker and a Worker components to the aplication, breaking the web API request execution flow into a shorter operation and a subsequent asynchronous operation. The original request will be reduced to:

  1. Mobile App sends a Like request providing authenticationToken and contentId parameters
  2. Web API receives the request, parses the parameters and validates the authenticationToken against the Database
  3. Upon successful validation it proceeds to publish a LikeAction message to the Broker
  4. Upon receiving a confirmation from the Broker the Web API returns a success response to the Mobile App

The third step above enqueues a message into the queue, which will eventually trigger the following asynchronous operation:

  1. The Broker delivers a LikeAction message to the Worker, which is subscribed to this queue
  2. The Worker persists a LikeAction entry into the Database, associating it with contentId
  3. Then it fetches information about the content author, and prepares a push notification request
  4. The push notification request is sent to an external cloud notification service for processing
  5. Upon receiving a confirmation from the external service the Worker completes processing the queue message, and stops

The resulting operation is presented below:

queue-sequence

Notice that the main web API request duration is now much shorter. One can argue that this technique should be incorporated to the system design since its conception, and applied systematically whenever the conditions above are met, resulting in a more efficient web API and more granular, independent code.


Bonus tip: Besides offloading web API requests, the usage of a queuing system also allows the distribution of CPU usage over time, reducing processing spikes and improving system stability. It’s easy to see why: message queues can handle operations sequentially that would otherwise be processed immediately, potentially at the same time.