Object Storage-এর অন্দরমহল — Flat Namespace, Consistency, আর Erasure Coding

এই স্ক্রিপ্ট সত্যিই চালানো হয়েছে। এটা একটা synthetic bucket তৈরি করে (কয়েক হাজার key, বাস্তব “folder”-প্যাটার্নে ছড়ানো — photos/<year>/<month>/img_NNNN.jpg, videos/2024/clip_NNNNN.mp4, backups/db/NNNN.tar.gz), তারপর একই prefix-query দুইভাবে চালায়: naive linear scan (প্রতিটা key check করা) বনাম sorted-key range scan (bisect দিয়ে, S3-র নিজের sorted key-index-এর একটা সরলীকৃত মডেল)।

# flat_namespace_prefix.py -- object storage has NO real directory tree:
# every "folder listing" is actually a PREFIX QUERY over a flat, sorted
# key space. This script builds a synthetic bucket of keys, then compares
# two ways to answer "list everything under photos/2024/":
#   (1) naive linear scan across ALL keys (what you'd do with no index)
#   (2) sorted-key range scan via bisect (conceptually how S3's internal
#       key index works: keys are stored in lexicographic sort order, so
#       a prefix query is just "find the [start, end) range of that sort
#       order" -- cost is O(log n) to find the boundary + O(matches) to
#       read them, NOT O(total keys in the bucket) and NOT O(directory
#       children) the way a real filesystem's readdir() would be.
import bisect

def make_bucket_keys():
    """Synthetic bucket: a realistic mix of 'folders' and object counts."""
    keys = []
    for year in (2022, 2023, 2024):
        for month in range(1, 13):
            count = 40 if year == 2024 else 25
            for i in range(count):
                keys.append(f"photos/{year}/{month:02d}/img_{i:04d}.jpg")
    for i in range(5000):
        keys.append(f"videos/2024/clip_{i:05d}.mp4")
    for i in range(300):
        keys.append(f"backups/db/{i:04d}.tar.gz")
    return keys

def linear_scan_count(keys, prefix):
    """Naive approach: check every single key in the bucket."""
    comparisons = 0
    matches = 0
    for k in keys:
        comparisons += 1
        if k.startswith(prefix):
            matches += 1
    return matches, comparisons

def sorted_range_count(sorted_keys, prefix):
    """Sorted-index approach: binary search for where the prefix's range
    starts and ends in lexicographic order, then the match count is just
    that range's length -- no need to touch keys outside the range."""
    lo = bisect.bisect_left(sorted_keys, prefix)
    hi = bisect.bisect_left(sorted_keys, prefix + "￿")
    matches = hi - lo
    import math
    n = len(sorted_keys)
    comparisons = 2 * max(1, math.ceil(math.log2(n))) if n > 1 else 1
    return matches, comparisons, lo, hi

if __name__ == "__main__":
    keys = make_bucket_keys()
    total = len(keys)
    print(f"total objects in bucket        : {total}")

    sorted_keys = sorted(keys)  # this is the ACTUAL storage order in a
                                 # real object store's key index -- keys
                                 # are not grouped by "folder" at all,
                                 # they just happen to sort that way
                                 # because the key STRING contains '/'

    for prefix in ["photos/2024/03/", "photos/2024/", "videos/2024/", "backups/"]:
        lin_matches, lin_cmp = linear_scan_count(keys, prefix)
        idx_matches, idx_cmp, lo, hi = sorted_range_count(sorted_keys, prefix)
        assert lin_matches == idx_matches, "match-count mismatch!"
        print(f"\nprefix = {prefix!r}")
        print(f"  matched objects              : {lin_matches}")
        print(f"  linear scan comparisons      : {lin_cmp} (= total bucket size)")
        print(f"  sorted-range comparisons     : {idx_cmp} (~ 2*log2(n), independent of match count)")
        print(f"  speedup (comparisons)        : {lin_cmp / idx_cmp:.1f}x")

    print("\n=== key takeaway ===")
    print("linear-scan cost stays constant at", total, "regardless of prefix,")
    print(f"while sorted-range cost stays near {idx_cmp} regardless of prefix too --")
    print("but BOTH still must then iterate the matched objects to return them,")
    print("so listing a 'folder' with many objects is proportionally slower")
    print("than listing one with few -- unlike a real filesystem directory,")
    print("whose readdir() cost depends only on ITS OWN entry count, never")
    print("on how many files exist elsewhere in the tree.")

প্রকৃত চালিয়ে পাওয়া output (deterministic — synthetic bucket-এর গঠন fixed, হুবহু এটাই আসবে):

total objects in bucket        : 6380

prefix = 'photos/2024/03/'
  matched objects              : 40
  linear scan comparisons      : 6380 (= total bucket size)
  sorted-range comparisons     : 26 (~ 2*log2(n), independent of match count)
  speedup (comparisons)        : 245.4x

prefix = 'photos/2024/'
  matched objects              : 480
  linear scan comparisons      : 6380 (= total bucket size)
  sorted-range comparisons     : 26 (~ 2*log2(n), independent of match count)
  speedup (comparisons)        : 245.4x

prefix = 'videos/2024/'
  matched objects              : 5000
  linear scan comparisons      : 6380 (= total bucket size)
  sorted-range comparisons     : 26 (~ 2*log2(n), independent of match count)
  speedup (comparisons)        : 245.4x

prefix = 'backups/'
  matched objects              : 300
  linear scan comparisons      : 6380 (= total bucket size)
  sorted-range comparisons     : 26 (~ 2*log2(n), independent of match count)
  speedup (comparisons)        : 245.4x

=== key takeaway ===
linear-scan cost stays constant at 6380 regardless of prefix,
while sorted-range cost stays near 26 regardless of prefix too --
but BOTH still must then iterate the matched objects to return them,
so listing a 'folder' with many objects is proportionally slower
than listing one with few -- unlike a real filesystem directory,
whose readdir() cost depends only on ITS OWN entry count, never
on how many files exist elsewhere in the tree.

পড়ার সময়: প্রতিটা prefix-এই sorted-range approach মাত্র ২৬টা comparison-এ boundary খুঁজে পায়, match যত ৪০-ই হোক বা ৫০০০-ই হোক — bucket-এর মোট আকার-এর ওপর নির্ভরতা log-scale-এ কমে যায়। এটাই S3-র “folder” খুলতে গেলে instant মনে হওয়ার পেছনের গণিত। কিন্তু videos/2024/ prefix-এ ৫০০০-টা match — সেই ৫০০০টা key ফেরত পাঠাতেই সময় লাগবে, backups/ prefix-এর মাত্র ৩০০-এর তুলনায় — এই অংশটাই matched-set-নির্ভর, আর এখানেই object storage-এর “folder listing” সত্যিকারের filesystem-directory-listing থেকে চরিত্রগতভাবে আলাদা। নিজে বাড়ান: make_bucket_keys()-এ আরও একটা “folder” যোগ করুন যাতে ১০ লাখ key থাকে, আর দেখুন sorted-range comparison-সংখ্যা কতটা কম বাড়ে (log2 growth) বনাম linear scan-এর সরাসরি সমানুপাতিক বৃদ্ধি।