Design a Hotel Reservation System like Expedia & Kayak

Source from:

1. High Level Features

• User Browses through rooms available for given dates range.
• User reserves a type of room in a oarticular hotel.
• One check-in, hotel manager assigns a room of that type to the user.

2. Performance Consideratiosn

• When does WRITE happen?
  • User reserves a room
  • User cancels a reservation
  • New hotel or room added
• When does READ happen?
  • Browsing through hotel catalog
  • Browsing through hotel features.

So a significantly higher amount of READ than WRITE.

3. API

Generic CRUD endpoints for hotel and room management, Let's ignore them.

Reservation

• GET /reservations

• GET /reservations/123

• POST /reservations

• DELETE /reservations/123

4. Data Model

Let's go with a relational database like MySQL or PostgreSQL. Why?

• Easier to model hotel and reservation data
• More READ than WRITE
• Mostly CRUD operations
• ACID properties, transactional guarantees
• Easier locking mechanisms
• Data can be easily sharded for scalability

Hotel Table

Room Table

Room Type Inventory(庫存) Table

Rate Table (費率表)

是酒店預訂系統中的一個重要組成部分，用於確定客房的價格和費用。它是一個表格或數據結構，將客房的不同因素（例如日期、房型、入住人數、套餐選項等）與相應的價格和費用進行關聯。

Reservation Table

Guest Table

5. What happens when user wants to reserve?

• Check the "Room Type Inventory" table for availability
• If not available:
  • Don't reserve. Throw error.
• If available:
  • Update inventory
  • Create reservation
  • Both should be done in the same transaction

6. How to avoid double booking by the same user?

Let's say the user clicked "Book" twice in very quick succession. How do we avoid booking twice?

Use an idempotency key /ˌaɪ.demˈpoʊ.t̬ənt/

Idempotency key（冪等鍵）是在網絡請求中使用的一種機制，用於確保請求的冪等性。冪等性是指對同一操作進行多次請求所產生的結果與對該操作進行一次請求所產生的結果相同。 在分佈式系統中，由於網絡問題、重試機製或其他原因，請求可能會被重複發送。這可能導致重複的操作，從而引發數據一致性問題或產生不正確的結果。為了避免這種情況，可以使用冪等性和冪等鍵來確保請求的冪等性。 冪等鍵是一個唯一標識符，用於標識特定請求的唯一性。當一個請求發送到服務器時，服務器會檢查該請求是否包含冪等鍵。如果服務器已經處理過具有相同冪等鍵的請求，它將忽略重複的請求，並返回之前處理過的結果，而不會執行重複的操作。 通過在每個請求中包含唯一的冪等鍵，可以確保即使請求被重複發送，服務器也能正確處理並保持數據的一致性。冪等鍵通常在請求的頭部或參數中傳遞，並且在每個請求中都應該是唯一的。 使用冪等鍵是一種常見的做法，特別是在涉及敏感操作或對數據狀態具有重要影響的操作中，例如支付、訂單處理等。通過使用冪等鍵，可以提高系統的可靠性和穩定性，並減少重複操作所帶來的不必要的副作用。

idempotent elements are the functions f: E → E […] such that for all x in E, f(f(x)) = f(x) idempotency 性質可以詮釋成：

• f：可以是 function 或是 API endpoint。
• x：可以是 argument 或是 API header & payload。
• 如果 f 是 idempotent，就代表：對 f(x) 執行 1 次產生的效果，與執行 N 次產生的效果，完全一樣。

Steps:

• When user lands in final checkout page
  • Backend generates a unique key (reservation_id)
  • Sends the key to the client
  • Client sends the key to the API when reserving
  • If user clicks twice:
    • Same key goes to the backend
    • Backend knows a reservation with that key has already been created
    • So Backend throws away the request

7. How to avoid multiple users reserving the same room?

1. 房間可用性跟踪：在系統中實時維護可用客房的清單。當用戶發起預訂請求時，檢查所請求日期的客房可用性。如果客房已經被預訂或不可用，通知用戶並提供替代選擇。
2. 預訂鎖定：實施鎖定機制，防止多個用戶同時預訂同一間客房。當用戶開始預訂過程時，臨時鎖定客房以保留給該用戶。在此鎖定期間，其他用戶無法預訂同一間客房。如果預訂成功完成，釋放鎖定；否則，如果預訂被取消或過期，也要釋放鎖定。
3. 原子操作：確保預訂客房的過程是一個原子操作，以維護數據一致性。使用數據庫提供的事務機製或實施自定義鎖定機制，確保預訂過程作為單個不可分割的單元執行。這有助於防止多個用戶同時嘗試預訂同一間客房的競爭條件。
4. 超時和過期：為預訂鎖定實施超時機制，處理用戶在未完成預訂的情況下放棄預訂過程的情況。如果用戶發起預訂但未在一定時間內完成，釋放鎖定，使客房再次可用於其他用戶。
5. 同步：在訪問與客房預訂相關的共享數據或資源時，使用適當的同步機制。確保對與預訂相關的數據的並發訪問得到正確的同步，以防止衝突和數據不一致。
6. 用戶通知：實時向用戶提供有關其預訂請求狀態的通知。如果由於不可用性或與其他用戶預訂衝突而無法完成預訂，立即提供反饋。這使用戶能夠及時選擇替代客房或日期。

Approach 1: Use Locking

• Add a new column version to the tables(room)
• Client reads the version column when reading a row
• When writing, the application increments the version by 1.
• In the meantime, if version has already been incremented by a different client:
  • Database throws an error
  • Operation is rolled back
  • User will have to try again with a different room

可考慮在以下的表中增加version column

1. Room（客房）表：為每個客房記錄添加version column，以便跟踪客房信息的版本。當客房信息更新時，可以通過增加版本號來區分不同的版本。
2. Reservation（預訂）表：在預訂表中添加version column，以記錄預訂信息的版本。當預訂信息發生變化時，可以更新版本號，例如更改入住日期、房型或其他預訂細節。
3. Rate Table（費率表）：對於費率表，您可以在表中添加version column，以記錄費率表的版本。當費率策略發生變化時，可以更新版本號，例如更改價格、促銷信息或套餐選項。

資料列(Row)是指資料表中某些「記錄」，它是以「水平」方式來呈現。 資料行(Column)是指資料表中的某些「欄位」，以「垂直」方式來呈現，其header來畫分數據類型

Approach 2: Database Constraint (If supported)

• Add a databse constraint
• CHECK ( (total_inventory - total_reserved) >= 0 )
• If constraint fails when writing, transaction is rolled back

Database Constraint

數據庫約束（Database Constraint）是在數據庫中定義的規則，用於強制執行數據的完整性和一致性。它們定義了對錶中數據的限制和規範，以確保數據的有效性和正確性。

數據庫約束可以應用於表、列或整個數據庫中的數據，用於控制以下方面：

1. 唯一性（Unique Constraint）：唯一約束確保表中的某個列或一組列的值是唯一的，不允許重複。這可用於避免重複的數據記錄，如要求用戶名、電子郵件地址或身份證號碼等具有唯一性的字段。
2. 主鍵（Primary Key Constraint）：主鍵約束定義了表中一個或多個列的唯一標識符。它們確保表中每一行都具有唯一的標識符，並且不允許為空。主鍵用於唯一地標識表中的記錄，並為其他表之間的關係提供基礎。
3. 外鍵（Foreign Key Constraint）：外鍵約束用於定義表之間的關係。它們確保一個表中的某個列（外鍵）引用另一個表中的主鍵值。外鍵約束可以用於保持數據之間的引用完整性，確保引用的數據在關聯表中存在。
4. 非空（Not Null Constraint）：非空約束要求列中的值不允許為空。它們強制要求在插入或更新數據時提供非空值，以防止數據的不完整性。
5. 默認值（Default Constraint）：默認值約束定義了在未提供具體值時，列應採用的默認值。它們確保在插入數據時，如果未指定列的值，則使用默認值。
6. 檢查約束（Check Constraint）：檢查約束用於定義一組條件，以驗證插入或更新的數據是否符合特定的規則或條件。它們允許對列的值進行自定義驗證，例如範圍檢查、格式檢查等。

通過定義這些數據庫約束，可以在數據庫層面強制執行數據的完整性、一致性和業務規則，以減少無效數據和錯誤的插入或更新操作，並提高數據質量和可靠性。

8. How to scale?

8.1 Database getting too large?

• Nightly batch to remove & archive older rows
• Shard database by hotel_id

8.2 Read is taking too long?

• Move read traffic from database to cache
• For more popular hotels, cache the invetory information
  • Will lead to more user facing errors
  • Inconsistent inventory data between cache and database
• For all hotels, cache static data like features and hotel details

8.3 How can you improve cache data accuracy?

• Database CDC(Change Data Capture) updates Cache
• Whenever inventory changes, cache is invalidated and updated with new inventory

Database CDC (Change Data Capture)

Database CDC（Change Data Capture，變更數據捕獲）是一種技術，用於捕獲和跟踪數據庫中發生的數據變更操作，並將這些變更操作作為事件流或日誌記錄進行持久化和傳輸。

以下是 Database CDC 的工作原理和主要特點：

• 數據變更捕獲：CDC 監視數據庫中的插入、更新和刪除等操作，並捕獲這些變更的詳細信息，例如變更前的值、變更後的值、變更發生的時間等。
• 日誌或事件流：捕獲的數據變更可以以事件流或日誌的形式進行持久化和傳輸。這些事件流或日誌記錄通常以有序的方式呈現，以確保變更的順序和一致性。
• 實時或近實時性：CDC 提供了實時或近實時的數據變更捕獲和傳輸能力。它能夠在變更發生後的短時間內將變更操作發送到訂閱者，以便及時響應變更。
• 數據複製和同步：CDC 可以用於數據複製和同步的場景。通過捕獲數據變更並將其傳輸到其他系統或副本數據庫，可以實現數據的實時或定期復制，以確保數據的一致性和可用性。
• 數據集成和分析：CDC 還可以用於數據集成和分析的目的。通過捕獲和傳輸數據變更，可以將數據庫中的數據與其他系統進行集成，或者用於實時分析和報告生成等任務。
• 低侵入性：CDC 技術通常以低侵入性的方式與數據庫集成，不需要對現有應用程序或數據庫架構進行大規模的更改。

CDC 技術在許多應用場景中非常有用，例如數據複製、數據倉庫、實時分析、事件驅動架構等。它可以幫助實現數據的實時性和一致性，並提供對變更操作的可追溯性和可靠性。

Reference

• [Youtube] Design a Hotel Reservation System like Expedia & Kaya
• PDF
• [Youtube]Airbnb System Design | Booking.com System Design | System Design Interview Question
• Idempotency Key：原理與實測