Skip to content

Latest commit

 

History

History
349 lines (264 loc) · 18.1 KB

README-zh-TW.md

File metadata and controls

349 lines (264 loc) · 18.1 KB
Raw

為一個社群網站設計資料結構

注意：本文件某些連結直接連到 系統設計主題的索引來避免重複的內容。你可以參考連結來取得相關重點、設計的取捨和選擇。

步驟一：描述使用情境與限制

蒐集問題的需求、資訊和範圍。 透過詢問問題來瞭解使用情境和限制。 討論你的假設。

在這裡沒有面試者會幫你釐清上面的問題，所以我們會預先定義一些使用情境和限制。

使用情境

我們將所要解決的問題限縮在以下範圍

  • 使用者會尋找某人，並且看到此搜尋的最短路徑
  • 服務本身具備高可用 (High-Availability)

限制與假設

狀態假設

  • 流量並非均勻的分佈
    • 某些搜尋總是比較熱門，但有的搜尋可能只出現一次
  • 資料並非僅存在於一台機器上
  • 圖的邊上並沒有權重
  • 一億名使用者
  • 平均每個使用者有 50 位朋友
  • 每月有 10 億次的搜尋朋友的行為

練習使用更傳統的系統 - 不要使用圖形化的解決方案，像是 GraphQL 或是圖形化資料庫 Neo4j。

計算使用量

向你的面試人員詢問你是否可以用比較粗略的方式來計算使用量

  • 50 億個朋友之間的關係要記錄
    • 一億個使用者 * 每個使用者平均 50 位朋友
  • 每秒 400 次搜尋

一些筆記：

  • 每月 250 萬秒
  • 每秒 1 次請求 = 每月 250 萬次請求
  • 每秒 40 次請求 = 每月 1 億次請求
  • 每秒 400 次請求 = 每月 10 億 次請求

步驟二：進行高階設計

提出所有重要元件的高階設計

Imgur

步驟三：設計核心元件

深入每個核心元件的細節

使用情境： 使用者會尋找某人，並且看到此搜尋的最短路徑

向你的面試者詢問你的程式碼要撰寫到多詳細.

如果沒有數百萬個使用者 (圖的點) 和數十億的朋友之間的關係 (圖的邊)，我們可以用一般的廣度優先搜尋演算法(BFS) 來解決未加權的最短路徑問題：

class Graph(Graph):

    def shortest_path(self, source, dest):
        if source is None or dest is None:
            return None
        if source is dest:
            return [source.key]
        prev_node_keys = self._shortest_path(source, dest)
        if prev_node_keys is None:
            return None
        else:
            path_ids = [dest.key]
            prev_node_key = prev_node_keys[dest.key]
            while prev_node_key is not None:
                path_ids.append(prev_node_key)
                prev_node_key = prev_node_keys[prev_node_key]
            return path_ids[::-1]

    def _shortest_path(self, source, dest):
        queue = deque()
        queue.append(source)
        prev_node_keys = {source.key: None}
        source.visit_state = State.visited
        while queue:
            node = queue.popleft()
            if node is dest:
                return prev_node_keys
            prev_node = node
            for adj_node in node.adj_nodes.values():
                if adj_node.visit_state == State.unvisited:
                    queue.append(adj_node)
                    prev_node_keys[adj_node.key] = prev_node.key
                    adj_node.visit_state = State.visited
        return None

我們不可能透過一台機器來服務所有的使用者，所以我們會需要使用到 分片 的技術來讓使用者分散到不同的 使用者伺服器 上，並且透過 查找服務 來搜尋他們。

  • 使用者 發送請求到 網頁伺服器，這個伺服器是以 反向代理伺服器 的方式執行
  • 網頁伺服器 轉送請求到 搜尋 API 伺服器
  • 搜尋 API 伺服器轉送請求到 使用者圖形服務
  • 使用者圖形服務 會進行以下行為：
    • 使用 查詢服務 來尋找 使用者伺服器，這個伺服器儲存了目前使用者的資訊
    • 尋找正確的 使用者伺服器 來取得目前使用者的 friend_ids 清單
    • 使用目前使用者當成 source，以及 friend_ids 當成 ids 來執行廣度優先搜尋演算法(BFS)
    • 給定 id，為了找到 adjacent_node：
      • 使用者圖形服務 需要 再一次 和 查詢服務 進行溝通，用來決定哪一台 使用者伺服器 用來儲存對應 id 的 adjacent_node。

向你的面試者詢問他預期你的程式碼要寫到什麼程度.

注意：為了簡化流程，例外處理並不在底下的程式碼中。向你的面試官詢問是否需要考慮例外處理。

查詢服務 實做：

class LookupService(object):

    def __init__(self):
        self.lookup = self._init_lookup()  # key: person_id, value: person_server

    def _init_lookup(self):
        ...

    def lookup_person_server(self, person_id):
        return self.lookup[person_id]

使用者服務 實作：

class PersonServer(object):

    def __init__(self):
        self.people = {}  # key: person_id, value: person

    def add_person(self, person):
        ...

    def people(self, ids):
        results = []
        for id in ids:
            if id in self.people:
                results.append(self.people[id])
        return results

使用者 實作：

class Person(object):

    def __init__(self, id, name, friend_ids):
        self.id = id
        self.name = name
        self.friend_ids = friend_ids

使用者圖形服務 實作：

class UserGraphService(object):

    def __init__(self, lookup_service):
        self.lookup_service = lookup_service

    def person(self, person_id):
        person_server = self.lookup_service.lookup_person_server(person_id)
        return person_server.people([person_id])

    def shortest_path(self, source_key, dest_key):
        if source_key is None or dest_key is None:
            return None
        if source_key is dest_key:
            return [source_key]
        prev_node_keys = self._shortest_path(source_key, dest_key)
        if prev_node_keys is None:
            return None
        else:
            # Iterate through the path_ids backwards, starting at dest_key
            path_ids = [dest_key]
            prev_node_key = prev_node_keys[dest_key]
            while prev_node_key is not None:
                path_ids.append(prev_node_key)
                prev_node_key = prev_node_keys[prev_node_key]
            # Reverse the list since we iterated backwards
            return path_ids[::-1]

    def _shortest_path(self, source_key, dest_key, path):
        # Use the id to get the Person
        source = self.person(source_key)
        # Update our bfs queue
        queue = deque()
        queue.append(source)
        # prev_node_keys keeps track of each hop from
        # the source_key to the dest_key
        prev_node_keys = {source_key: None}
        # We'll use visited_ids to keep track of which nodes we've
        # visited, which can be different from a typical bfs where
        # this can be stored in the node itself
        visited_ids = set()
        visited_ids.add(source.id)
        while queue:
            node = queue.popleft()
            if node.key is dest_key:
                return prev_node_keys
            prev_node = node
            for friend_id in node.friend_ids:
                if friend_id not in visited_ids:
                    friend_node = self.person(friend_id)
                    queue.append(friend_node)
                    prev_node_keys[friend_id] = prev_node.key
                    visited_ids.add(friend_id)
        return None

我們會使用公開的 REST API：

$ curl https://social.com/api/v1/friend_search?person_id=1234

回應：

{
    "person_id": "100",
    "name": "foo",
    "link": "https://social.com/foo",
},
{
    "person_id": "53",
    "name": "bar",
    "link": "https://social.com/bar",
},
{
    "person_id": "1234",
    "name": "baz",
    "link": "https://social.com/baz",
},

內部通訊上，我們可以使用 遠端程式呼叫 的方式。

步驟四：擴展你的設計

根據你設定的限制條件，提出目前設計架構上的瓶頸，並提出解決方法

Imgur

重要提醒：不要一開始就從最初的設計跳到最後階段

描述你如何進行 1) 負載壓力測試、2) 描述瓶頸、3) 解決瓶頸，並提出替代方案、4) 重複以上步驟。可以參考 在 AWS 上設計可以乘載百萬使用者的系統 章節作為參考，學習如何一步一步來擴展你的初始架構設計。

針對初始設計所會遇到的瓶頸進行討論，並且知道如何解決是很重要的。舉例來說，你可以透過增加一台負載平衡器來加入多個網頁伺服器來解決什麼問題？CDN呢？主-從架構？每個選擇的替代方案和權衡條件是什麼？

我們會介紹一些元件來使系統設計更完整，並且解決擴展性的問題。這裡沒有顯示內部負載平衡器，以免讓整個架構太混亂。

為了避免重複贅述，請參考 系統設計主題索引 中提到的各種架構的取捨與選擇：

為了解決平均每秒 400 次的讀取請求 (高峰時可能更高)，使用者資料可以從 記憶體快取，像是 Redis 或 Memcached 中取得，用以降低回應時間和降低下游服務的流量。這對連續進行多次搜尋的使用者以及連接良好的使用者特別有用。從記憶體中循序讀取 1 MB 的資料大約需要花費 250 微秒，然而，從 SSD 中讀取則需要花 4 倍以上的時間，而從硬碟中讀取則要花費 80 倍以上的時間1

底下是一些額外的優化建議：

  • 在記憶體快取中儲存完整或部分 BFS 遍歷的結果來加速查找過程
  • 在離線時，批次計算完整或部分 BFS 結果，用來加速後續在 NoSQL 資料庫 中查找的過程
  • 將透過 使用者服務 來查找朋友的過程批次處理，並且將此服務託管在同一台機器上避免伺服器之間的跳轉
    • 透過將 使用者服務 依照位置進行 分片 來進一步改善料能，因為通常朋友之間的距離在圖形上會靠得很近
  • 可以同時執行兩個 BFS 搜尋，一個從起始點開始，一個從終點開始，最後再進行合併
  • 在進行 BFS 搜尋時，先從朋友數目多的使用者開始，因為他們更有可能減少當前使用者與搜尋目標之間的 分離度 的數量
  • 在使用者要繼續搜尋之前，根據時間或跳轉的數量來設定一些限制，因為在某些情況下，搜尋可能需要花很多時間
  • 使用像是 Neo4j 或是圖形查詢語言 GraphQL (如果沒有限制使用 圖形資料庫)

其他想要談論的重點

根據你問題的範圍和面試剩餘的時間，深入討論以下主題

SQL 擴展模式

NoSQL

快取

非同步機制與微服務

通訊

安全

可以參考 資訊安全 章節。

延遲數目

可以參考 每個開發者都應該知道的延遲數量級 章節。

持續調整與改善

  • 持續的評估和監控你的系統，找出可能的瓶頸
  • 擴展是一個不斷來回迭代的過程