Week 12.a
CS6640
11/21 2023
https://naizhengtan.github.io/23fall/

1. fs namespace
2. lab6 design
---

1. fs namespace

  * the question under-the-hood:

    Q: Consider you have 1,000 books at home. How will you organize them so that
       you can easily find the book you want?

    Q: Consider you are a librarian with 1,000 books. How would you organize books
       so that when a guest comes, you can find the book for them?

    Q: Are there any difference of how you organize the books?

    [these apply to file systems
      books: files
      your organization system: namespace
    ]

    * a book is an extent-based readonly fs
      --book pages: disk (persistent)
      --articals/sections: files
      --contents: dirs

  * "boring" hierarchical namespace

    -- used since CTSS (1960s), and Unix picked it up and used it nicely

    -- structure like:
        [draw: 
                      "/"
           bin/     dev/     tmp/    usr/
         ls, grep    ...
        ]

    -- How to lookup a file, say "/bin/ls"?

  * is the hierarchical namespace the only option? 
    No, take a look at databases.
    comparison: file system vs. databases
      databases: structured data
      fs: unstructured data

  * "Hierarchical file systems are dead" (2009)
    Margo Seltzer and Nicholas Murphy, HotOS'09

    -- hFSD argues,
       hiererachical namespace works good in the past.
       "The situation, however, has evolved"

    i) storage size grows
      -- 1992: 300MB disk
      -- 2009: 300GB disk (the paper's time, 23 years later)
      -- 2023: 22TB disk & 8TB SSD (14 years later than paper)
      -- 2030(?): 1000TB SSD
         [https://www.techradar.com/news/1000tb-ssds-could-become-mainstream-by-2030-as-samsung-plans-1000-layer-nand]

    ii) "..they [file sizes] have not increased by the same margin."
       larger space => 
          file size wasn't growing that fast => 
            more files => 
              harder to manage
        [Q: does logic flow?]

    iii) "Google is a verb"
      what they want instead of where it lives
      [a sharp observation]

   * Why hierarchical namespace is a problem?
     -- files are siloed (no need for a global namespace)
        Sounds familiar?
          this is very much like smartphone's logic
          (notice that this paper was 2009; iphone debuted in 2007)
     -- walk the hierarchy (performance is bad, without cache)
     -- concurrency (this is fundamental)

   * hFAD design

     idea: instead of a hierarchical namespace,
           use a tagged, search-based namespace

     [see Fig1]
     -- based on an object-based storage device (OSD)
     -- naming (via index) and accessing (via obj store)
     -- "An object is named by one or more tag/value pairs."

     Q: how about updates? deleting a file needs to update multiple
        indexes at the same time.

        Note: index is a data structure that accelerate data retrieval,
        at the cost of more expensive updates and more space.

   * DISCUSSION: search-based fs vs. hierarchical fs
     real question: human-readable vs. machine-readable


2. lab6 design

    - an abstract disk
      -- simulated SD Card
      -- a block is 512B

                        |<-inode arr->|<-data blocks->|
       +-------+--------+-------------+---------------+
       | super | block  |  |  | ...   |  |  | ...     |
       | block | bitmap |  |  |       |  |  |         |
       +-------+--------+-------------+---------------+
    block  0       1     2  3    ...11 12...

    - talk to the disk?
      int block_read(int block_no, void* dst);
      int block_write(int block_no, void* src);

    - inode data structure
      [see fig]

    - read/write files