कोडिंग इंटरव्यू: एक्सपायरेशन के साथ TTL कैश को लागू करना

प्रश्न और यह कब लागू होता है

एक इन-मेमोरी कैश लागू करें जहाँ प्रत्येक की (key) का एक मान (value) और एक एक्सपायरेशन समय हो। get को कभी भी एक्सपायर हो चुका मान वापस नहीं करना चाहिए। क्लॉक, बाउंड्री, क्लीनअप, कैपेसिटी, कॉनकरेंसी और कॉम्प्लेक्सिटी की व्याख्या करें।

Amazon सॉफ्टवेयर-डेवलपमेंट इंटरव्यू विषयों में डेटा स्ट्रक्चर, एल्गोरिदम और कोडिंग को सूचीबद्ध करता है और ज्ञान को लागू करने पर जोर देता है। Redis शेष लाइफटाइम और प्रिसिजन सहित TTL और EXPIRE सेमेंटिक्स का दस्तावेजीकरण करता है। LRU या LFU के विपरीत, यह समस्या समय के सेमेंटिक्स और एक्सपायरेशन क्लीनअप पर केंद्रित है।

इंटरव्यूअर्स क्या आंकते हैं

इंटरव्यूअर्स एक स्पष्ट TTL यूनिट और क्लॉक, एक सही एक्सपायरेशन बाउंड्री, क्लीनअप विकल्प, कॉनकरेंट कंसिस्टेंसी, कैपेसिटी व्यवहार, और टाइम और स्पेस कॉम्प्लेक्सिटी की जांच करते हैं।

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

• क्या TTL सेकंड में है या मिलीसेकंड में? क्या शून्य तुरंत एक्सपायर हो जाता है?
• क्या क्लॉक मोनोटोनिक (monotonic) है?
• क्या एक्सपायर हो चुकी एंट्रियों को तुरंत हटाया जाना चाहिए?
• क्या कोई अधिकतम कैपेसिटी या LRU पॉलिसी है?
• set, get और क्लीनअप कैसे सिंक्रोनाइज़ होते हैं?
• क्या किसी की (key) को अपडेट करने से TTL रीसेट होता है?
• क्या पर्सिस्टेंस या क्रॉस-प्रोसेस शेयरिंग आवश्यक है?
• क्या क्लीनअप कार्य बाउंडेड (bounded) होना चाहिए?

30-सेकंड उत्तर ढांचा

“मैं प्रत्येक की (key) के मान और एब्सोल्यूट expiresAt को एक हैश टेबल में स्टोर करता हूँ। get पहले मोनोटोनिक क्लॉक की जांच करता है; यदि now, expiresAt के बराबर या उसके बाद है, तो यह उसे डिलीट करता है और एक मिस (miss) लौटाता है। set मान और TTL को बदल देता है। बेसिक वर्शन अमॉर्टाइज़्ड O(1) get और O(n) स्पेस के साथ लेज़ी (lazy) क्लीनअप का उपयोग करता है। एक मिन-हीप (min-heap) या बाउंडेड स्कैन कोल्ड एंट्रियों को संभालता है। लॉक्स या शार्डिंग हैश और क्लीनअप अपडेट की सुरक्षा करते हैं। टेस्ट ज़ीरो TTL, इक्वलिटी, रिफ्रेश और रेस कंडीशंस को कवर करते हैं।”

गहन उत्तर, चरण-दर-चरण

चरण 1: आइटम को परिभाषित करें

value और expiresAt स्टोर करें; कोई भी TTL इनफिनिटी का उपयोग नहीं कर सकता। हर पाथ पर एक ही नियम, now >= expiresAt, का उपयोग करें।

चरण 2: get और set को लागू करें

get किसी अनुपस्थित की (key) के लिए मिस लौटाता है। एक्सपायर हो चुकी की के लिए, यह मिस लौटाने से पहले उसे डिलीट करता है। set एक एब्सोल्यूट एक्सपायरी की गणना करता है और किसी भी क्लीनअप इंडेक्स को अपडेट करता है।

चरण 3: एक क्लॉक चुनें

बीते हुए समय के लिए एक मोनोटोनिक क्लॉक का उपयोग करें ताकि वॉल-क्लॉक एडजस्टमेंट TTL को बढ़ा न सकें। पर्सिस्टेंस और क्रॉस-प्रोसेस डिज़ाइनों के लिए एक स्पष्ट टाइम बेसिस और प्रिसिजन की आवश्यकता होती है।

चरण 4: क्लीनअप रणनीति चुनें

लेज़ी क्लीनअप सरल है लेकिन कोल्ड कीज़ मेमोरी की खपत कर सकती हैं। एक मिन-हीप सबसे प्रारंभिक एक्सपायरी को पहले निकालता है; समय-समय पर किए जाने वाले स्कैन काम को सीमित (bound) करते हैं लेकिन डिलीशन में देरी कर सकते हैं।

चरण 5: अपडेट को कॉनकरेंट-सुरक्षित बनाएं

set, get, delete और क्लीनअप को एक ही मान और एक्सपायरी पर सहमत होना चाहिए। एक ग्लोबल लॉक, रीड-राइट लॉक या शार्डेड लॉक्स का उपयोग करें। हीप और टेबल का अपडेट एक साथ अटॉमिक होना चाहिए।

चरण 6: कैपेसिटी को TTL से अलग करें

TTL कैपेसिटी को परिभाषित नहीं करता है। सीमा पर, LRU, रैंडम एविक्शन (eviction), या राइट्स को अस्वीकार करने का विकल्प चुनें। एक्सपायरेशन से अलग एविक्शन को ट्रैक करें।

चरण 7: कॉम्प्लेक्सिटी और स्यूडोकोड बताएं

कोर बाउंड्री है:

get(key):
  item = table[key]
  if item is absent: return MISS
  if clock.now() >= item.expiresAt:
    delete table[key]
    return MISS
  return item.value

लेज़ी get और set अमॉर्टाइज़्ड O(1) हैं, स्पेस O(n) है। हीप क्लीनअप पॉप की लागत O(log n) होती है।

चरण 8: बाउंड्रीज़ का परीक्षण करें

ज़ीरो TTL, इक्वलिटी, रिफ्रेश, बार-बार क्लीनअप, क्लॉक परिवर्तन, कॉनकरेंट get/set, कैपेसिटी एविक्शन और इंजेक्टेड विफलताओं का परीक्षण करें। टेस्ट में स्लीप (sleep) करने के बजाय क्लॉक को इंजेक्ट करें।

उच्च-गुणवत्ता वाला नमूना उत्तर

“मैं CacheItem(value, expiresAt) को परिभाषित करता हूँ और आइटम्स को हैश टेबल में स्टोर करता हूँ। set, TTL को एक एब्सोल्यूट एक्सपायरी में बदलता है; शून्य का अर्थ है तुरंत एक्सपायर होना। get एक मोनोटोनिक क्लॉक की जांच करता है और मिस लौटाने से पहले डिलीट करता है।

पहला वर्शन अमॉर्टाइज़्ड O(1) रीड और राइट के साथ लेज़ी क्लीनअप का उपयोग करता है। कई कोल्ड कीज़ के लिए मैं एक मिन-हीप जोड़ता हूँ। प्रत्येक हीप रिकॉर्ड का एक वर्शन होता है; क्लीनअप डिलीट करने से पहले वर्शन को मान्य करता है, ताकि कोई पुराना रिकॉर्ड किसी रिफ्रेश किए गए मान को न हटा सके। शार्डेड लॉक्स टेबल और हीप की सुरक्षा करते हैं। टेस्ट इक्वलिटी, रिफ्रेश, बार-बार क्लीनअप, रेस कंडीशंस और कैपेसिटी एविक्शन को कवर करते हैं।”

सामान्य गलतियाँ

• ज़ीरो TTL और इक्वलिटी को अपरिभाषित छोड़ना।
• बीते हुए TTL के लिए वॉल-क्लॉक समय का उपयोग करना।
• जब तक कोई बैकग्राउंड वर्कर नहीं चलता, तब तक get को एक्सपायर हो चुका मान लौटाने देना।
• रिफ्रेश के बाद हीप के पुराने (stale) रिकॉर्ड्स को अनदेखा करना।
• TTL को LRU कैपेसिटी पॉलिसी की तरह मानना।
• लंबे क्लीनअप के दौरान ग्लोबल लॉक को बनाए रखना।
• केवल हिट्स और मिसेस का परीक्षण करना, बाउंड्री रेस कंडीशंस का नहीं।
• प्रिसिजन और कॉम्प्लेक्सिटी को छोड़ देना।

फॉलो-अप प्रश्न और उनके उत्तर कैसे दें

फॉलो-अप 1: एब्सोल्यूट एक्सपायरी ही क्यों?

यह एक तुलना नियम प्रदान करता है और क्लीनअप को एक्सपायरी के आधार पर एंट्रियों को क्रमबद्ध करने की अनुमति देता है। रिफ्रेश expiresAt को बदल देता है।

फॉलो-अप 2: क्या होगा यदि वॉल क्लॉक पीछे चली जाए?

बीते हुए समय के लिए एक मोनोटोनिक क्लॉक का उपयोग करें। एक पर्सिस्टेंट या डिस्ट्रीब्यूटेड कैश को एक प्रलेखित (documented) टाइम बेसिस की आवश्यकता होती है।

फॉलो-अप 3: कोई बैकग्राउंड थ्रेड नहीं है, लेकिन कई कोल्ड कीज़ हैं?

रीड्स या राइट्स के दौरान बाउंडेड क्लीनअप करें, जैसे कि प्रति ऑपरेशन हीप पॉप की एक निश्चित संख्या, और डिलीशन में होने वाली एक सीमित देरी को स्वीकार करें।

फॉलो-अप 4: आप हीप और टेबल को कैसे कंसिस्टेंट रखते हैं?

एक लॉक या अटॉमिक ऑपरेशन और हीप रिकॉर्ड्स पर एक वर्शन का उपयोग करें। केवल तभी डिलीट करें जब वर्शन अभी भी मेल खाता हो।

फॉलो-अप 5: कैपेसिटी पूरी होने पर क्या होता है?

पहले एक्सपायर हो चुकी एंट्रियों को हटाएं, फिर लाइव एंट्रियों पर प्रलेखित एविक्शन पॉलिसी लागू करें और कारण को ट्रैक करें।

फॉलो-अप 6: कई प्रोसेस इसे कैसे शेयर करते हैं?

एक इन-मेमोरी कैश सिंगल-प्रोसेस होता है। क्रॉस-प्रोसेस उपयोग के लिए अटॉमिक TTL, क्लॉक और विफलता सेमेंटिक्स के साथ एक बाहरी या डिस्ट्रीब्यूटेड स्टोर की आवश्यकता होती है।