एक भारित निर्देशित ग्राफ (कुंजी/मान डेटाबेस से अधिक)

Question

हम एक भारित निर्देशित ग्राफ ठीकरा चाहते हैं,

उपयोगकर्ता नोड्स और किनारों गतिशील रूप में जोड़ सकते हैं, पहले DB/ग्राफ़ खाली है पर विभाजन।

हम एक कुंजी/मान डेटाबेस (शायद Redis) में नोड्स और किनारों रखें: प्रत्येक नोड के लिए, हम कुंजी के रूप में nodeId और संदर्भित नोड्स की चाबियों का एक sortedset sortedSet में प्रत्येक nodeId के स्कोर है होगा किनारे का वजन।

(के बारे में प्रश्न देखें कि यहाँ: Redis: Implement Weighted Directed Graph)

हम एक संतुलन बाधा नहीं है, ग्राफ़ पर सबसे आम कार्रवाई डिज्कस्ट्रा है, और हम मैं/हे कम करने के लिए (में नेटवर्क की तरह था हमारे मामले)

संभव समाधान: प्रत्येक DB सर्वर आईपी के साथ अन्य सर्वर की एक सूची है:

कुंजी: server1, मूल्य: .... 250,1

कुंजी: server2, मूल्य: .... 250.2

कुंजी: server3, मूल्य: .... 250,3

और प्रत्येक nodeId

serverX.originalNodeId हो जाएगा क्या एल्गोरिथ्म है कि निर्णय लेता है जो नोड जहां चला जाता है हो सकता है? क्या हमें नोड की पुन: स्थिति का समर्थन करना चाहिए?

मुझे लगता है कि अनुभवहीन दृष्टिकोण, होगा serverX नोड एक जोड़ने जहां argmax (सर्वर एक्स में नोड्स है कि नोड एक साथ किनारों का #), जब तक पूरी तरह से कब्जा कर लिया serverX नहीं है ..

Answer 1

के बाद से प्रोसेसिंग क्लाइंट साइड होता है, इस तरह के ग्राफ डेटा को शेड करना बहुत कठिन नहीं होता है - आपको प्रत्येक चरण में एक ही क्रमबद्ध सेट की आवश्यकता होती है, इसलिए इससे कोई फ़र्क नहीं पड़ता कि सेट कौन सा नोड लोड किया गया है। नोड के साथ जाने के लिए वास्तविक डेटा प्राप्त करना अंतिम चरण के रूप में होता है - यदि आपके पास केवल एक नोड है, तो यह एक साधारण एमजीईटी होगा, और कई नोड्स में विभाजित करना काफी आसान है।

यह निर्धारित करने के लिए कि कौन सा नोड एक कुंजी संग्रहीत किया जाएगा, आपको मैन्युअल रूप से उन्हें ट्रैक करने की कोशिश करने के बजाय हैश का उपयोग करना चाहिए। मैं किसी विशेष नोड को हैश की एक श्रृंखला मैपिंग का उपयोग करता हूं। यह दीर्घकालिक दृढ़ता के लिए रेडिस में संग्रहीत है लेकिन वास्तव में ग्राहक का हिस्सा है। किसी विशेष कुंजी तक पहुंचने के लिए आपको बस की हैश प्राप्त करें, इसे तालिका में देखें, और उस नोड से कनेक्ट करें। हजारों स्लॉट वाले टेबल का उपयोग करना डेटा को दूसरे नोड में स्थानांतरित करना आसान बनाता है - तालिका को अपडेट करें और किसी विशेष स्लॉट के लिए अनुरोध एक अलग नोड पर जायेंगे। यह काफी समान है, हालांकि रेडिस क्लस्टर में उपयोग किए जाने वाले दृष्टिकोण के समान नहीं है।

उसने कहा, शेडिंग स्थापित करने का मेरा कारण ग्राफ डेटा नहीं था। केवल छोटे आईडी वाले छोटे सॉर्ट किए गए सेट में ज्यादा मेमोरी नहीं होती है - आपको बिना किसी परेशानी के एक एकल नोड पर 100 मिलियन किनारों को संभालने में सक्षम होना चाहिए।