चरण 1: मामलों और बाधाओं का उपयोग करें आवश्यकताओं को इकट्ठा करें और समस्या को हल करें। उपयोग के मामलों और बाधाओं को स्पष्ट करने के लिए प्रश्न पूछें। मान्यताओं पर चर्चा करें।
साक्षात्कारकर्ता के बिना स्पष्ट प्रश्नों को संबोधित करने के लिए, हम कुछ उपयोग मामलों और बाधाओं को परिभाषित करेंगे।
बक्सों का इस्तेमाल करें हम केवल निम्नलिखित उपयोग के मामलों को संभालने के लिए समस्या को हल करेंगे उपयोगकर्ता किसी को खोजता है और खोजे गए व्यक्ति का सबसे छोटा रास्ता देखता है सेवा की उच्च उपलब्धता है अड़चनें और धारणाएँ राज्य की धारणाएँ यातायात समान रूप से वितरित नहीं किया जाता है कुछ खोज दूसरों की तुलना में अधिक लोकप्रिय हैं, जबकि अन्य केवल एक बार निष्पादित होती हैं ग्राफ डेटा एक मशीन पर फिट नहीं होगा ग्राफ़ किनारों का आकार कम किया गया है 100 मिलियन उपयोगकर्ता प्रति उपयोगकर्ता औसत 50 मित्र 1 बिलियन मित्र प्रति माह खोज करता है अधिक पारंपरिक प्रणालियों के उपयोग का अभ्यास करें - ग्राफ़-विशिष्ट समाधानों जैसे कि ग्राफ़कॉक या नियो 4 जे जैसे ग्राफ़ डेटाबेस का उपयोग न करें
उपयोग की गणना करें अपने साक्षात्कारकर्ता के साथ स्पष्ट करें कि क्या आपको बैक-ऑफ-द-लिफाफा उपयोग गणनाओं को चलाना चाहिए।
5 अरब मित्र संबंध 100 मिलियन उपयोगकर्ता * प्रति उपयोगकर्ता औसत 50 मित्र प्रति सेकंड 400 खोज अनुरोध आसान रूपांतरण गाइड:
2.5 मिलियन सेकंड प्रति माह 1 प्रति सेकंड अनुरोध = प्रति माह 2.5 मिलियन अनुरोध 40 प्रति सेकंड अनुरोध = प्रति माह 100 मिलियन अनुरोध प्रति माह 400 अनुरोध = प्रति माह 1 बिलियन अनुरोध चरण 2: एक उच्च स्तरीय डिज़ाइन बनाएं सभी महत्वपूर्ण घटकों के साथ एक उच्च स्तरीय डिजाइन की रूपरेखा।
Imgur
चरण 3: डिजाइन कोर घटक प्रत्येक मुख्य घटक के लिए विवरण में गोता लगाएँ।
मामले का उपयोग करें: उपयोगकर्ता किसी की खोज करता है और खोजे गए व्यक्ति के लिए सबसे छोटा रास्ता देखता है अपने साक्षात्कारकर्ता के साथ स्पष्ट करें कि आपको कितने कोड लिखने की उम्मीद है।
लाखों उपयोगकर्ताओं (वर्टिकल) और अरबों मित्र संबंधों (किनारों) की अड़चन के बिना, हम सामान्य BFS दृष्टिकोण के साथ इस सबसे छोटे पथ को हल कर सकते हैं:
वर्ग ग्राफ़ (ग्राफ़):
def shortest_path (स्वयं, स्रोत, भाग्य): यदि स्रोत कोई नहीं है या कोई भी नहीं है: कोई नहीं यदि स्रोत भाग्य है: वापसी [source.key] prev_node_keys = self._shortest_path (स्रोत, भाग्य) अगर prev_node_keys कोई नहीं है: कोई नहीं लौटा अन्य: path_ids = [dest.key] prev_node_key = prev_node_keys [dest.key] जबकि prev_node_key कोई नहीं है: path_ids.append (prev_node_key) prev_node_key = prev_node_keys [prev_node_key] वापसी path_ids [:: - 1]
def _shortest_path (स्वयं, स्रोत, भाग्य): कतार = deque () queue.append (स्रोत) prev_node_keys = {source.key: कोई नहीं} source.visit_state = State.visited जबकि कतार: नोड = कतार.पॉपलेफ़्ट () यदि नोड भाग्य है: वापसी prev_node_keys prev_node = नोड नोड में adj_node.adj_nodes.values () के लिए: अगर 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 कोई नहीं लौटा हम सभी उपयोगकर्ताओं को एक ही मशीन पर फिट करने में सक्षम नहीं होंगे, हमें उपयोगकर्ताओं को व्यक्तिगत सर्वर पर शार्प करने और उन्हें लुकअप सेवा के साथ एक्सेस करने की आवश्यकता होगी।
क्लाइंट एक रिवर्स प्रॉक्सी के रूप में चल रहा है, वेब सर्वर के लिए एक अनुरोध भेजता है वेब सर्वर खोज एपीआई सर्वर के अनुरोध को आगे बढ़ाता है खोज एपीआई सर्वर उपयोगकर्ता ग्राफ सेवा के लिए अनुरोध को आगे बढ़ाता है उपयोगकर्ता ग्राफ़ सेवा निम्नलिखित करती है: व्यक्ति सर्वर जहां वर्तमान उपयोगकर्ता की जानकारी संग्रहीत है खोजने के लिए लुकअप सेवा का उपयोग करता है उपयोगकर्ता के वर्तमान मित्र की सूची को पुनः प्राप्त करने के लिए उपयुक्त व्यक्ति सर्वर को ढूँढता है प्रत्येक निकटवर्ती_कोड के लिए आईडी के रूप में वर्तमान उपयोगकर्ता के स्रोत और वर्तमान उपयोगकर्ता के friend_ids के रूप में एक BFS खोज चलाता है दिए गए आईडी से adjacent_node प्राप्त करने के लिए: उपयोगकर्ता ग्राफ़ सेवा को फिर से लुकअप सेवा के साथ संवाद करने की आवश्यकता होगी, यह निर्धारित करने के लिए कि दिए गए आईडी से मेल खाते हुए पर्सनेल सर्वर थ्रेडिकेंट_नोड (ऑप्टिमाइज़ेशन के लिए संभावित) अपने साक्षात्कारकर्ता के साथ स्पष्ट करें कि आपको कितना कोड लिखना चाहिए।
नोट: त्रुटि से निपटने को सरलता के लिए नीचे रखा गया है। पूछें कि क्या आपको उचित त्रुटि सौंपने का कोड चाहिए।
लुकअप सेवा कार्यान्वयन:
क्लास लुकअप सर्विस (ऑब्जेक्ट):
def __init __ (स्व): self.lookup = self._init_lookup () # कुंजी: person_id, मान: person_server
def _init_lookup (स्व): ...
डीफ़ लुकिंग_पर्सन_सर्वर (स्वयं, person_id): स्व वापस जाएँ। [person_id] व्यक्ति सर्वर कार्यान्वयन:
वर्ग व्यक्ति (वस्तु):
def __init __ (स्व): self.people = {} # कुंजी: person_id, मान: व्यक्ति
def add_person (स्व, व्यक्ति): ...
लोगों को (स्वयं, आईडी) को हराया: परिणाम = [] आईडी में आईडी के लिए: अगर स्वयं में आईडी। लोग: results.append (self.people [id]) वापसी के परिणाम व्यक्ति कार्यान्वयन:
वर्ग व्यक्ति (वस्तु):
def __init __ (स्व, आईडी, नाम, friend_ids): self.id = आईडी स्व.नाम = नाम self.friend_ids = friend_ids उपयोगकर्ता ग्राफ़ सेवा
