प्रॉम्प्ट और संदर्भ
यह कॉलमर-मेमोरी-फ़ॉर्मेट और निष्पादन-इंजन निर्णय से जुड़ा प्रश्न है। Apache Arrow Run-End Encoding (REE) क्रमिक समान मानों के एक लॉजिकल ऐरे को बढ़ते हुए run ends और एक मैचिंग values ऐरे के साथ दर्शाता है; पैरेंट ऐरे में कोई स्वतंत्र डेटा बफ़र नहीं होते हैं। परीक्षण इस बात का है कि क्या आप हर जगह कम्प्रेशन सक्षम करने के बजाय डेटा वितरण के आधार पर रिप्रजेंटेशन चुनते हैं।
मान लें कि कॉलम कई प्रोग्रामिंग भाषाओं के इम्प्लीमेंटेशन्स में उपयोग होता है और पाठकों (readers) को स्लाइसिंग, फ़िल्टरिंग, एग्रीगेशन और रैंडम पोज़ीशन रीड्स की आवश्यकता होती है। कुछ सीक्वेंस हज़ारों पंक्तियों तक एक ही स्टेटस रखते हैं; अन्य लगभग हर पंक्ति में बदलते हैं। आपको एन्कोडिंग का चयन, मापन मानदंड (measurement gate), डिकोडिंग सीमा और परिणाम सत्यापन निर्दिष्ट करना होगा।
इंटरव्यूअर क्या मूल्यांकन करता है
- यह समझाना कि run end एक लॉजिकल पोज़ीशन है, न कि run length, जबकि values-to-runs संबंध सुरक्षित रहता है।
- आसन्न दोहराव (adjacent repetition), गैर-आसन्न दोहराव और रैंडम एक्सेस के लिए REE, एक फ़्लैट ऐरे और डिक्शनरी एन्कोडिंग की तुलना करना।
- Nulls, स्लाइस, कॉनकेटनेशन, फ़िल्टरिंग और भाषा इम्प्लीमेंटेशन्स के बीच अंतर को संभालना।
- एन्कोडिंग चयन को एक सुरक्षित फ़ॉलबैक के साथ एक मापने योग्य नीति में बदलना।
- मेमोरी बचत, डिकोड CPU, कैश लोकैलिटी और एंड-टू-एंड क्वेरी लेटेंसी को अलग-अलग करके देखना।
स्पष्टीकरण के लिए प्रश्न
- रन-लेंथ वितरण, वैल्यू प्रकार और null दर क्या है? यह निर्धारित करता है कि क्या run ends लॉजिकल पंक्तियों की तुलना में बहुत कम हैं।
- क्या वर्कलोड सीक्वेंशियल स्कैन है, रैंडम पोज़ीशन रीड्स है, या कई स्लाइस और फ़िल्टर हैं? एक्सेस पैटर्न इंडेक्स लागत निर्धारित करता है।
- क्या निर्माण के बाद डेटा अक्सर संशोधित (mutate) होता है या केवल पढ़ने के लिए (read-only) है? Arrow पढ़ने और डेटा विनिमय का समर्थन करता है; इन-प्लेस बार-बार म्यूटेशन ट्रेड-ऑफ को बदल देता है।
- क्या सभी उपभोक्ता REE का समर्थन करते हैं? यदि नहीं, तो क्या हम सीमा पर डिकोड करते हैं या उस भौतिक एन्कोडिंग को अस्वीकार करते हैं?
- मेमोरी बजट या लेटेंसी SLO में से कौन सा अधिक सख्त है? केवल कंप्रेस्ड बाइट्स के आधार पर डिज़ाइन नहीं चुना जा सकता।
30-सेकंड का उत्तर
"मैं पहले रन काउंट और लंबाई वितरण को मापूंगा। लंबे रन, सीक्वेंशियल स्कैन और मेमोरी का दबाव REE के पक्ष में हो सकते हैं क्योंकि कम मान और run ends प्रोसेस होते हैं। अत्यधिक बदलने वाला डेटा या भारी रैंडम एक्सेस एक फ़्लैट ऐरे के पक्ष में होता है; गैर-आसन्न दोहराव डिक्शनरी एन्कोडिंग के पक्ष में हो सकता है। यह रिप्रजेंटेशन लॉजिकल लंबाई, बढ़ते run ends, मान और null सेमांटिक्स को बनाए रखता है, जबकि एक नियंत्रित इंडेक्स हॉट रैंडम रीड्स को पूरा कर सकता है। मैं मेमोरी, p95 लेटेंसी और CPU के लिए वास्तविक स्लाइस, फ़िल्टर और एग्रीगेट्स का बेंचमार्क करूंगा, और फिर रन अनुपात या उपभोक्ता क्षमता के मानदंड विफल होने पर फ़ॉलबैक करूंगा।"
चरण-दर-चरण समाधान
चरण 1: लॉजिकल और फिजिकल मॉडल परिभाषित करें
प्रत्येक लॉजिकल पोज़ीशन उस मान से संबंधित होती है जो उस पोज़ीशन से बड़े पहले run end से जुड़ा होता है। Run ends बढ़ते क्रम में होते हैं, अंतिम run end लॉजिकल लंबाई के बराबर होता है, और values की संख्या पंक्ति संख्या के बजाय रन संख्या के बराबर होती है। Nulls, values-ऐरे सेमांटिक्स का हिस्सा हैं; उन्हें किसी अलग "null run" नियम की आवश्यकता नहीं है।
उदाहरण के लिए, लॉजिकल मान A A A B B C C C C, run ends 3, 5, 9 और values A, B, C का उपयोग कर सकते हैं। यह लेआउट को दर्शाता है और प्रत्येक इम्प्लीमेंटेशन के सटीक मेमोरी आकार का दावा नहीं है।
चरण 2: वितरण के अनुसार चुनें
लॉजिकल लंबाई N और रन काउंट R के लिए, REE का मुख्य डेटा आकार R और values के प्रकार पर निर्भर करता है; एक फ़्लैट ऐरे N के साथ स्केल करता है। जब R, N से बहुत कम होता है, तो मेमोरी और स्कैन वॉल्यूम कम हो सकते हैं। जब मान लगातार बदलते हैं, तब भी REE कई रन बनाता है। जब समान मान अलग-अलग होते हैं, तो डिक्शनरी एन्कोडिंग मान साझा करती है लेकिन फिर भी प्रति पंक्ति एक इंडेक्स स्टोर करती है।
प्रत्येक प्रकार पर एक ही कम्प्रेशन अनुपात लागू न करें। रन ends, values, बिटमैप्स, अलाइनमेंट और डिकोड लागत सहित स्ट्रिंग्स, विस्तृत संरचनाओं और अधिक null वाले कॉलम को अलग से मापें। कम कार्डिनैलिटी का अर्थ लंबे रन नहीं होता है, और उच्च कार्डिनैलिटी स्थानीय लंबे रन को समाप्त नहीं करती है।
चरण 3: रैंडम एक्सेस, स्लाइसिंग और कॉनकेटनेशन को संभालें
एक फ़्लैट ऐरे किसी पोज़ीशन को सीधे संबोधित करता है। REE बढ़ते run ends में रन का पता लगाता है; एक इम्प्लीमेंटेशन लीनियर स्कैन, कैश या बाइनरी सर्च का उपयोग कर सकता है, इसलिए लागत लाइब्रेरी और एक्सेस पैटर्न पर निर्भर करती है। लंबे रन और सीक्वेंशियल स्कैन कर्सर के अनुकूल होते हैं। हॉट रैंडम रीड्स अतिरिक्त मेमोरी लागत पर एक स्पार्स इंडेक्स का उपयोग कर सकते हैं।
एक स्लाइस को लॉजिकल लंबाई और सीमा सेमांटिक्स को बनाए रखना चाहिए। इसकी शुरुआत किसी रन के बीच में हो सकती है, इसलिए पहले आउटपुट रन को एक सापेक्ष सीमा की आवश्यकता होती है; मूल run ends को केवल पुन: उपयोग नहीं किया जा सकता है। दो REE ऐरे को संयोजित (concatenate) करने के लिए समान आसन्न सीमा मानों को मर्ज करना और यह जांचना आवश्यक है कि अंतिम लॉजिकल पोज़ीशन निरंतर है।
चरण 4: Null और कम्प्यूट सेमांटिक्स तय करें
Arrow निर्दिष्ट करता है कि पैरेंट-ऐरे nulls को पूरी तरह से values ऐरे में दर्शाया जाता है। आसन्न nulls एक एकल null मान का उपयोग करते हैं; बदलते हुए null और गैर-null मान रन काउंट को बढ़ाते हैं। फ़िल्टरिंग, तुलना और एग्रीगेशन के लिए स्पष्ट null प्रोपेगेशन की आवश्यकता होती है; null को एक सामान्य स्ट्रिंग के रूप में डिकोड करने से परिणाम बदल जाते हैं।
एक इंजन उस ऑपरेशन को ऑप्टिमाइज़ कर सकता है जो प्रति रन एक बार लागू होता है, जैसे कि काउंट या इंटरवल संचय, लेकिन उसे यह सत्यापित करना होगा कि क्या फ़ंक्शन पंक्ति क्रम पर निर्भर करता है। एक ऑपरेटर जो प्रति पंक्ति एक परिणाम देता है, वह डिकोडेड या कर्सर व्यू के साथ अधिक सरल हो सकता है। प्रत्येक ऑप्टिमाइज़ेशन को लॉजिकल फ़्लैट परिणाम के विरुद्ध जाँचा जाना चाहिए।
चरण 5: क्रॉस-लैंग्वेज और फ़ॉलबैक सीमाएं परिभाषित करें
Arrow क्रॉस-लैंग्वेज है, लेकिन समर्थित कम्प्यूट फ़ंक्शंस और ज़ीरो-कॉपी पाथ इम्प्लीमेंटेशन के आधार पर भिन्न होते हैं। एक्सचेंज सीमा को फिजिकल प्रकार, लॉजिकल लंबाई, run-end प्रकार, null सेमांटिक्स और क्या डिकोडिंग की अनुमति है, यह घोषित करना चाहिए। यदि किसी उपभोक्ता में REE समर्थन की कमी है, तो प्रत्येक व्यावसायिक उपभोक्ता को आधे-अधूरे नियम लागू करने के लिए मजबूर करने के बजाय सीमा पर एक बार डिकोड करें।
प्रेषक कॉलम सांख्यिकी से REE चुन सकता है या दोनों फिजिकल रूपों को कैश कर सकता है। केवल एक डिकोड से बचने के लिए प्रत्येक ऑपरेटर में REE शाखा जोड़ने से बचें। एक उच्च-रैंडम-एक्सेस क्वेरी, असमर्थित उपभोक्ता, या उच्च रन अनुपात फ़्लैट रिप्रजेंटेशन का उपयोग करने का एक मजबूत कारण है।
चरण 6: वास्तविक वर्कलोड के साथ मानदंड (Gates) निर्धारित करें
कम से कम चार बेंचमार्क बनाएं: लॉन्ग-रन सीक्वेंशियल स्कैन, अल्टरनेटिंग-वैल्यू स्कैन, रैंडम पोज़ीशन रीड्स, और स्लाइस-देन-एग्रीगेट। पीक मेमोरी, डिकोड CPU, कैश-मिस प्रॉक्सी, p50/p95 लेटेंसी और आउटपुट सत्यापन रिकॉर्ड करें। वैल्यू की चौड़ाई, null दर और बैच आकार के अनुसार विभाजित करें ताकि एक छोटा नमूना कम्प्रेशन लाभ को बढ़ा-चढ़ाकर न दिखाए।
रन-अनुपात सैंपलिंग नीति के साथ शुरुआत करें और क्वेरी-लेटेंसी फ़ीडबैक का उपयोग करके इसे परिष्कृत करें। यदि REE मेमोरी बचत लक्ष्य से चूक जाती है या रैंडम-रीड p95 बजट से अधिक हो जाता है, तो फ़्लैट ऐरे पर वापस आ जाएं। फ़ॉलबैक स्कीमा, लॉजिकल लंबाई और null परिणामों को सुरक्षित रखता है और दोबारा चलाने (replay) के लिए एन्कोडिंग संस्करण रिकॉर्ड करता है।
डिज़ाइन ट्रेड-ऑफ़ और सीमाएं
#### REE बनाम फ़्लैट ऐरे
REE लंबे आसन्न रन और मेमोरी-बाधित स्कैन के लिए उपयुक्त है। एक फ़्लैट ऐरे रैंडम एक्सेस, सरल SIMD और व्यापक उपभोक्ता समर्थन के लिए उपयुक्त है। फ़ॉर्मेट प्राथमिकता के बजाय R/N, एक्सेस पैटर्न और एंड-टू-एंड मेट्रिक्स के आधार पर चुनें।
#### REE बनाम डिक्शनरी एन्कोडिंग
REE आसन्न दोहराव को कंप्रेस करता है; डिक्शनरी एन्कोडिंग गैर-आसन्न दोहराव को कंप्रेस करती है लेकिन प्रति पंक्ति एक इंडेक्स बनाए रखती है। एक कॉलम मानों को डिक्शनरी-एन्कोड कर सकता है और फिर आसन्न इंडेक्स को REE-एन्कोड कर सकता है, लेकिन यह संयोजन कार्यान्वयन और परीक्षण जटिलता को बढ़ाता है और इसका उपयोग केवल तभी किया जाना चाहिए जब बेंचमार्क इसे सही ठहराते हों।
#### एक बार डिकोड करना बनाम कंप्रेस्ड रखना
एक बार डिकोड करने से कई ऑपरेटर सरल हो जाते हैं और रैंडम रीड्स में सुधार होता है लेकिन मेमोरी का पीक बनता है। कम्प्रेशन बनाए रखने से मेमोरी की बचत होती है लेकिन ऑपरेटरों को रन सीमाओं को समझने की आवश्यकता होती है। क्वेरी योजना के अनुसार चुनें और आवश्यकता पड़ने पर हॉट कॉलम के लिए एक अल्पकालिक फ़्लैट कैश को मटीरियलाइज़ करें।
मॉडल उत्तर
"मैं पहले R/N और रन-लेंथ वितरण को मापूंगा, फिर स्कैन, रैंडम-रीड और स्लाइस अनुपात का निरीक्षण करूंगा। लंबे रन, सीक्वेंशियल स्कैन और मेमोरी का दबाव REE के पक्ष में हैं: बढ़ते run ends लॉजिकल सीमाओं को परिभाषित करते हैं और values प्रति रन एक मान संग्रहीत करता है, जिसमें values में null सेमांटिक्स सुरक्षित रहता है। भारी रैंडम एक्सेस या एक के करीब रन अनुपात एक फ़्लैट ऐरे के पक्ष में होता है; गैर-आसन्न दोहराव डिक्शनरी तुलना का हकदार है। रन के अंदर से शुरू होने वाले स्लाइस को सापेक्ष सीमाओं की आवश्यकता होती है, और कॉनकेटनेशन समान सीमा रन को मर्ज करता है। मैं मेमोरी, CPU और p95 के लिए लंबे रन, अल्टरनेटिंग मान, रैंडम रीड्स और एग्रीगेट्स का बेंचमार्क करूंगा, फिर लॉजिकल परिणामों को समान रखते हुए किसी उपभोक्ता या SLO के विफल होने पर सीमा पर डिकोड करूंगा।"
सामान्य गलतियाँ
- Run ends को run lengths मानना → पोज़ीशन लुकअप और स्लाइस सीमाएं गलत हो जाती हैं → स्पष्ट करें कि प्रत्येक मान एक लॉजिकल एंड पोज़ीशन तक मान्य है।
- कार्डिनैलिटी कम होने पर हमेशा REE चुनना → समान मान आसन्न नहीं हो सकते हैं, जिससे रन संख्या N के करीब रह जाती है → समीपता (adjacency) और एक्सेस पैटर्न को मापें।
- Values में null सेमांटिक्स को अनदेखा करना → डिकोडिंग से null काउंट या एग्रीगेट्स बदल जाते हैं → Arrow पैरेंट-ऐरे null नियम का परीक्षण करें।
- स्लाइस के लिए मूल run ends का पुन: उपयोग करना → सापेक्ष लंबाई और पहली सीमा गलत हो जाती है → स्लाइस सीमाओं और लॉजिकल लंबाई की पुनर्गणना करें।
- केवल कंप्रेस्ड मेमोरी की रिपोर्ट करना → डिकोड CPU, रैंडम रीड्स या उपभोक्ता समर्थन हावी हो सकते हैं → एंड-टू-एंड वर्कलोड और p95 पर मानदंड निर्धारित करें।
फॉलो-अप और उत्तर
क्या REE तब उपयोगी है जब प्रत्येक मान अलग हो?
आमतौर पर नहीं। जब R, N के करीब पहुंचता है, तो run ends सीमा स्टोरेज जोड़ते हैं और रैंडम एक्सेस अधिक जटिल हो जाता है, इसलिए फ़्लैट ऐरे का उपयोग करें। केवल सैद्धांतिक बाइट्स पर निर्भर रहने के बजाय वास्तविक वैल्यू प्रकार और बैच आकार के साथ मापें।
जब कोई स्लाइस एक लंबे रन के अंदर शुरू होता है तो आप सटीकता कैसे बनाए रखते हैं?
शुरुआत वाले रन को ढूंढें, इसे शून्य से शुरू होने वाली सापेक्ष सीमा में ट्रिम करें, बाद के run ends से स्लाइस की शुरुआत को घटाएं, और अंतिम छोर को स्लाइस की लंबाई के बराबर बनाएं। फ़्लैट डिकोडिंग के साथ तुलना करें और खाली व सीमा से बाहर के स्लाइस का परीक्षण करें।
एक एग्रीगेशन प्रत्येक रन को प्रत्येक पंक्ति में डिकोड करने से कैसे बच सकता है?
यदि यह केवल मान और अंतराल की लंबाई पर निर्भर करता है, तो रन स्तर पर गणना करें, जैसे कि किसी मान को उसकी रन लंबाई से गुणा करना और संचय करना। यदि यह पंक्ति क्रम, विंडो या पंक्ति प्रेडिकेट पर निर्भर करता है, तो कर्सर या डिकोडेड व्यू का उपयोग करें। Null और ओवरफ़्लो नियमों के साथ प्रत्येक ऑप्टिमाइज़ेशन को मान्य करें।
REE समर्थन की कमी वाले रिमोट उपभोक्ता के लिए कौन डिकोड करता है?
प्रेषक या साझा Arrow एडेप्टर फ़ॉर्मेट सीमा पर डिकोड करता है और भौतिक रिप्रजेंटेशन परिवर्तन की घोषणा करता है। उपभोक्ताओं को स्वतंत्र रूप से run ends का अनुमान नहीं लगाना चाहिए। डिकोड काउंट और विस्तारित मेमोरी रिकॉर्ड करें, और आवश्यकता पड़ने पर अनुकूलता उपभोक्ताओं के लिए एक फ़्लैट कैश प्रदान करें।