Please enable JavaScript.

Coggle requires JavaScript to display documents.

Designing a Yelp - Coggle Diagram

- - - - Pushing sensitive information online and don’t know how to remove.
      - Adding information that are too large or dangerous to the application.
      - Modifying the front end code and found sensitive information or break something.
    - - Attacker can STRIDE: Spoofing, Tempering, Repudiation, Information disclosure, DoS, Elevation of Privilage.
        
        Spoofing: IP Spoofing and then lead to DDoS Attack, DNS spoofing and then cause users visite the wrong website through our URL.
        
        Tempering: Attacking the tree structure and add lots of fake business information and rating. Or flood the business with fake rating to change the overall rating of the business.
        
        Repudiation: calling in as a business owner and provide fake information to their or others business.
        
        Information disclosure: attacking the DB and access user passwords.
        
        DoS: flood the LB and servers with requests in a region and try to cause specific hotspot partition server down.
        
        Elevation of privilege: Using XSS and CSRF to attack the account of business owner or user, so that they can control their accounts and send fake reviews from them.
    - - Improper implementation of cache, sharing, and security machinists.
    - - The Server could all go down
      - The LB could all go down
      - The DB could all go down
      - The Cache could all go down
  - - - Using more redundancy nodes and back up DB in a separated node that constantly update, so when the primary is down, we can use them.
      - Using reverse index to build Index nodes, such that when the servers are down, they can rebuild the data structure (QuadTree) faster.
      - Redundancy application nodes for consistent serving.
    - - Input validation, and using whitelisting for both inputs and IP addresses for sensitive information access. :
      - Good LB technic and monitoring for abnormal behavior from request from one or multiple IPs.
      - Assigning review and request limit to a single user.
    - - Be careful about what contents users can add and remove.
      - Proper application and business logic encapsulation to prevent user from doing crazy things and cause damages.
- - - - In 5 years, places will be about 3 Billions, and QPS will be about 600K.
- - - - Total = 8 *3 + 256 + 512 + 1 >= 793 bytes
  - - - Total = 8 + 4 + 512 + 1 >= 525 bytes
- - - - api_dev_key (String): The developer API key of a registered account. This will be used to, among other things, throttle users based on their allocated quota
      - search_terms (String): the searching string given by user
      - user_location (String): location of the user performing the search
      - radius_filter (int): (option) specify the search radius in meters
      - maximum_results_to_return (int): number of businesses to return
      - category_filter (String): (option) filter to select the category(s) of business to query
      - sort (int): (option) sort mode: best match is (0 by default), minimum distance (1), and highest rated (2).
      - page_token (String): a token that specify a page in the result set that should be returned.
    - - JSON data: containing the detailed information about a list of business. Including the thumbnails, location, distance, discretions, address, business name, rating, and category.
- - - - Solution
        
        Store all the data in a Relational DB (such as MySQL). Each place will be stored in a separate row, uniquely identified by LocationID. Each place will have its longitude and latitude stored separately in two columns.
        For fast search, we should have indexes for both of these two fields (break into small chunks for indexing)
        
        SQL Concept code: Select * from Places where Latitude between X-D and X+D and Longitude between Y-D and Y+D (More accurate search can be applied, here is just for simplicity)
      - Efficiency (Low)
        
        Too many places between the search area, we should somehow shorten these lists. (Since we have 500M places to be stored in our service)
        
        Two indexes, and intersection between them is not efficient!
    - - Solution
        
        Intuition: splitting the whole world into grids (indexing by grid). So that the size of the grid is fixed, and they can be easily found with latitude and longitude (by using grdiID).
        
        When we search, we first find the grids covered by our area, and then the neighbors that surround these grids. If the search area is less than or equals to the grid size, then we only need to search that one grid and the 8 neighbors around it.
        
        Optimization: Indexing the grids in memory (HashMap<GridID, List<Place>>)
      - Efficiency (Medium)
        
        The runtime is improved, but since the distribution of the place is sparse in some place and dense in the other, the performance is not really good.
        
        Solution: dynamically assign the grid, which means we make the dense place with more grid, and sparse place with less.
        Hard points: (1) How to map these places to locations, (2) how to find the neighbor grids?
    - - Efficiency
      - Solution
        
        What data Structure can hold these data?
        
        Using a QuadTree Structure to split the grid into 4 parts whenever the population in the grid is larger than 500.
        
        How will we build a Quad tree?
        
        We starting from the root node to represent all the places in the world within one grid. And then we can start to split the node into 4 if the size is larger than 500. Until all the leaf nodes are in the desired size.
        
        How will we find the grid for a given location?
        
        Starting from the root node we check if the location is within the node, and check if the four children contains the location. When we reach the leaf node that contains the location, we found it in the right grid.
        
        How to find neighboring grids
        
        Using doubly linked list to connect each node in each level of the tree, then the sibling nodes close to the current location node are the neighbors.
        
        Once we have the LocationID's we can query the backend DB to find details about those places.
        
        Search wordflow
        
        Find the node that contains the user's location. If the amount in that node has the desired amount of places, then we return that to the user. Else we keep expending to the neighboring nodes until either we find the required number of places or exhaust our search based on the maximum radius.
        
        Memory usage needed to store the QuadTree
        
        Cache:
        
        All the locationID (8 bytes) + Lat/Long (8 + 8 bytes): 24 bytes
        
        Total is: 500 Million places * 24 bytes = 12 Billion Bytes = 12 GB
        
        Total grids = 500 million / 500 places per grid = 1 million grids (leaf nodes)
        
        So the leaf nodes will save all the location and lat/long data for 12GB. And the internal nodes will save the tree structure details
        
        Internal nodes are about 1/3 the amount of the leaf nodes: 1 million * 1/3 * 4 fields * 8 bytes/field >= 10 MB
        
        Total memory for the QuadTree
        
        12.01GB (fit into modern data server)
        
        Insert a place
        
        For non-distributed system
        
        Insert into the DB and the QuadTree.
        
        For Distributed system
        
        Find the grid/server of the new place, and then add it there (data partitioning)
- - - - Key based sharding (using LocationID as the key)
        
        Using consistent hashing
        
        Consistent hashing (load balancing and flexibility)
        
        The trick of consistent hashing
        
        the best solution is not to use K hash functions, but to generate K replica ids for each server id. Designing K hash functions while maintaining random uniformity and consistency is hard. Generating K replica ids is easy: xxx gives K replicas xxx + '1', xxx + '2', ..., xxx + 'K'. Then you take these replicas and generate K points on the ring with the same hash function
        and this is what is actually used in practice. Chord algorithm is just an example of this technique to add K replicas for each server id
        
        :star: Define: in a ring of values, we can map the range of hash function out to the ring by mod the output by the range length. Then we can using the trick above (using k replica id and hash onto the ring) to more evenly distribute the servers (esp. when the number of actually server is not large). This can prevent Shen one node is down, and the next node after it need to take all the remaining work loads.
        
        You can hash the locationID to find the place to store the data to after you have a ring of consistent hashed serverIDs (and replica ID Hash) on the ring.
        
        Finding the neighbors
        
        Just using the level linked list to find the neighbors and find them through all servers
        
        In the end the aggregation server will combine all the results
        
        Intuition
        
        H(Place) -> value, if value is in [a, b], where server A takes care of value between [a, b], then Place will be on ServerA (using consistent hashing ring and K replica “virtual servers” to evenly store places on different servers)
        
        Reverse index is needed for faster rebuild when the QuadTree Server is down (otherwise you will need to filter the whole DB just for that sub server Partition)
        
        Index server can be built with just iterating through the DB, and adding places (value) to corresponding serverID (key) on the consistent hashing ring.
        
        Replica for index server is also a good idea.
      - Range Based Sharding (Range of Region)
        
        Issues
        
        HotSpot (this is very obvious in geo-data).
        
        The performance slow and some nodes save too much, and some don't save enough.
        
        Solution
        
        Repartition
- - - - Write: only Master node
        Read: distributed between Master and Slave nodes
      - Update of write info will first show on Master, and then pass to the slave(s). A little delay is acceptable here (a few milliseconds).
    - - If only one die, then the other one can take control after the failover (cause their data structures are exactly the same)
  - - - :red_flag: Pitfalls: BF using the hash function to filter the whole DB. Then try to find the places that will be mapped to this new server (super slow and cannot response to requests when the node is rebuilt)
      - :star: How can we efficiently retrieve a mapping between Places and QuadTree server?
        
        Using reverse index: basically saving all the key that corresponding to the value as a set (reversed relationship)
        
        Here we just need to save serverIDs as keys, and the places that corresponding to/saved on the server as a set (key)