ऐतिहासिक रूप से, Mail.Ru मेल ने "बड़ी" खोज (go.mail.ru) से एक तंत्र का उपयोग किया; हालांकि, मेलबॉक्स विकल्प संसाधनों की बड़ी खपत और रखरखाव के रिश्तेदार जटिलता की वजह से इष्टतम नहीं था में समस्याओं को खोजने के लिए। लगभग 3% मेलबॉक्स मालिक मेल खोज का उपयोग करते हैं; हालांकि, हालांकि यह आंकड़ा अपेक्षाकृत छोटा लगता है, इन लोगों के बक्से आमतौर पर काफी बड़े होते हैं, और उन्हें वास्तव में एक खोज की आवश्यकता होती है। इसलिए, हमने एक विशेष खोज डेमॉन लिखने का फैसला किया जो विशेष रूप से मेल खोज से निपटेगा। इसके लिए मुख्य आवश्यकताएं उपभोग किए गए संसाधनों (सूचकांक आकार - 3% से अधिक मेलबॉक्स आकार, औसत रैम की खपत - 100 एमबी से अधिक नहीं, औसत सीपीयू उपयोग - 3% से अधिक नहीं) और क्वेरी निष्पादन गति (औसत समय - नहीं) पर प्रतिबंध था। 200 से अधिक एमएस)। यह कैसे आयोजित किया गया था, इसके बारे में मैं नीचे बताऊंगा।
दो मुख्य प्रक्रियाओं निर्णय के ढांचे में मेल स्कैन कार्य द्वारा किए गए अनुक्रमण बक्से, और खोज क्वेरी के निष्पादन है। एक नया मेल की प्राप्ति के समय में आप खोज अनुक्रमणिका को भरने के लिए, उसे पत्र बनाने आवश्यकता नहीं है। जाहिर है, सूचकांक में डेटा को सुव्यवस्थित और यथासंभव कॉम्पैक्ट होना चाहिए; हालाँकि, इस मामले में, यह सबसे अधिक संभावना है कि फ़ाइल के बीच में सम्मिलन की आवश्यकता होती है, जो डिस्क में बहुत "भारी" रिकॉर्डिंग को जन्म देगा। यह देखते हुए कि नए पत्र का आगमन किसी भी खोज क्वेरी के निष्पादन की तुलना में कई गुना अधिक होता है, खोज सूचकांक को बनाए रखने के लिए इस तरह के एक कठिन ऑपरेशन का उपयोग संदिग्ध है।
हमने दो फ़ाइलों का एक इंडेक्स बनाने का फैसला किया: स्नैपशॉट, जिसमें एक पूर्ण-पाठ इंडेक्स (सॉर्ट किया गया डेटा), और xlog है, जिसमें इंडेक्स पर लागू लगातार लेनदेन की एक सूची शामिल है। सूचकांक पर कोई भी ऑपरेशन (उदाहरण के लिए, एक नया पत्र प्राप्त करना) डिस्क पर एक एकल लिखने का कारण बनता है - यह xlog फ़ाइल के अंत में एक लेखन है। खोज क्वेरी के निष्पादन के समय, दो खोज कार्य किए जाते हैं - स्नैपशॉट द्वारा एक द्विआधारी खोज और xlog द्वारा अनुक्रमिक खोज - जिसके परिणाम संयुक्त हैं। उस समय, जब xlog पर खोज की गति हमें संतुष्ट करना बंद कर देती है, हम स्नैपशॉट का पुनर्निर्माण कर रहे हैं - हम xlog से इसमें सभी परिवर्तन करेंगे, और हम फिर से xlog को सहेजना शुरू करेंगे। यह क्षण स्वचालित रूप से दो संभावित नीतियों में से एक द्वारा निर्धारित किया जाता है: जब अगले अनुरोध का निष्पादन समय निर्धारित सीमा से अधिक हो जाता है, या जब सेट थ्रेशोल्ड xlog फ़ाइल के आकार से अधिक हो जाता है।
एक नए पत्र को अनुक्रमित करना टोकन के साथ शुरू होता है। टोकनेशन एक पत्र को अलग-अलग शब्दों में विभाजित करना है (पूर्ण-पाठ खोज एक पूरे शब्द तक काम करता है और एक मनमाने ढंग से प्रतिस्थापन द्वारा खोज करने में सक्षम नहीं है)। यह ध्यान देने योग्य है कि टोकन सबसे तुच्छ कार्य नहीं है। उदाहरण के लिए एक ईमेल पता लें
d.kalugin-balashov@corp.mail.ruजाहिर है, वह पूरा शब्द है। यह संभव है कि d.kalugin शब्द द्वारा खोज करना संभव हो (उपयोगकर्ताओं के खोज प्रश्नों के एक अध्ययन से पता चला है कि वे अक्सर "ईमेल भाग" द्वारा खोज करने का प्रयास करते हैं)। हालांकि, इस शब्द के सभी सब्सट्रिंग का समर्थन करना असंभव है, क्योंकि इससे सूचकांक के आकार में तेज वृद्धि होगी, और परिणामस्वरूप, क्वेरी निष्पादन की गति में कमी। किसी शब्द को विराम चिह्नों के अनुसार ही सब्स्टीट्यूशन में तोड़ना बहुत उचित है। तदनुसार, हमें निम्नलिखित उपशब्द मिलते हैं:
d.kalugin-balashov@corp.mail.ru
d.kalugin-balashov@corp.mail
d.kalugin-balashov@corp
d.kalugin-Balashov
d.kalugin
घ
kalugin-balashov@corp.mail.ru
kalugin-balashov@corp.mail
कलुगिन-बालाशोव @ कॉर्प
Kalugin-Balashov
Kalugin
balashov@corp.mail.ru
balashov@corp.mail
balashov @ कॉर्प
Balashov
corp.mail.ru
corp.mail
mail.ru
मेल
आरयूइन सभी शब्दों को सूचकांक में शामिल किया जाएगा।
ध्यान दें कि ऐसे पुनरावर्ती शब्द विराम में कुछ समस्याएं हैं। उदाहरण के लिए, सिस्टम प्रशासक अक्सर ऐसे सेवा पत्र प्राप्त करते हैं जिनमें विभिन्न पथ (/usr/local/something/libexec/libany.so) होते हैं, अक्सर बहुत लंबे होते हैं। इस तरह के शब्द पुनरावृत्ति की बड़ी गहराई का कारण बन सकते हैं। इसलिए, जो शब्द टोकनर के कॉन्फ़िगरेशन फ़ाइल में निर्दिष्ट लंबाई से अधिक लंबे होते हैं, उन्हें पुनरावृत्ति रूप से टोकन में विभाजित नहीं किया जाता है, लेकिन न्यूनतम लंबाई (मूल शब्द, हालांकि, सूचकांक में भी आता है) के उप-पासवर्ड में विभाजित हैं।
उदाहरण के लिए, शब्द लें:
/usr/local/something/libexec/libany.soबशर्ते कि यह अब लंबाई पुनरावर्ती tokenization के लिए अनुमति से, यह निम्न subword में बांटा गया है है:
/usr/local/something/libexec/libany.so
usr
स्थानीय
कुछ
libexec
libany
इतनाइस तरह के ब्रेकडाउन से कम गुणवत्ता वाले खोज परिणाम मिलते हैं, लेकिन यह गुणवत्ता / संसाधनों के मामले में एक समझौता है।
टोकेनाइजेशन का अंतिम चरण शब्द का पहला रूप प्राप्त करना है ("बड़ी खोज से लेमेटाइज़र" का उपयोग सभी शब्द रूपों की खोज के लिए किया जाता है) और इसमें से CRC32 लिया जाता है। इंडेक्स के सभी शब्द इन 32-बिट पूर्णांकों के ठीक समान हैं।
एक अक्षर में संख्यात्मक (फ़ोल्डर, तिथि, आकार, चेक बॉक्स, अनुलग्नकों की उपस्थिति, आदि) और पाठ (विषय, प्रेषक, पाठ, आदि) क्षेत्रों का एक विशिष्ट सेट होता है। ज़ोन की सूची एक विशेष फ़ाइल में कॉन्फ़िगर की गई है और इसे खोज प्रणाली के संचालन के दौरान पूरक किया जा सकता है।
स्नैपशॉट में दो भाग होते हैं - एक डिक्शनरी (सभी शब्दों की एक सूची जो अक्षरों में दिखाई देती है, और पॉइंटर्स (ऑफ़सेट)) और डिक्शनरी द्वारा पॉइंटर्स द्वारा संदर्भित वास्तव में दस्तावेजों (और ज़ोन) की सूची। खोज करते समय, शब्दकोश पढ़ा जाता है, जिसमें खोज क्वेरी में शामिल शब्द होते हैं, जिसके बाद शब्दकोश से प्राप्त संकेतों के अनुसार दस्तावेजों की सूचियों को पढ़ा जाता है; परिणाम संयुक्त हैं। औसतन, एक शब्द के लिए खोज क्वेरी (केवल स्नैपशॉट का उपयोग करके) को दो डिस्क एक्सेस की आवश्यकता होती है - एक शब्दकोश पढ़ने और दस्तावेजों की एक सूची पढ़ने के लिए।
Xlog में क्रमिक रूप से रिकॉर्ड किए गए लेनदेन होते हैं। प्रत्येक लेनदेन की अखंडता को इसकी सामग्री के एक चेकसम (CRC32) द्वारा गारंटी दी जाती है। Xlog पढ़ते समय, सभी लेनदेन जिनके लिए चेकसम मेल नहीं खाता था, उन्हें छोड़ दिया जाता है (हालाँकि, पढ़ने की प्रक्रिया तब तक बाधित नहीं होती है जब तक कि त्रुटियों की संख्या कॉन्फ़िगरेशन फ़ाइल में निर्धारित संख्या से अधिक न हो)। एक लेनदेन, एक नियम के रूप में, कई टीमों के होते हैं और हमेशा बिल्कुल एक अक्षर का वर्णन करते हैं। मुख्य भूमिका टीम द्वारा खेला जाता है, शब्द है कि इस पत्र में मौजूद हैं की सूची का वर्णन, और पाठ क्षेत्रों की संख्या में वे होते हैं। xlog पर एक खोज प्रश्न का निष्पादन, स्मृति और सभी लेनदेन के विश्लेषण में पूरे फ़ाइल को पढ़ने की आवश्यकता है, इसलिए आकार xlog गंभीर रूप से सीमित कर दिया। ज़्लॉग और स्नैपशॉट पर क्वेरी निष्पादन के परिणाम एक सामान्य परिणाम में संयुक्त होते हैं।
एक बार पत्र जिसमें क्वेरी के शब्दों देखते हैं की सूची तैयार की, उनके लिए सभी संख्यात्मक क्षेत्रों के मूल्यों प्राप्त करता है। न्यूमेरिक ज़ोन मान nzdata फ़ाइल में संग्रहीत हैं। फ़ाइल संरचना स्नैपशॉट की संरचना के समान है - यह एक ऐसा शब्दकोश है जिसमें सभी अक्षरों और बिंदुओं की संख्या होती है जो इस पत्र के संख्यात्मक क्षेत्रों के मूल्यों की सूची को संदर्भित करते हैं। हालाँकि, यह फ़ाइल पूरी तरह से मेमोरी में पढ़ी जाती है क्योंकि स्नैपशॉट के विपरीत इसके अंदर डेटा की संख्या बड़ी है, और फ़ाइल स्वयं बहुत छोटी है। ध्यान दें कि nzdata में संख्यात्मक क्षेत्रों के सभी प्रासंगिक मूल्य शामिल नहीं हैं। उन्होंने कहा कि, का एक स्नैपशॉट की तरह, एक निश्चित समय पर क्षेत्र के संख्यात्मक मान हैं, और बाद के सभी संशोधनों xlog में निहित। स्नैपशॉट के रूप में एक ही समय में पुनर्निर्माण nzdata किया जाता है। सभी संख्यात्मक क्षेत्रों को लोड करने के बाद, दूसरा xlog पढ़ा जाता है और संख्यात्मक क्षेत्रों में परिवर्तन का वर्णन करने वाले सभी आदेशों को लोड किए गए परिणामों पर लागू किया जाता है। हम यह भी ध्यान देते हैं कि खोज डेमॉन, नजदता की ओर मुड़ने से पहले, डेमॉन से संख्यात्मक क्षेत्र प्राप्त करने की कोशिश करता है जो डाक कोड के साथ काम प्रदान करता है (जो कि बॉक्स में सक्रिय रूप से काम करने पर मेमोरी में कैश किया जाता है)। यह विधि कई गुना तेज है और डेटा स्थिरता सुनिश्चित करती है। Nzdata से संख्यात्मक क्षेत्र प्राप्त करना, वास्तव में, केवल आपातकालीन स्थितियों में होता है।
संख्यात्मक क्षेत्र प्राप्त करने के बाद, खोज डेमॉन क्वेरी में निर्दिष्ट फ़िल्टर लागू करना शुरू कर देता है। फिल्टर संख्यात्मक क्षेत्रों के प्रतिबंध हैं: "बराबर", "बराबर नहीं", "अधिक", आदि। सबसे लोकप्रिय फिल्टर तिथि पर प्रतिबंध ("कल", "प्रति सप्ताह"), फ़ोल्डर पर ("इनबॉक्स") , "भेजा गया", "स्पैम में नहीं"), किसी भी ध्वज ("अपठित", "ध्वजांकित", "संलग्नक के साथ")। परिणाम की सूची से प्रत्येक अक्षर में क्रमिक रूप से फिल्टर लगाए जाते हैं और वहां से कुछ अक्षरों को बाहर कर देते हैं।
एक ही चरण में, ग्रुपर्स का उपयोग किया जाता है जो यह गणना करता है कि "ऐसे फ़िल्टर लागू किए जाने पर कितने परिणाम होंगे"।
अगला चरण रैंकिंग है। मेल खोज के मामले में, अन्य पूर्ण-पाठ खोज कार्यों के विपरीत, सबसे प्रासंगिक रैंकिंग फ़ंक्शन स्पष्ट और सरल है - यह पत्र की तिथि के अनुसार क्रमबद्ध है। रैंकिंग उन पत्रों को काटकर समाप्त होती है जो वर्तमान पृष्ठ में नहीं आते हैं (SQL में लिमाइट ऑपरेशन के समान)।
खोज परिणाम बनाने के लिए, संख्यात्मक क्षेत्र अकेले हैं। चूँकि सबसे अधिक बार रैंकिंग करने के बाद भी 25 से अधिक अक्षर नहीं रहते हैं (एक पृष्ठ पर प्रदर्शित पत्रों की मानक संख्या), इस स्तर पर टेक्स्ट ज़ोन को लोड करने और संसाधित करने के भारी संचालन होते हैं। लोड करने के बाद, प्रत्येक पाठ क्षेत्र को शब्दों में विभाजित किया जाता है, जिसके बीच खोज क्वेरी में मौजूद लोगों को हाइलाइट किया जाता है (शब्द रूपों और मामले असंवेदनशील के संबंध में)। इन शब्दों को <b> और </ b> टैग के साथ "हाइलाइट किया गया" है, और पाठ क्षेत्र खुद को एक निश्चित आकार के बाईं और दाईं ओर काट दिया जाता है, जिसे पहले चयनित शब्द को शामिल करने की गारंटी है।
Sjest इंडेक्स स्नैपशॉट में xlog के पुनर्निर्माण के समय बनाया गया है। अनुरोध की लंबाई की गणितीय अपेक्षा 6 वर्ण है।
सुगम सूचकांक उन शब्दों को संग्रहीत करता है जो उस पत्र में पहले रूप में कम नहीं होते हैं जिसमें वे पत्र में होते हैं। सुगम सूचकांक में दो भाग होते हैं:
1. एक शब्द जिसमें उपसर्ग शामिल हैं (6 वर्ण तक लंबे)। 6 वर्णों से अधिक लंबे शब्दों के लिए, शब्दकोश पोस्टफ़िक्स सूचियों के लिंक को संग्रहीत करता है।
2. उपसर्गों की बहुत सारी सूची (मनमानी लंबाई की)।
अनुभव यह पाया गया है कि सूचकांक sadzhestov उपसर्ग लंबाई के निर्माण के 6 प्रतीकों इसके आकार को कम करता है। यह खोज सूचकांक के विपरीत, सबसे सुस्पष्ट सूचकांक को कैश करने के लिए समझ में आता है, लेकिन इसे अपेक्षाकृत कम समय के लिए स्मृति में रखें, क्योंकि उपयोगकर्ताओं के लिए कई अक्षरों में तब तक प्रवेश करना आम है जब तक कि वे सैगेस्ट के मुद्दे से संतुष्ट नहीं होते हैं। अब तक उपसर्ग (पूरा) और सभी पढ़ने की सूची कैश्ड डिस्क सूचियों प्रत्यय से। सेस्ट जनरेट करते समय xlog से डेटा का उपयोग नहीं किया जाता है, क्योंकि xlog को पढ़ने में काफी समय लग सकता है। इसलिए, सुगेस्ट इंडेक्स हमेशा बॉक्स की वास्तविक स्थिति से थोड़ा "पीछे" होता है। अगले पुनर्निर्माण स्नैपशॉट के दौरान sagest सूचकांक xlog से डेटा के साथ फिर से भर दिया जाता है।
यदि आपके पास कार्यान्वयन के बारे में प्रश्न हैं या इस तरह की समस्या को हल करने में अनुभव है - तो हमारे सर्वोत्तम प्रथाओं को साझा करें।
दिमित्री कलुगिन-बालाशोव,
प्रोग्रामर मेल.रु मेल टीम