Exercise: DNS Resolver Cache တစ်ခု တည်ဆောက်ခြင်း

နားလည်ထားရမယ့် အချက်

DNS အလုပ်ဖြစ်နေတာ root server တွေ မြန်လို့ မဟုတ်ဘူး။ သူတို့ကို ဘယ်သူမှ မမေးလို့ အလုပ်ဖြစ်နေတာ။ Internet တစ်ခုလုံးအတွက် root name server address ဆယ့်သုံးခုပဲ ရှိတယ်။ Browser tab တိုင်းက hostname တိုင်းကို root ကနေ စပြီး resolve လုပ်ခဲ့ရင် ဒီ system ဟာ လွန်ခဲ့တဲ့ ဆယ်စုနှစ်တွေကတည်းက ပြိုကျသွားပြီးဖြစ်မယ်။ Caching ဆိုတာ DNS ပေါ်မှာ နောက်မှ တပ်ဆင်လိုက်တဲ့ optimisation မဟုတ်ဘူး — ဒီလောက် တိမ်တဲ့ hierarchy တစ်ခုကို ရှင်သန်နိုင်စေတဲ့ load-shedding mechanism ကိုယ်တိုင်ပဲ။ Cached record အလုံး နှစ်ထောင်သုံးထောင်နဲ့ တစ်နေ့ query သန်းချီ ဖြေပေးနေတဲ့ resolver ဟာ protocol ကို ဒီဇိုင်းဆွဲစဉ်က ရည်ရွယ်ခဲ့တဲ့ အတိုင်း အတိအကျ လုပ်နေတာပါ။

ပြန်သုံးတာကို လုံခြုံစေတဲ့ အရာက TTL ဖြစ်ပြီး၊ TTL ကို လွဲမှားနားလည်ဖို့ အလွန်လွယ်တယ်။ သူက server က ကိုယ့်အတွက် ထိန်းပေးနေတဲ့ countdown မဟုတ်ဘူး၊ သက်တမ်းကုန်တဲ့အခါ record ပြောင်းသွားလိမ့်မယ်ဆိုတဲ့ ကတိလည်း မဟုတ်ဘူး။ သူက တစ်ဖက်သတ် contract တစ်ခုပါ — zone owner က "ဒီအဖြေကို နောက် N စက္ကန့်အထိ ပြန်သုံးလို့ ရတယ်၊ အဲဒီ window အတွင်း ငါ့ဘက်က မင်းဆီ လှမ်းပြင်ဖို့ နည်းလမ်း မရှိဘူးဆိုတာ ငါ လက်ခံတယ်" လို့ ပြောနေတာ။ ဒါကြောင့် စီစဉ်ထားတဲ့ migration တိုင်းမတိုင်ခင် ပထမဆုံး လုပ်ရတာက TTL ကို လျှော့ချတာ ဖြစ်တယ်။ ကိုယ်တိုင် stale data မဖန်တီးခင်မှာ အဲဒီ stale data ရဲ့ blast radius ကို ကြိုတင် ချုံ့ထားလိုက်တာပါ။

ဘယ်သူကမှ ကိုယ့်ဆီ update push မလုပ်နိုင်တဲ့အတွက် expiry check ကို timer နဲ့ မဟုတ်ဘဲ read လုပ်တဲ့အချိန်မှာ လုပ်ရမယ်။ Background pass နဲ့ပဲ expired entry တွေ ရှင်းတဲ့ cache ဟာ sweep နှစ်ခုကြား အကွာအဝေးမှာ stale address ကို ထုတ်ပေးလိမ့်မယ်။ Insert လုပ်တဲ့အချိန်မှာ absolute expires_at ကို သိမ်းပါ၊ ပြီးရင် lookup တိုင်းမှာ လက်ရှိအချိန်နဲ့ နှိုင်းယှဉ်ပါ။ Dictionary တစ်ခုကို cache တစ်ခု ဖြစ်သွားစေတာ အဲဒီ read-time expiry ပါပဲ။

DNS CACHE LOOKUP PATH
---------------------
             lookup(name, now)
                    |
                    v
          +---------------------+
          | name in cache?      |
          +----+-----------+----+
            no |           | yes
               |           v
               |   +---------------------+
               |   | now < expires_at ?  |  <-- TODO (b)
               |   +----+-----------+----+
               |    yes |           | no
               |        v           v
               |    +-------+   +----------+
               |    | HIT   |   |  evict   |
               |    +-------+   |  entry   |
               |     TODO (a)   +----+-----+
               |                     |
               +----------+----------+
                          v
              +-------------------------+
              | fetch_from_zone(name)   |   zone_queries += 1
              +-------------------------+
                          |
                          v
              +-------------------------+
              | cache[name] =           |
              |   (addr, now + ttl)     |   store ABSOLUTE expiry
              +-------------------------+
                          |
                          v
                        MISS

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

အောက်က scaffold ဟာ plumbing အားလုံး တပ်ဆင်ပြီးသား၊ စိတ်ဝင်စားစရာ အကောင်းဆုံး ဆုံးဖြတ်ချက် နှစ်ခုကိုတော့ ချန်ထားတဲ့ resolver တစ်ခုပါ။ ZONE က authoritative data ဖြစ်ပြီး name သုံးခု ပါတယ် — တစ်ခုချင်းစီမှာ address နဲ့ TTL 60၊ 30၊ 300 စက္ကန့် ရှိတယ်။ cache က name တစ်ခုကို (address, expires_at) tuple နဲ့ map လုပ်တယ်။ zone_queries က authoritative server ဆီ သွားတဲ့ အကြိမ်တိုင်းကို ရေတွက်တယ် — အဲဒါက ကိုယ် နောက်ဆုံးမှာ လျှော့ချချင်တဲ့ ဂဏန်းပါပဲ။

အချိန်ကို နာရီကနေ လုံးဝ မယူဘူး။ lookup တိုင်းက စက္ကန့်နဲ့ ဖော်ပြထားတဲ့ now ကို parameter အဖြစ် လက်ခံတယ်၊ TRACE ကလည်း t = 0၊ 10၊ 12၊ 75၊ 80 နဲ့ 100 မှာ query ခြောက်ခု ရှိတဲ့ သတ်မှတ်ထားတဲ့ script တစ်ခုပါ။ ဒါကြောင့် ဒီ exercise ကို စစ်ဆေးလို့ ရတယ် — input တူရင် trace အမြဲတူတာမို့ ကိုယ့် output ကို မျှော်လင့်ထားတဲ့ output နဲ့ diff လုပ်ကြည့်လို့ ရတယ်၊ run တိုင်း ရွေ့နေတဲ့ wall-clock timing ကို မျက်စိကျဉ်းပြီး ကြည့်နေစရာ မလိုဘူး။

lookup() ဟာ cache-miss path အတွက် ပြီးပြီးသားပါ။ Zone ကနေ fetch လုပ်တယ်၊ now + ttl ဆိုတဲ့ absolute expiry နဲ့ address ကို သိမ်းတယ်၊ ပြီးရင် miss လို့ report လုပ်တယ်။ Entry ရှိပြီးသား branch ကတော့ တမင်တကာ အလွတ်ချန်ထားတာ။ ဖြစ်နိုင်ပုံပေါက်တဲ့ အဖြေတစ်ခုကို တိတ်တိတ်ပုန်း ပြန်ပေးမယ့်အစား MISS (cache hit not implemented) လို့ ရိုးရိုးသားသား ပြောတယ် — ဒါဆို ဘယ်ဆုံးဖြတ်ချက်တွေ ကျန်နေသေးလဲဆိုတာ trace ကနေ တိတိကျကျ မြင်ရမယ်။ ဘာမှ မရေးခင် တစ်ခါ run ပြီး status column ကို အပေါ်ကနေ အောက်အထိ ဖတ်ကြည့်ပါ။

• DNS scale ဖြစ်တာ cache က ဖြေပေးလို့၊ root server မြန်လို့ မဟုတ်ဘူး
• TTL က countdown မဟုတ်ဘူး — window အတွင်း ပြန်မရုပ်သိမ်းနိုင်တဲ့ contract
• Expiry ကို read time မှာ စစ်ပါ၊ background sweep က stale အဖြေ ထုတ်ပေးတတ်တယ်

အတူတူ စမ်းရေးကြည့်မယ်

"""DNS resolver cache -- STARTER SCAFFOLD.

The clock is passed in as an explicit integer `now` (seconds since the
trace started) so that every run gives the same result. Two pieces are
left for you to write: the cache-hit path and the TTL expiry check.
"""

# The "authoritative" zone: name -> (address, ttl in seconds)
ZONE = {
    "www.example.com": ("93.184.216.34", 60),
    "api.example.com": ("93.184.216.35", 30),
    "cdn.example.com": ("93.184.216.36", 300),
}

# name -> (address, expires_at)
cache = {}

zone_queries = 0


def fetch_from_zone(name):
    """Stand-in for asking the authoritative server. Counts the traffic."""
    global zone_queries
    zone_queries += 1
    return ZONE[name]


def lookup(name, now):
    """Resolve `name` at time `now`. Returns (status, address)."""
    entry = cache.get(name)

    if entry is not None:
        # TODO (b): if now >= entry[1] the entry has expired -- evict it
        #           from the cache and fall through to the fetch below.
        # TODO (a): otherwise this is a HIT: return the cached address
        #           without touching the zone table at all.
        return ("MISS (cache hit not implemented)", entry[0])

    address, ttl = fetch_from_zone(name)
    cache[name] = (address, now + ttl)
    return ("MISS (fetched from zone)", address)


TRACE = [
    ("www.example.com", 0),
    ("www.example.com", 10),
    ("api.example.com", 12),
    ("www.example.com", 75),
    ("api.example.com", 80),
    ("cdn.example.com", 100),
]

print("{:<5} {:<18} {:<34} {}".format("t", "name", "status", "address"))
print("-" * 74)
for query_name, query_time in TRACE:
    status, address = lookup(query_name, query_time)
    print("{:<5} {:<18} {:<34} {}".format(query_time, query_name, status, address))

print("-" * 74)
print("zone queries: {}".format(zone_queries))
print("cached names: {}".format(len(cache)))

t     name               status                             address
--------------------------------------------------------------------------
0     www.example.com    MISS (fetched from zone)           93.184.216.34
10    www.example.com    MISS (cache hit not implemented)   93.184.216.34
12    api.example.com    MISS (fetched from zone)           93.184.216.35
75    www.example.com    MISS (cache hit not implemented)   93.184.216.34
80    api.example.com    MISS (cache hit not implemented)   93.184.216.35
100   cdn.example.com    MISS (fetched from zone)           93.184.216.36
--------------------------------------------------------------------------
zone queries: 3
cached names: 3

RFC 1035 - Domain Names: Implementation and Specification — Computer Networking