Booking Deduplication: How Agoda Manages Duplicate Bookings Across Multiple Data Centers (Part 1)
At Agoda, we faced a significant issue with unwanted bookings being accidentally created each day, primarily due to system incidents. Often, delays in the booking creation process led customers to rebook when they did not receive a confirmation email or see their booking on the Agoda website or app. This resulted in multiple duplicate bookings despite the customers’ intention to make only one. Consequently, they contacted customer service to cancel the unwanted bookings, requiring Agoda to issue refunds and absorb the cancellation costs. To mitigate this financial loss, Agoda introduced the booking deduplication feature many years ago to prevent the creation of duplicate bookings.
How Does Booking Deduplication Appear to Customers
When a customer makes a booking, they receive a Booking ID in return.
If the customer attempts to make another identical booking, the booking deduplication service detects the existing booking in Agoda’s system. It then pauses the second booking request and displays a pop-up asking, “Is this a duplicate booking?” to confirm the customer’s intent.
Challenges
As Agoda continued to grow rapidly, multiple data centers (DCs) were established to support scaling operations. A new challenge emerged when we needed to transfer traffic from one data center to another during incidents. The legacy booking deduplication system could not detect duplicates as it was designed to function locally.
Additionally, we expanded our business by offering more products, such as flight tickets, car rentals, and activities at customers’ destinations. Each product has its own criteria and logic for detecting duplicate bookings. For example, hotel bookings are compared based on hotel IDs, while flight bookings are compared based on flight numbers. This necessitated maintaining multiple booking deduplication services tailored to a specific product.
Beyond these business challenges, a common technical issue was also addressed: Every day, front-end clients send duplicate API requests to backend APIs.
This article explains how we addressed these challenges by leveraging our infrastructure, which traditionally relies on SQL servers to improve our booking deduplication processes.
Multi-Product Booking Deduplication in Agoda’s Multi-Data Centers
Multi-Data Centers: In the legacy booking deduplication system, the service worked only locally because it relied on data created in a specific data center. Each DC was unaware of data created in other DCs. When traffic was shifted from one DC to another, the deduplication service in the new DC failed to function correctly due to the lack of data from the original DC. To resolve this, one DC was designated as the central DC, housing data from all other DCs. The booking deduplication feature was then enhanced to utilize this centralized data, allowing it to function correctly even with traffic movement across multiple data centers.
Redundancy: With centralized data in the central DC, redundancy was achieved by enhancing the service to query data from both the central and local DCs.
Simplicity: To unify the booking deduplication feature across all Agoda products, we adopted data hashing. Instead of using different data for different products, all product data is hashed and stored in a single table. This approach ensures the deduplication feature functions seamlessly, regardless of product type.
Scalability: Under the legacy booking deduplication system, launching a new product at Agoda required creating a new service to handle data from product-specific tables. The new multi-product booking deduplication system uses a single service to consume data from one unified table for all products. This makes adding new products seamless.
Time-Sensitive Use Cases: By leveraging the unique key constraint feature and isolation level settings in SQL databases, we address the common issue of duplicate API requests in BackEnd APIs, particularly within a one-second interval.
New Architecture
The diagram above illustrates how the booking deduplication service fetches data from both local and central databases, combines the results, and processes the data to determine if a customer request is a duplicate booking.
The local database contains data created in that specific local data center, while the central database holds data from all DCs. By using centralized data from the central database, the booking deduplication service continues to function correctly even when traffic is shifted between data centers. In contrast, the legacy booking deduplication system, which only consumed data from the local database, failed to detect duplicate bookings properly when traffic was moved.
To ensure redundancy, the booking deduplication service retrieves data from local and central databases. This approach addresses potential data gaps and mismatches caused by database failures. For instance, if the local database experiences downtime and cannot record new entries, the data generated during this period will still be available in the central database. By merging results from both databases, the service maintains data integrity, even if the local database is missing information. Additionally, queries to both the local and central databases are executed in parallel to minimize the increase in service latency.
Different Products, Different Logic
As previously mentioned, each product type has its own booking deduplication logic because different products have distinct datasets stored in separate physical tables. Below are sample tables illustrating the booking data required for deduplication logic for each product type.
We need to verify whether a booking request will result in a duplicate entry to prevent duplicate bookings. For each product type, the booking deduplication service extracts the booking context from the request and checks the database for matches. If an existing booking matches the extracted context, the request is identified as a duplicate.
For static data such as property ID, room type ID, flight number, and guest names, an exact match is required. However, some fields require dynamic comparison; for example, date and time fields are compared based on overlapping date ranges.
One Table for All
A new table dedicated to this feature has been created in both the local and central databases. This table is designed to be generic, allowing it to accommodate any type of product that Agoda currently sells or may sell in the future.
For each newly created booking, the necessary data for booking deduplication logic is inserted into this new table as a candidate. The data is divided into two parts for static and dynamic comparisons.
Static comparison data is hashed and stored in the candidate_hash column. For the purpose of hashing, an unkeyed cryptographic hashing function, SHA-256, was selected. SHA-256 was selected due to its high collision resistance and deterministic nature, ensuring data integrity. The hash function produces the same output for identical inputs, with significant changes for any minor input variations.
In the legacy design, the service compared booking data field by field, involving around ten fields. By using hash values, we can consolidate these fields into a single hashed data field, allowing the service to compare just this one field. This approach also means that adding or removing data fields for static comparison does not require modifying table columns.
Moreover, SHA-256 returns fixed-length hash values, enabling stable and nearly constant-time performance for data access. Since SHA-256 is a one-way function, it is secure for exact matching in static comparisons; the service does not need to retrieve or process the actual data values, making retrieving raw booking data unnecessary.
For data used in dynamic comparisons, the service needs to process the data later, so it is stored as raw data. This raw data is kept as a JSON-formatted string in the candidate_json column. JSON format was chosen because it can contain multiple data fields and supports nested structures. Adding or removing data fields is hassle-free and doesn’t require new table columns. Data consumers can easily deserialize a JSON string back to an object and operate on it, and data writers can do the reverse. JSON is also readable, which helps during issue investigations as we can read the data directly or use it in code debugging or automation tests. In manual testing, developers can easily modify or insert JSON data in databases to simulate test scenarios.
The status of each record, the candidate_status column, is updated during the booking creation process. When a new booking is successfully created, the booking creation service inserts a record into the dbo.duplication_candidates table with candidate_status set to Active. If the booking is later canceled, the candidate’s status is updated to Inactive. For bookings awaiting customer payment, the candidate_status is temporarily set to Awaiting.
This design is generic for any product type and highly scalable. Unlike the legacy design, where each product had its specific tables, introducing a new product type required new physical tables. Adding or removing fields for the booking deduplication service involved adding or removing table columns. A new booking deduplication service would also need to be created specifically for the new product to consume the product-specific tables. With this new unified table, introducing a new product type requires minimal effort.
Booking Creation Process
When Agoda receives a booking request from a customer, the Booking Deduplication Service checks if the request is a duplicate. If it is, Agoda rejects the request with a pop-up asking, “Is this a duplicate booking?” If it is not, Agoda proceeds with the request. If the booking is created successfully, Agoda returns a Booking ID to the customer and inserts the new booking into the local and central databases, making it a new candidate for future booking deduplication.
However, booking creation may fail for various reasons, such as payment failure or unavailable allotment. In such cases, Agoda rejects the request and displays an error message to inform the customer that the booking was not created successfully.
Zoom In on Booking Deduplication Service
The Booking Deduplication Service consists of four main steps, which are the same for all kinds of products:
- Retrieve duplication candidates from both local and central databases and combine the results.
- Filter out the candidates by status.
- Filter out the candidates using additional product-specific logic.
- Reach a conclusion.
Step 1: Retrieve Duplication Candidates from Both Local and Central Databases and Combine the Results
This step consists of two sub-steps:
1.1 Retrieve Duplication Candidates from Both Local and Central Databases
The Booking Deduplication Service extracts booking context from the Make-a-Booking request based on the product type and generates a list of booking hashes. The service then calls stored procedures in both local and central databases to query the dbo.duplication_candidates table. Each database returns a list of duplicate candidates for the service.
1.2 Combine the results from the two databases
Two databases are used for redundancy purposes but can also lead to data mismatches between the two sources. This section explains possible scenarios and how they are handled when combining the results.
Case #1: The results from both local and central databases are matched.
This indicates that the results are accurate and reliable.
Case #2: When the Service Retrieves a Candidate from Only One Database
When the service gets a candidate from only one database, it will trust the result that has more data.
This situation can arise from two possible scenarios:
- One Database was down while writing the candidate: When a booking is successfully created, the booking creation process attempts to insert the new booking into the candidates table on both databases. If one of the databases is down, the insertion fails, and the candidate is missing from the affected database. Later, when the broken database is back to normal, the booking deduplication service queries both databases. The previously broken database will not return the candidate due to the missing data. However, the service can still retrieve the candidate from the always-healthy database.
- One database was down while reading the candidates’ table: After receiving a booking request, the booking deduplication service made stored procedure calls to query the candidates’ table on both databases. For example, if one database is down due to a connection issue, the service only receives results from the healthy database.
Case #3: When the service retrieves mismatched candidates from Both Databases
If the service retrieves a candidate from both databases but the results are mismatched, it combines the results by applying a priority order of candidate statuses: Inactive > Active > Awaiting.
During the combination process, if the service notices that for a given candidate, the statuses from the two databases are not equal. The service will trust the record with the higher priority status according to the defined order.
This situation can occur when a booking is created and successfully inserted into the candidates table in both databases. Later, the booking is canceled, and the cancellation service attempts to update the candidate’s status to inactive in both databases. However, if one database is down during the update, the candidate record in that database is not updated.
When the broken database is restored, and the booking deduplication service queries both databases, the always-healthy database returns the candidate with inactive status, while the previously broken database returns the candidate with active status. The service will then trust the inactive status due to its higher priority.
Case #4: Handling Multiple Candidates Due to Hash Collision
When the service encounters multiple candidates for one booking hash due to a hash collision, it retains all candidates at this step. Candidates not identified as duplicate bookings will be filtered out later in Step 3, which involves filtering out candidates based on additional product-specific logic.
Case #5: Hash Collision Combined with a Missing Candidate
When multiple candidates arise from a hash collision (Case #4) and one candidate is missing from one database due to a failure (Case #2), the service handles it by first retaining all candidates, as in Case #4, and then trusting the result with more candidates as per (Case #2).
Case #6: Hash Collision Combined with Mismatched Data
When multiple candidates result from a hash collision (Case #4) and one candidate has mismatched data due to a database failure (Case #3), the service applies the approach from Case #4 by keeping all candidates and then resolves the mismatch by applying the priority order of candidate statuses: Inactive > Active > Awaiting, as in Case #3.
Case #7: Hash Collision, Missing Data, and Mismatched Data
When multiple candidates arise from a hash collision (Case #4), and one candidate is missing from one database due to a failure (Case #2), another candidate has mismatched data due to a failure (Case #3), the service will apply the same approaches in Case #4, Case #2 and Case #3 respectively.
Step 2: Filter Out Candidates by Status
After retrieving a list of duplication candidates from the first step, candidates with the status of inactive or awaiting are filtered out.
This status filtering is deliberately kept out of the stored procedure for several reasons:
- Simplicity: To keep the stored procedure simple with only one SELECT statement.
- Visibility and Debugging: Maintaining logic in the application layer makes it more visible and easier to debug.
- Data Accuracy and Reliability: Returning all applicable records from the redundant databases ensures confidence in data accuracy and reliability, allowing the application to handle any potential data mismatches.
Step 3: Filter Out Candidates by Additional Product-Specific Logic
In this step, the service performs further filtration by processing the JSON data part. (We continue using the property product type as an example). The candidate_json field of each candidate is deserialized into a PropertyBookingData object. The service then filters out candidates by performing dynamic comparisons on these objects.
One example of dynamic comparison is comparing date and time fields by overlapping date ranges. Different product types have different ways of overlapping date ranges and applying them to different DateTime fields. For instance, the overlapping range for the property product type is seven days on the check-in date and time, whereas for the flight product type, it is three days on the departure date and time.
As mentioned earlier, in cases of hash collisions, this step’s filtration will intrinsically filter out any candidates not identified as duplicates. Here are some sample cases illustrating this process. In reality, there are more additional product-specific logics in this step.
Case #1: When the service gets two candidates for one booking hash due to a hash collision. One candidate is a property product booking with a candidate_json field containing a JSON string of the PropertyBookingData model. The other candidate is a flight product booking with a candidate_json field containing a JSON string of the FlightBookingData model. If the service is processing a make-a-booking request for a property product type, it will filter out the latter candidate, which does not have a JSON string of the PropertyBookingData model.
Case #2: When the service gets two candidates for one booking hash due to a hash collision, and both are property product bookings. The check-in date of one candidate is in June, while the other is in December. If the service is processing a make-a-booking request with a check-in date in June, it will filter out the candidate with a check-in date in December after comparing date and time fields by overlapping date ranges.
Step 4: Reach a Conclusion
In this final step, the Booking Deduplication Service determines whether the request is a duplicate booking. The service examines the candidates list after all previous filtration steps. If the list is empty, the request is not a duplicate booking. If there are still duplication candidates in the list, the request is concluded to be a duplicate booking.
In the next part of this article, you will learn about serving latency-sensitive cases, further development, and applications of the deduplication system.
