My Experience Interning at Amazon

Non-Relational Databases

On the non-relational side, options like DynamoDB and MongoDB are popular. These databases store data in flexible formats like JSON, which is great for flexibility because the objects don't need to have a predefined structure. However, this flexibility comes at a cost. Complex searches are difficult because DynamoDB, for example, operates essentially as a key-value store. It allows reads, writes, and updates by opportunity ID but doesn’t support advanced searching. MongoDB offers slightly more advanced searching capabilities, but its limited number of indexes means complex queries are still restricted. For our team's use cases, these non-relational options weren’t sufficient.

Relational Databases

Relational databases, such as MySQL, PostgreSQL, Oracle, and IBM Db2, store data in tables with rows and columns. The objects are mapped to rows, and relationships can be created between different tables. While relational databases excel in handling structured data and complex queries, they do have some drawbacks. The rigid schema requires every object to be mapped to a row, and fields that aren't used in every data object are often set to null. Additionally, traditional relational databases have historically had storage limitations. However, cloud services like AWS have significantly increased these limits. For example, Amazon Aurora can handle up to 128 TB of data, which is far more than our team's current storage needs of less than 1 TB.

Relational databases also excel in transactional processing (OLTP), which is crucial for operations that involve frequent updates, inserts, and searches. By creating indexes on various fields, relational databases can support efficient searches, including those needed for filtering opportunities by vendor managers. The downside is that creating too many indexes can increase storage costs and slightly slow down query times. I also found some differences between relational database engines. For example, PostgreSQL uses immutable rows, meaning that every update to a row creates a new version, and every associated index must be updated to point to the new row. This approach, while beneficial for concurrency and versioning, adds overhead. On the other hand, MySQL allows in-place updates, which are more efficient because the row is modified directly without the need for creating a new one or updating associated indexes. Though MySQL's in-place update approach is more efficient, my team ultimately did not choose MySQL. We selected PostgreSQL instead, as it supports more complex features, such as indexing JSON data, which was critical for transitioning from DynamoDB.

Analytical Engines

On the analytical engine side, online analytical processing (OLAP) tools like Elasticsearch, RedShift, and Trino offer powerful search and aggregation capabilities. These engines are built on top of other storage systems, such as DynamoDB, PostgreSQL, or AWS S3. They can handle complex searching, aggregation, and calculations but are much more compute- and storage-intensive than traditional databases. These engines also don’t support transactional processing, so write operations, such as inserts and updates, require a separate data storage solution. Furthermore, the time for these engines to reflect updates can be several hours, making them unsuitable for our project needs.

Analyzing the Existing DynamoDB Workload

To begin with, I examined our existing DynamoDB databases. These databases contained approximately 30 million opportunities, each supporting sub-20 millisecond latency for insert, update, and read operations. This gave me a benchmark for performance, and I used it as a reference point when designing the PostgreSQL performance tests.

Designing the PostgreSQL Schema

The next step was to decide on the schema and structure of the PostgreSQL tables. I needed to define the number of columns, field types, indexes, and other design details. I aimed to populate these PostgreSQL tables with roughly 30 million opportunities to replicate the existing workload.

Initially, I tried to design the schema to closely mirror the structure of the data in DynamoDB. In DynamoDB, the opportunities were stored as JSON objects, with each object broken down into sub-objects representing various parts of the opportunity. Based on this, I created an opportunity table in PostgreSQL with a superset of all the fields across all opportunities. I also represented the sub-objects as custom PostgreSQL composite types.

Challenges with the Initial Schema Design

This initial schema resulted in a unique database structure, involving arrays of composite types. However, I encountered some limitations, especially when I attempted to index nearly every field. For instance, I discovered that indexing on fields within composite types stored in arrays was not possible.

Research and Re-evaluation of the Schema

To resolve these issues, I conducted further research to explore alternative approaches. During my search, I came across the concept of database normalization, which organizes data into multiple tables and creates relationships between them. This technique allows you to break down complex data structures into simpler components, making them easier to manage and index.

Normalization and Improved Database Efficiency

I realized that my initial schema design was highly inefficient and not recommended. With the principles of database normalization in mind, I restructured the schema by separating the composite types from the main opportunity table. I created two tables: one for the main opportunity data and another for the composite types, which were previously stored in arrays. By associating each composite type with a corresponding row in the main table, I could now index these composite types, significantly improving the efficiency of searches for matching opportunities.

This normalization approach not only optimized database performance but also increased flexibility for potential future schema changes. It was a valuable learning experience, and the revised schema has allowed for better performance, reliability, and scalability in Aurora PostgreSQL.

Populating the Database with 30 Million Opportunities

The next challenge was populating the PostgreSQL database with 30 million opportunities. Initially, I considered using real opportunities from our existing DynamoDB database. However, this would require reading from DynamoDB, deserializing the data, and then writing it to PostgreSQL. The deserialization process was slowing me down, so my teammate suggested using fake data since the performance test didn't require the actual data. I decided to take their advice and began using fake data.

Performance Issues on Local Machine

I started by running a Python script on my local computer to populate the database. However, my computer could only insert about 1 million fake opportunities per hour. I attempted to run the script overnight and over the weekend, but my machine frequently timed out, losing connection to the database. As a result, several days passed with minimal progress.

Leveraging EC2 for Better Performance

Eventually, I realized that using an EC2 instance with more computing power and uninterrupted runtime could significantly speed up the process. I set up an EC2 instance, and the difference was remarkable. The performance was drastically better compared to my local machine. I was able to run 400 workers in parallel, allowing me to populate 30 million fake opportunities in nearly an hour instead of the 30 hours it would have taken on my local machine.

Setting Up the Tests

With the fake data successfully populated in the database, I proceeded to write Python scripts for the three tests I planned to run. The first script simulated simple inserts, gets, and updates by opportunity ID, mimicking the existing workload in DynamoDB. The second script tested more complex operations, such as filtering and aggregation, to support use cases like Project 1, which involved using opportunity filters to find matching opportunities. The third test aimed to simulate deadlock scenarios, simply to observe how the system handled them.

Running the Tests

I ran each test with several readers and writers operating in parallel, as well as with dozens of readers and writers in high-concurrency scenarios. This allowed me to compare how the system performed under low and high concurrency conditions. To analyze the results, I used AWS Performance Insights. This tool provided valuable data, including the load on the database CPU, write latency, read latency, read and write I/O operations per second, number of connections to the database, deadlocks, rolled-back transactions, cache rate, and much more.

Promising Results

The test results were extremely promising. In fact, they were even a bit too good to be true. Writes and read latency were consistently under a millisecond—faster than DynamoDB. The cache hit rate was 100%, and no deadlocks occurred. These results indicated that the PostgreSQL database was performing exceptionally well under the test conditions.

Addressing Concerns with Data Generation and Randomness

After sharing the initial performance results with my team, everyone was pleased, but one teammate raised a valid concern. He questioned the high cache hit rate and pointed out that the fake data I was generating might not be random enough, leading to a limited number of unique opportunities. I reviewed my approach and discovered that the Python library I was using, Faker, generated fake data by selecting values from a limited set—like names from a list of only 100 options.

To improve the randomness of my data, I decided to generate it manually using combinations of strings concatenated with random numbers. I used my teammate’s knowledge of our actual dataset, such as the number of unique brand codes, to guide the random number range and better align the fake data with the characteristics of the real data. This update helped ensure that the data more closely resembled the variety we would expect in production.

Solving the Random Seed Issue for Parallel Workers

While making this change, I realized another issue with my parallel workers. Previously, all workers were using the same random seed, which resulted in them generating identical "random" data. I switched to Python’s random library, which made it more apparent that I needed to assign a unique random seed to each worker. This ensured that each worker would generate different data, preventing any overlap and increasing the variability of the generated opportunities.

Deadlock Testing: Adjusting Worker Behavior

Next, I revisited my deadlock test, where parallel workers were updating and reading from two opportunities. Initially, all workers were updating opportunity ID A before ID B. This meant they were waiting to acquire locks in the same order, preventing deadlocks from occurring. To create a real deadlock scenario, I adjusted the worker behavior so that some workers acquired A’s lock first while others acquired B’s lock first. This change led to a true deadlock situation, where workers would hold one lock and wait for the other worker to release the second lock, causing a deadlock.

Once I implemented this change, deadlocks appeared instantly during the tests. I learned that when a deadlock occurs, PostgreSQL rolls back the affected transactions, forcing one worker to abort their operations. This was a key insight for improving the accuracy of my tests.

Re-evaluating Latency Measurements

The sub-millisecond latency I had seen in AWS Performance Insights seemed too good to be true, so I dug deeper into the latency metrics. Upon reviewing the information, I found that AWS was reporting the latency per I/O operation, not the total latency per query. An I/O operation is a single interaction with a page of memory on the disk, and each SQL query could involve hundreds or thousands of I/O operations. To get a more accurate picture of the latency, I decided to measure the query latency directly from the script itself, rather than relying on AWS Performance Insights. Although this measurement included network delay, it provided a more realistic view of the user experience, especially from the perspective of a frontend user interacting with the database.

Running the Updated Performance Tests

With the updates in place, I ran all three performance tests again. This time, the results showed a much more realistic latency range. For updates, reads, and inserts by ID, the operations took between half a second and a second and a half 99% of the time—much higher than the sub-millisecond latency I had originally seen. The complex reads and filtering queries performed similarly, which was a promising result. However, for aggregation queries, the latency could reach up to 8 seconds, which was unacceptable for our use case.

Optimizing Aggregate Queries

To address the issue with aggregate queries, I explored potential solutions. Despite experimenting with additional indexing and restructuring SQL queries, performance remained unsatisfactory. I then came across a recommendation to create an additional aggregate table that stored vendor companies and the total amount of money Amazon could make from negotiations with them. I implemented this by adding PostgreSQL trigger functions that updated the aggregate table every time an opportunity was inserted, updated, or deleted. This optimization resulted in sub-second response times for the main aggregate query we needed to support.

Final Thoughts on Deadlocks and Realistic Patterns

Finally, my team and I discussed the possibility of deadlocks in production. While we had successfully forced deadlocks during testing, we concluded that, in reality, our read and update patterns would not trigger deadlocks under normal circumstances. Therefore, while deadlocks are possible, they were unlikely to occur in our actual workload.