नैनोसेकंड timestamp टकराव आम हैं

 (evanjones.ca)
5 पॉइंट द्वारा GN⁺ 2023-07-23 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • कई physical cores पर एक साथ clock पढ़ने वाले आधुनिक systems में नैनोसेकंड timestamp भी आसानी से टकरा जाते हैं, और 4 physical cores पर एक साथ मापने में कुल samples का लगभग 5% टकराया
  • raw timestamp को unique identifier की तरह इस्तेमाल करने वाली design जोखिमभरी है, और टकराव की आवृत्ति operating system और execution method के अनुसार बदलती है
  • Go का time.Now() absolute time और monotonic clock के सापेक्ष समय, दोनों को साथ रिकॉर्ड करता है, जिससे लगातार calls के बीच का अंतर और absolute timestamp के duplication को अलग-अलग जांचा जा सकता है
  • Linux single-thread में समय हमेशा बढ़ता रहा और न्यूनतम बढ़त 32ns थी, लेकिन threads अलग होने पर वही absolute time देखा गया
  • Mac OS X में absolute time की microsecond resolution होने से टकराव बहुत ज्यादा होते हैं, और single-thread में भी monotonic clock के न बढ़ने वाले मामले अक्सर दिखाई देते हैं

समवर्ती पढ़ाई में सामने आई टकराव की आवृत्ति

  • मुख्य सवाल यह है कि आधुनिक systems में नैनोसेकंड timestamp टकराव वास्तव में कितनी बार होते हैं
  • 4 physical cores पर एक साथ clock पढ़ने पर कुल samples का लगभग 5% टकराता है
  • 4-core system में सिर्फ 2 threads इस्तेमाल करने पर भी लगभग 2% timestamps एक जैसे मिले
  • इसलिए यह मान लेना सुरक्षित नहीं है कि सिर्फ raw नैनोसेकंड timestamp से unique ID बनाई जा सकती है

टेस्ट का तरीका और operating system के अनुसार अंतर

  • test program Go में लिखा गया है
  • Go का time.Now() हर call पर absolute time और monotonic clock के सापेक्ष समय दोनों रिकॉर्ड करता है
    • टेस्ट लगातार timestamps के बीच सापेक्ष अंतर की तुलना करता है
    • साथ ही absolute timestamp के duplication की भी जांच करता है

  • Linux

    • single-thread में absolute time और monotonic time हमेशा बढ़ते हैं
    • मापे गए system में न्यूनतम बढ़त 32ns थी
    • threads के बीच absolute time किसी दूसरे thread के बिल्कुल समान होने की घटना लगभग 5% रही

  • Mac OS X

    • absolute time की microsecond resolution होने से उसी टेस्ट में बहुत ज्यादा टकराव हुए
    • single-thread में भी monotonic clock के न बढ़ने वाले मामले अक्सर देखे गए

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-07-23
Hacker News की राय

  • इस तरह की समस्या से बचने का तरीका है ऐसा ID इस्तेमाल करना जिसमें समय तत्व और क्रम संख्या दोनों शामिल हों
    उदाहरण के लिए, UUIDv7 में मिलीसेकंड-स्तर का समय तत्व होता है, उसी मिलीसेकंड के भीतर हर इवेंट के लिए बढ़ने वाला एक फ़ील्ड होता है, और अलग-अलग मशीनों पर बने IDs के बीच टकराव की संभावना को खगोलीय रूप से कम करने लायक random bits भी होते हैं
    बेशक, bits की संख्या सीमित होती है, इसलिए अगर एक ही समय-खंड में इवेंट बहुत ज़्यादा हों तो क्रम संख्या overflow कर सकती है, मशीनों के बीच collision वास्तव में हो सकता है, और increment operation की वजह से CPU synchronization की ज़रूरत पड़ सकती है जिससे इवेंट जनरेशन की गति सीमित हो सकती है
    फिर भी, व्यावहारिक पैमाने पर UUIDv7 बहुत अच्छी तरह काम करता है

    • थोड़ा संयोग से टाइम ट्रैवलर जैसा महसूस हो रहा है, लेकिन मुझे याद है कि कम-से-कम 10 साल पहले किसी टेक मीटअप में कोई व्यक्ति प्रति मिलीसेकंड 1000 से ज़्यादा UUID बना रहा था और uniqueness की समस्या से जूझ रहा था, और उस समय उपलब्ध विकल्पों से संतुष्ट नहीं था
      इंटरनेट पर ठीक से नहीं मिल रहा कि UUIDv7 कितना पुराना है
    • शुरुआत से ही समझ नहीं आता कि समय तत्व की ज़रूरत क्यों है
      यह सिर्फ UUID के bits खा जाता है और entropy में ज़्यादा योगदान नहीं देता
    • PostgreSQL जैसे लोकप्रिय डेटाबेस में sorting order के साथ भी यह अच्छी तरह मेल खाता है
      अभी यह core में शामिल नहीं है, लेकिन application level पर सीधे इस्तेमाल करने के अलावा uuidv7 देने वाले कई बेहतरीन pg extensions मौजूद हैं
    • UUID की समस्या यह है कि इसे पढ़ना बिल्कुल कठिन है
      सिर्फ समझना ही नहीं, आँखों से एक-दूसरे से अलग पहचानना भी बहुत मुश्किल है
      इसलिए कुछ मामलों में ऐसा identifier उपयोगी होता है जिसमें ज़रूरी न्यूनतम जानकारी के अलावा कोई अतिरिक्त जानकारी या शोर बिल्कुल न हो
    • use case के अनुसार “उसी मिलीसेकंड” तक संभालने की भी ज़रूरत नहीं होती और कुछ cycles बचाए जा सकते हैं
      किसी भी रूप में overflow होने वाला increment counter और थोड़े random bits आम तौर पर काफ़ी होते हैं, और ठीक से लिखा जाए तो दोनों branchless भी हो सकते हैं

  • इसी से जुड़ी बात, मैं पहले Windows के security event log का program manager था
    multicore systems में अगर काम एक साथ या बहुत पास-पास के समय पर हो, तो thread scheduling अवलोकित नतीजों पर बड़ा असर डाल सकती है
    उदाहरण के लिए, timestamp लेने वाली system call तक पहुँचने से पहले, या बाद में timestamp लगाने के लिए event को queue में डालने वाले buffer को सौंपने से पहले, thread quantum खत्म हो सकता है
    वास्तव में 2000 के दशक के Windows multiprocessing systems में event log entries का क्रम उल्टा दिखाई देना बहुत आम था, और log timestamp की accuracy पर बहुत ज़्यादा बारीकी से भरोसा नहीं किया जा सकता था
    सुरक्षित lower bound व्यावहारिक रूप से 1 सेकंड था, और याद पड़ता है कि कुछ components timestamp को truncate या round भी करते थे

  • अगर आपको unique identifier चाहिए, तो version 4 UUID, यानी random UUID, इस्तेमाल कर लीजिए
    collision की संभावना लगभग उतनी ही है जितनी quantum fluctuation की वजह से एक पूरा बड़ा डायनासोर अचानक आपके बेडरूम में प्रकट हो जाए

    • मैं यह जोखिम ले लूँगा
      थोड़ा गंभीर होकर कहूँ तो, अगर इस्तेमाल कर सकते हैं तो पुराना incremental value शायद सबसे अच्छा है
      यह तेज़ और सस्ता है, खासकर डेटाबेस में, लेकिन ID value से जानकारी का अनुमान लगाया जा सकता है, इसलिए privacy·security समस्याएँ होती हैं
      ऐसे मामलों में, या distributed systems के साथ काम करते समय, UUID बेहतर है
    • v7 v4 की locality समस्या को हल करता है, और फिर भी collision होने की संभावना से कहीं ज़्यादा lottery लगने की संभावना होती है, इसलिए यह बेहतर लगता है
    • “डायनासोर अचानक बेडरूम में प्रकट हो जाने की संभावना” वाली गणना कैसी है, यह देखना चाहूँगा
    • तो इसका मतलब बुरी चीज़ होने की संभावना लगभग 2 गुना बढ़ गई, इसलिए यह स्वीकार्य नहीं है

  • resolution नैनोसेकंड हो तब भी, असली कंप्यूटर घड़ी की precision कितनी होती है, यह जानना दिलचस्प है
    यह मानना मुश्किल है कि वह सचमुच नैनोसेकंड स्तर की होगी, और इससे मुझे फिजिक्स लैब की कक्षाएँ याद आ गईं जहाँ मैं छात्रों से बार-बार कहता था कि किसी मापक यंत्र पर दिखने वाला सबसे छोटा अंक उसकी accuracy के बराबर नहीं होता

    • अगर कोई डिवाइस 1GHz या उससे ऊपर चलता है, तो घड़ी का हर नैनोसेकंड पर बढ़ना पूरी तरह संभव है
      लेकिन इसका मतलब यह नहीं कि वह उस स्तर तक accurate है, और multicore systems में अलग-अलग cores की घड़ियाँ उस स्तर तक synchronized न भी हों
      ARMv8 यह गारंटी देता है कि घड़ी कम-से-कम 1GHz पर बढ़ेगी, लेकिन Intel और पुराने ARM में मामला अधिक जटिल है
    • वास्तव में यह नैनोसेकंड है

  • Erlang/Elixir का BEAM VM इस अंतर को बहुत स्पष्ट रूप से दिखाता है। यह monotonically increasing और strictly monotonically increasing के बीच का फर्क है
    https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
    “monotonically increasing values की sequence में, हर वह value जिसके पहले कोई value है, अपने पहले वाली value से बड़ी या बराबर होती है”
    इसे https://www.erlang.org/doc/man/erlang.html#monotonic_time-0 function के साथ इस्तेमाल किया जा सकता है
    https://www.erlang.org/doc/apps/erts/time_correction.html#st...
    “strictly monotonically increasing values की sequence में, हर वह value जिसके पहले कोई value है, अपने पहले वाली value से बड़ी होती है”
    strict monotonic values किसी न किसी प्रकार के synchronization या coordination का संकेत देते हैं, और जब concurrent processes बहुत हों तो इसकी performance cost आती है
    यह feature https://www.erlang.org/doc/man/erlang.html#unique_integer-1 function से मिलता है, और docs भी चेतावनी देते हैं कि strictly monotonically increasing values बनाना स्वभावतः महंगा है और अच्छी तरह scale नहीं होता, इसलिए monotonic modifier केवल तब दें जब सच में जरूरत हो

    • Erlang के reference values भी strict monotonic global generator से नहीं बनाए जाते, बल्कि अंदरूनी तौर पर एक सामान्य monotonic identifier और उसे request करने वाली process के PID की जोड़ी से बने होते हैं
      दूसरे शब्दों में, यह UUIDv1 या https://en.wikipedia.org/wiki/Snowflake_ID जैसा है
      सच में strict monotonic global identifier केवल तब चाहिए जब तुरंत consistent first/last write winner जरूरी हो
      इसके बजाय अगर eventually consistent first/last write winner चल सकता है, जैसे write events किसी event store या queue में ID के आधार पर linearize हों और “concurrent” writes में सबसे ऊँची ID priority वाले को छोड़कर बाकी को processing के दौरान या read time पर discard किया जा सके, तो मैं पहले compact (nodeID, seq) pair पर विचार करूंगा
      अगर global event ordering चाहिए, तो खासकर Snowflake ID के रूप (timestampMajor, nodeID, timestampMinor, seq) पर विचार किया जा सकता है

  • FreeBSD में CLOCK_MONOTONIC_RAW नहीं है, इसलिए उसे comment out करने पर सब ठीक लगता है
    मेरी समझ यह थी कि अगर collisions हों तो कुछ timestamps दोहरने चाहिए, लेकिन मैं collisions बना ही नहीं पा रहा हूँ
    clock_getres(CLOCK_REALTIME, ...)=1 ns, clock_getres(CLOCK_MONOTONIC, ...)=1 ns दिखता है, और 30 samples में भी फर्क लगभग 29~71ns की range में लगातार बढ़ता रहा

    • लेखक की तरह 4 cores पर एक साथ चलाया गया था या नहीं, यह महत्वपूर्ण है

  • आखिरकार बात किसी बिंदु पर instruction set architecture की समस्या तक नहीं पहुँचती?
    3GHz पर चलने वाला CPU प्रति nanosecond 3 clock cycles पाता है
    compiler optimization के कारण clock register पढ़ने वाली assembly calls का लगातार चिपक जाना काफी संभव लगता है
    अगर लगातार time.Now() calls 3 clock cycles के भीतर हो जाएँ, तो क्या सच में unique nanosecond precision की उम्मीद करना उचित है?

    • Linux के x86_64 में RDTSC का उपयोग होता है और VDSO से पढ़े गए value से correction की जाती है, इसलिए यह वास्तव में बहुत तेजी से हो सकता है
    • आधुनिक chips में cycle counter register पढ़ने में भी लगभग 20 cycles लगते हैं
      भले collisions कुछ दुर्लभ हों, लेकिन अगर वे दिन में कुछ बार होती हैं, तो यह “लगभग कभी नहीं होता” से कहीं खराब है

  • इससे Lotus Notes से जुड़ी एक कहानी याद आती है
    पहले कहा जाता था कि वहाँ 1-second resolution वाला timestamp unique ID के रूप में इस्तेमाल होता था
    collision होने पर बस उसमें 1 second जोड़ दिया जाता था, और आखिरकार collisions इतने बढ़ गए कि items के पास future timestamps आने लगे

  • बिल्कुल सटीक समय अपने आप में एक security issue है
    CPU designers पूरी predictability रोकने के लिए, DEC Alpha के समय से ही बहुत पहले से जानबूझकर clock jitter डालते आए हैं
    x86 पर भी अगर आप इसे 3~4 बार चलाकर values को register में store करें और अंत में देखें, तो संभवतः पाएँगे कि time differences बिल्कुल समान नहीं हैं

    • क्या इसके लिए कोई source है?
      मुझे खोजने पर ज्यादा कुछ नहीं मिला, लेकिन अगर यह बात शुरुआती x86 तक भी लागू होती है, तो यह हैरान करने वाली बात है कि accurate clocks के security implications इतनी जल्दी पहचाने गए थे
      व्यक्तिगत रूप से, मुझे लगता है कि इस millennium से पहले मैं ऐसी समस्याओं के बारे में नहीं जानता था, और जो clock jitter दिखती थी उसे interrupts जैसी चीज़ों से समझाता
      मेरा मतलब यह नहीं कि आप गलत हैं, बस मैं और जानना चाहता हूँ

  • मैंने बहुत से लोगों को millisecond या microsecond timestamp collisions पर हैरान होते देखा है
    सबसे यादगार और सबसे खराब pattern वह है जिसमें दो system calls से timestamp जोड़ा जाता है
    एक ऊपरी digits के लिए और दूसरा निचले digits के लिए call किया जाता है, लेकिन process preemption की वजह से अगर ऊपरी digits पढ़ने के बाद निचला हिस्सा 99x से 00x पर चला जाए, तो ऐसा timestamp बन सकता है जो उस entity को बनाने वाले कारण से भी पहले का समय दिखाए
    इससे कुछ code बहुत शानदार तरीके से टूट जाता है, और मैंने कम-से-कम दो बार infinite loop देखा है
    अगर इसे ऐसी चीज़ के रूप में याद न रखा जाए जिससे हमेशा बचना है, तो tests 99.5% बार pass हो जाते हैं, और फिर किसी ऐसे व्यक्ति की जरूरत पड़ती है जिसकी pattern-matching intuition बहुत तेज हो, जो पकड़े कि “वही test डेढ़ महीने तक हफ्ते में एक बार लाल हुआ”
    CI/CD code के अंदर logic bomb के ठीक होने से पहले जिंदा रहने के लिए यह बहुत लंबा समय है

    • सबसे यादगार उदाहरण वह था जब support बातचीत में मैंने कहा, “लगता है कोई race condition है,” और जवाब मिला, “वे दोनों events ठीक उसी समय हुए थे, इसलिए यह race condition नहीं हो सकती”