लाखों नोड्स (सोशल नेटवर्क) के साथ ग्राफ डेटा स्ट्रक्चर

Question

Graphsडेटा संरचना का उपयोग करके सोशल नेटवर्क के डिज़ाइन के संदर्भ में, जहां आप एक व्यक्ति से दूसरे कनेक्शन में कनेक्शन खोजने के लिए बीएफएस कर सकते हैं, मेरे पास कुछ प्रश्न हैं इससे संबंधित

यदि लाखों उपयोगकर्ता हैं, तो टोपोलॉजी वास्तव में ग्राफिक्स की तुलना में अधिक जटिल और अंतःस्थापित होगा और मैं यह समझने की कोशिश कर रहा हूं कि आप इन समस्याओं को कैसे हल कर सकते हैं।

1. असली दुनिया में, सर्वर असफल। यह आपको कैसे प्रभावित करता है?

2. कैशिंग कैशिंग का लाभ कैसे ले सकता है?

3. क्या आप ग्राफ (अनंत) के अंत तक खोज करते हैं? आप कब हारने का फैसला करते हैं?

4. वास्तविक जीवन में, कुछ लोगों के पास दूसरों के मुकाबले दोस्तों के अधिक मित्र हैं, और इसलिए अधिक संभावना है कि आप और किसी और के बीच पथ बनाने के लिए। आप इस डेटा का उपयोग कैसे कर सकते हैं यह चुनने के लिए कि आप कहां से शुरू करते हैं?

Answer 1

आपका प्रश्न रोचक और उत्सुक लगता है :)

1) खैर ... ज़ाहिर है, डेटा डिस्क में संग्रहीत है, राम में नहीं। डिस्क में ऐसे सिस्टम होते हैं जो विफलता से बचते हैं, विशेष रूप से, RAID-5 उदाहरण के लिए। रिडंडेंसी कुंजी है: यदि एक सिस्टम विफल रहता है तो वहां एक और प्रणाली अपनी जगह लेने के लिए तैयार होती है। एक साथ रिडंडेंसी और वर्कलोड साझाकरण भी है ... दो कंप्यूटर हैं जो समानांतर में काम करते हैं और अपनी नौकरियां साझा करते हैं, लेकिन अगर कोई केवल एक ही काम बंद कर देता है और पूर्ण वर्कलोड लेता है।

Google या फेसबुक रिडंडेंसी जैसी जगहें 2 नहीं हैं, 1200000000 है :) और यह भी मानें कि डेटा एक सर्वर फार्म में नहीं है, Google में कई डेटासेंटर एक साथ जुड़े हुए हैं, इसलिए यदि एक इमारत विस्फोट हो जाती है, तो दूसरा उदाहरण के लिए अपनी जगह ले जाएगा।

2) बिल्कुल आसान सवाल नहीं है, लेकिन आम तौर पर इन प्रणालियों में डिस्क सरणी के लिए बड़ा कैश होता है, इसलिए डिस्क पर डेटा पढ़ने और लिखना हमारे लैपटॉप की तुलना में तेज़ है :) डेटा कई समवर्ती द्वारा समानांतर में संसाधित किया जा सकता है सिस्टम और यह फेसबुक जैसी सेवाओं की गति की कुंजी है।

3) ग्राफ का अंत अनंत नहीं है। तो वास्तव में वास्तविक तकनीक के साथ यह संभव है।

सभी कनेक्शनों की खोज करने की कम्प्यूटेशनल जटिलता और ग्राफ पर सभी नोड्स ओ (एन + एम) है जहां एन शिखर की संख्या है और किनारों की संख्या है। इसका मतलब है, यह पंजीकृत उपयोगकर्ता की संख्या और उपयोगकर्ताओं के बीच कनेक्शन की संख्या के लिए रैखिक है। और राम इन दिनों बहुत सस्ता है।

आवश्यक होने पर संसाधनों को जोड़ने में रैखिक वृद्धि होने के नाते आसान है। अधिक कंप्यूटर जोड़ें जितना अधिक आप अमीर हो जाते हैं :)

यह भी विचार करें कि कोई भी प्रत्येक नोड के लिए वास्तविक खोज नहीं करेगा, फेसबुक में सब कुछ काफी "स्थानीय" है, आप एक व्यक्ति के प्रत्यक्ष मित्र को देख सकते हैं, नहीं दोस्त के दोस्त का दोस्त .... यह उपयोगी नहीं होगा।

डेटा संरचना अच्छी तरह से की जाती है, तो सीधे एक चरम से जुड़े शीर्षकों की संख्या प्राप्त करना, बहुत आसान और तेज़ है। एसक्यूएल में यह एक साधारण चयन होगा और यदि टेबल अच्छी तरह अनुक्रमित हैं तो यह बहुत तेज़ होगा और उपयोगकर्ताओं की कुल संख्या पर भी निर्भर नहीं होगा (हैश टेबल की अवधारणा देखें)।