designing_ticketmaster.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Design E-Ticketing System\n",
    "\n",
    "Let's design an online E-ticketing system that sells movie tickets.\n",
    "\n",
    "A movie ticket booking system provides its customer the ability to purchase theatre seats online. They allows the customer to browse movies currently being played and to book available seats, anywhere anytime."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Requirements and System goals\n",
    "\n",
    "### Functional Requirements\n",
    "- The service should list different cities where its affiliated cinemas are located.\n",
    "- When user selects a city, the service should display movies released in that particular city.\n",
    "- When user selects movie, the service should display the cinemas running the movie plus available show times.\n",
    "- Users should be able to book a show at a cinema and book tickets.\n",
    "- The service should be able to show the user the seating arrangement of the cinema hall. The user should be able to select multiple seats according to the preference.\n",
    "- The user should be able to distinguish between available seats from booked ones.\n",
    "- Users should be able to put a hold on the seat (for 5 minutes) while they make payments.\n",
    "- Users should be able to wait if there is a chance that the seats might become available (When holds by other users expire).\n",
    "- Waiting customers should be serviced in a fair, first come, first serve manner.\n",
    "\n",
    "### Non-Functional Requirements\n",
    "- The service should be highly concurrent. There will be multiple booking requests for the same seat at any particular point in time. \n",
    "- The system has financial transactions, meaning it should be secure and the DB should be ACID compliant.\n",
    "- Assume traffic will spike on popular/much-awaited movie releases and the seats would fill up pretty fast, so the service should be highly scalable and highly available to keep up with the surge in traffic.\n",
    "\n",
    "\n",
    "### Design Considerations\n",
    "1. Assume that our service doesn't require authentication.\n",
    "2. No handling of partial ticket orders. Either users get all the tickets they want or they get nothing.\n",
    "3. Fairness is mandatory.\n",
    "4. To prevent system abuse, restrict users from booking more than 10 seats at a time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Capacity Estimation\n",
    "\n",
    "> **Traffic estimates:** 3 billion monthly page views, sells 10 million tickets a month.\n",
    " \n",
    "> **Storage estimates:**\n",
    "500 cities, on average each city has 10 cinemas, each with 300 seats, 3 shows daily.\n",
    "\n",
    "Let's assume each seat booking needs 50 bytes (IDs, NumberOfSeats, ShowID, MovieID, SeatNumbers, SeatStatus, Timestamp, etc) to store in the DB.\n",
    "We need to store information about movies and cinemas; assume another 50 bytes.\n",
    "\n",
    "So to store all data about all shows of all cinemas of all cities for a day\n",
    "\n",
    "```\n",
    "        500 cities * 10 cinemas * 300 seats * 3 shows * (50 + 50) bytes = 450 MB / day\n",
    "```\n",
    "To store data for 5 years, we'd need around\n",
    "```\n",
    "    450 MB/day * 365 * 5 = 821.25 GB\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. System APIs\n",
    "Let's use REST APIs to expose the functionality of our service.\n",
    "\n",
    "\n",
    "### Searching movies\n",
    "```python\n",
    "search_movies(\n",
    "    api_dev_key: str,      #  The API developer key. This will be used to throttle users \n",
    "                           #  based on their allocated quota.\n",
    "    keyword: str,          # Keyword to search on.\n",
    "    city: str,             # City to filter movies by.\n",
    "    lat_long: str,         # Latitude and longitude to filter by.\n",
    "    radius: int,           # Radius of the area in which we want to search for events.\n",
    "    start_date: datetime,  # Filter with a starting datetime.\n",
    "    end_date: datetime,    # Filter with an ending datetime.\n",
    "    postal_code: int,      # Filter movies by postal code / zipcode.\n",
    "    include_spell_check,   # (Enum: yes or no)\n",
    "    result_per_page: int   # number of results to return per page. Max = 30.\n",
    "    sorting_order: str     # Sorting order of the search result. \n",
    "                           # Allowable values: 'name,asc', 'name,desc', 'date,asc', \n",
    "                           # 'date, desc', 'distance,asc', 'name,date,asc', 'name,date,desc'\n",
    ")\n",
    "\n",
    "```\n",
    "Returns: (JSON)\n",
    "```json\n",
    "[\n",
    "  {\n",
    "    \"MovieID\": 1,\n",
    "    \"ShowID\": 1,\n",
    "    \"Title\": \"Klaus\",\n",
    "    \"Description\": \"Christmas animation about the origin of Santa Claus\",\n",
    "    \"Duration\": 97,\n",
    "    \"Genre\": \"Animation/Comedy\",\n",
    "    \"Language\": \"English\",\n",
    "    \"ReleaseDate\": \"8th Nov. 2019\",\n",
    "    \"Country\": \"USA\",\n",
    "    \"StartTime\": \"14:00\",\n",
    "    \"EndTime\": \"16:00\",\n",
    "    \"Seats\": \n",
    "    [\n",
    "      {  \n",
    "        \"Type\": \"Regular\",\n",
    "        \"Price\": 14.99,\n",
    "        \"Status\": \"Almost Full\"\n",
    "      },\n",
    "      {  \n",
    "        \"Type\": \"Premium\",\n",
    "        \"Price\": 24.99,\n",
    "        \"Status\": \"Available\"\n",
    "      }\n",
    "    ]\n",
    "  },\n",
    "  {\n",
    "    \"MovieID\": 2,\n",
    "    \"ShowID\": 2,\n",
    "    \"Title\": \"The Two Popes\",\n",
    "    \"Description\": \"Biographical drama film\",\n",
    "    \"Duration\": 125,\n",
    "    \"Genre\": \"Drama/Comedy\",\n",
    "    \"Language\": \"English\",\n",
    "    \"ReleaseDate\": \"31st Aug. 2019\",\n",
    "    \"Country\": \"USA\",\n",
    "    \"StartTime\": \"19:00\",\n",
    "    \"EndTime\": \"21:10\",\n",
    "    \"Seats\": \n",
    "    [\n",
    "        {  \n",
    "          \"Type\": \"Regular\",\n",
    "          \"Price\": 14.99,\n",
    "          \"Status\": \"Full\"\n",
    "      },\n",
    "        {  \n",
    "          \"Type\": \"Premium\",\n",
    "        \"Price\": 24.99,\n",
    "        \"Status\": \"Almost Full\"\n",
    "      }\n",
    "    ]\n",
    "  },\n",
    " ]\n",
    " ```\n",
    " ### Reserving Seats\n",
    " ```python\n",
    "reserve_seats(\n",
    "    api_dev_key: str,  # API developer key.\n",
    "    session_id: str,   # User Session ID to track this reservation. \n",
    "                       # Once the reservation time of 5 minutes expires, \n",
    "                       # user's reservation on the server will be removed using this ID.\n",
    "    movie_id: str,     # Movie to reserve.\n",
    "    show_id:  str,     # Show to reserve.\n",
    "    seats_to_reserve: List(int)  # An array containing seat IDs to reserve.\n",
    ")\n",
    "```\n",
    "\n",
    "Returns: (JSON)\n",
    "```\n",
    "    The status of the reservation, which would be one of the following:\n",
    "        1. Reservation Successful,\n",
    "        2. Reservation Failed - Show Full\n",
    "        3. Reservation Failed - Retry, as other users are holding reserved seats.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. DB Design\n",
    "\n",
    "1. Each **City** can have multiple **Cinema**s\n",
    "2. Each **Cinema** can have multiple **Cinema_Hall**s.\n",
    "3. Each **Movie** will have **Show**s and each Show will have multiple **Booking**s.\n",
    "4. A **User** can have multiple **Booking**s.\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "\n",
    "![](images/e_ticketing_db_design.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. High Level Design\n",
    "From a bird's eye view, \n",
    "- Web servers handle user's sessions,\n",
    "- Application servers handle all the ticket management and\n",
    "- stored in the DB\n",
    "- as well as work with cache servers to process reservations.\n",
    "\n",
    "![](images/e_ticketing_high_level.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. Detailed Component Design\n",
    "\n",
    "Let's explore the workflow part where there are no seats available to reserve, but all seats haven't been booked yet, (some users are holding in the reservation pool and have not booked yet)\n",
    "- the user is taken to a waiting page, waiting until the required seats get freed from the reservation pool. Options for the user at this point include:\n",
    "- if the required number of seats become available, take the user to theatre page to choose seats\n",
    "- While waiting, if all seats are booked, or there are fewer seats in the reservation pool than the user intends to book, then the user is shown the error message.\n",
    "- User cancels the waiting and is taken back to the movie search page.\n",
    "- At maximum, a user waits for an hour, after that the user's session expires and the user is taken back to the movie search page.\n",
    "       \n",
    "If seats are reserved successfully, the user has 5 minutes to pay for the reservation. After payment, booking is marked complete. If the user isn't able to pay within 5 minutes, all the reserved seats are freed from the reservation pool to become available to other users.\n",
    "\n",
    "#### How do we keep track of all active reservations  that haven't been booked yet? and also keep track of waiting customers?\n",
    "We need two daemon services:\n",
    "\n",
    "**a. Active Reservation Service**\n",
    "\n",
    "This will keep track of all active reservations and remove expired ones from the system.\n",
    "\n",
    "We can keep all the reservations of a show in memory in a [Linked Hashmap](https://www.geeksforgeeks.org/linkedhashmap-class-java-examples/), in addition to also keeping data in the DB. \n",
    "- We will need this doubly-linked data structure to jump to any reservation position to remove it when the booking is complete. \n",
    "- The head of the HashMap will always points to the oldest record, since we will have expiry time associated with each reservation. The reservation can be expired when the timeout is reached.\n",
    "\n",
    "To store every reservation for every show, we can have a HashTable where the `key` = `ShowID` and `value` = Linked HashMap containing `BookingID` and creation `Timestamp`.\n",
    "\n",
    "In the DB, \n",
    "- we store reservation in the `Booking` table\n",
    "- expiry time will be in the Timestamp column. \n",
    "- The `Status` field will have a value of `Reserved(1)` and, as soon as a booking is complete, update the status to `Booked(2)`\n",
    "    - After status is changed, remove the reservation record from Linked HashMap of the relevant show. \n",
    "- When reservation expires, remove it from the Booking table or mark it `Expired(3)`, and remove it from memory as well.\n",
    "\n",
    "ActiveReservationService will work with the external Financial service to process user payments. When a booking is completed, or a reservation expires, WaitingUserService will get a signal so that any waiting customer can be served.\n",
    "\n",
    "```python\n",
    "\n",
    "# The HashTable keeping track of all active reservations\n",
    "hash_table = {\n",
    "    # ShowID :  # LinkedHashMap <BookingID, Timestamp>\n",
    "    'showID1': {\n",
    "        (1, 1575465935),\n",
    "        (2, 1575465940),\n",
    "        (2, 1575466950),\n",
    "    },\n",
    "    'showID2': { ... },\n",
    "}\n",
    "```\n",
    "\n",
    "**b. Waiting User Service**\n",
    "\n",
    "- This service will keep track of waiting users in a Linked HashMap or TreeMap.\n",
    "- To help us jump to any user in the list and remove them when they cancel the request.\n",
    "- Since it's a first-come-first-served basis, the head of the Linked HashMap would always point to the longest waiting user, so that whenever seats become available, we can serve users in a fair manner.\n",
    "\n",
    "We'll have a HashTable to store all waiting users for every show. \n",
    "    Key = `ShowID`, value = `Linked HashMap containing UserIDs and their  start-time`\n",
    "    \n",
    "Clients can use Long Polling to keep themselves updated for their reservation status. Whenever seats become available, the server can use this request to notify the user.\n",
    "\n",
    "#### Reservation Expiration\n",
    "On the server, the Active Reservation Service keeps track of expiry of active connections (based on reservation time). \n",
    "\n",
    "On the client, we will show a timer (for expiration time), which could be a little out of sync with the server. We can add a buffer of 5 seconds on the server to prevent the client from ever timing out after the server, which, if left unchecked, could prevent successful purchase. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7. Concurrency\n",
    "We need to handle concurrency, such that no 2 users are able to book the same seat.\n",
    "\n",
    "We can use transactions in SQL databases, isolating each transaction by locking the rows before we can update them. If we read rows, we'll get a write lock on the them so that they can't be updated by anyone else.\n",
    "\n",
    "Once the DB transaction is committed and successful, we can start tracking the reservation in the Active Reservation Service."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 8. Fault Tolerance\n",
    "If the two services crash, we can read all active reservations from the Booking table. \n",
    "\n",
    "Another option is to have a **master-slace configuration** so that, when the master crashes, the slave can take over. We are not storing the waiting users in the DB, so when Waiting User Service crashes, we don't have any means to recover the data unless we have a master-slave setup.\n",
    "\n",
    "We can also have the same master-slave setup for DBs to make them fault tolerant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 9. Data Partitioning\n",
    "Partitioning by MovieID will result in all Shows of a Movie being in a single server. \n",
    "For a hot movie, this could cause a lot of load on that server. A better approach would be to partition based on ShowID; this way, the load gets distributed among different servers.\n",
    "\n",
    "We can use Consistent Hashing to allocate application servers for both (ActiveReservationService and WaitingUserService) based on `ShowID`. This way, all waiting users of a particular show will be handled by a certain set of servers.\n",
    "\n",
    "**When a reservation expires, the server holding that reservation will:**\n",
    "\n",
    "1. Update DB to remove the expired Booking (or mark it `Expired(3)` and update the seats status in `Show_Seats` table.\n",
    "2. Remove the reservation from Linked HashMap.\n",
    "3. Notify the user that their reservation expired.\n",
    "4. Broadcast a message to `WaitingUserService` servers that are holding waiting users of that Show to find who the longest waiting user is. Consistent Hashing scheme will help tell what servers are holding these users.\n",
    "5. Send a message to the `WaitingUserService` to go ahead and process the longest waiting user if required seats have become available.\n",
    "\n",
    "**When a reservation is successful:**\n",
    "1. The server holding that reservation will send a message to all servers holding waiting users of that Show.\n",
    "2. These servers upon receiving the above message, will query the DB (or a DB cache) to find how many seats are available. \n",
    "3. The servers can now expire all waiting users that want to reserve more seats than the available seats.\n",
    "4. For this, the WaitingUSerService has to iterate through the Linked HashMap of all the waiting users to remove them.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}