CSE_lecture2:File System 1

From single to distributed: inode-based File System

使用不同的存储系统来对应不同的服务：scalable file system, scalable database, scalable key-value store，其中key-value store存放不必精确的数据，定期更新就行，而database用于精确存放准确的数据

single-node inode-based filesystem

文件包含两个特性：durable, name

disk driver的抽象：

• 分为一个一个的sector（早期512B，现在为4KB），注意sector为磁盘扇区的概念，而block为操作系统的概念
• API为read和write
• 需要进一步抽象成file system，如果是直接分配sector index，会出现难以寻找空闲sector，难以放大文件，难以命名，可用性和安全性都不足

inode: 7 software layers

L1: block layer

提供block id，得到4KB数据；或者提供block id和要写的数据，将其写入到对应的block，即实现block number->block data

procedure BLOCK_NUMBER_TO_BLOCK(integer b) -> block
    return devices[b]

为什么使用block而非sector？因为file system的最小单位是block，而磁盘的最小单位是sector，只是恰好这俩大小一致罢了，而这是可以调整的

如何决定block size？权衡efficiency和utilization，以及内部的碎片

如何得知block size？使用磁盘开头的super block记录metadata，super block包含block size, num of free blocks, a list of free blocks, etc.

使用bitmap for free blocks记录哪些block被用过，哪些没有

L2: file layer

记录某一个文件使用了哪些block，即inode，包含block_nums[N]和size，size为精确值，从而保证了安全性（之前回收的文件不会清零），其中N可以不用太大，当文件过大时，使用indirect block解决，而当文件过小时，其实可以直接存在inode里面，并修改type

procedure INODE_TO_BLOCK(integer offset, inode i) -> block
    o <- offset / BLOCKSIZE
    b <- INDEX_TO_BLOCK_NUMBER(i, o)
    return BLOCK_NUMBER_TO_BLOCK(b)

procedure INDEX_TO_BLOCK_NUMBER(inode i, integer index) -> integer
    return i.block_nums[index]

L3: inode number layer

实现inode num->inode，即inode table，是一个大数组

procedure INODE_NUMBER_TO_INODE(integer num) -> inode
    return inode_table[num]

procedure INODE_NUMBER_TO_BLOCK(integer offset, integer inode_number) -> block
    inode i = INODE_NUMBER_TO_INODE(inode_number)
    o <- offset / BLOCKSIZE
    b <- INDEX_TO_BLOCK_NUMBER(i, o)
    return BLOCK_NUMBER_TO_BLOCK(b)

L4: file name layer

实现file name和inode number的一一对应关系，存放在directory，而这个directory也抽象成file，存放在inode中，因此inode内部增加type来区分目录和普通文件

procedure NAME_TO_INODE(string filename, integer dir) -> integer
    return LOOKUP(dir, filename)

procedure LOOKUP(string filename, integer dir) -> integer
    block b
    inode i = INODE_NUMBER_TO_INODE(dir)
    if i.type != DIRECTORY then return FAILURE
    for offset from 0 to i.size - 1 do
        b <- INODE_NUMBER_TO_BLOCK(offset, dir)
        if STRING_MATCH(filename, b) then
            return INODE_NUMBER(filename, b)
        offset <- offset + BLOCKSIZE
    return FAILURE

L5: path name layer

层次化的directory为path，直接层层递归即可

procedure PATH_TO_INODE_NUMBER(string path, integer dir) -> integer
    if PLAIN_NAME(path) return NAME_TO_INODE_NUMBER(path, dir)
    else
        dir <- LOOKUP(FIRST(path), dir)
        path <- REST(path)
        return PATH_TO_INODE_NUMBER(path, dir)

Links

link让不同的文件名指向相同的inode num，而unlink取消filename和inode num之间的联系，这是hard link，而hard link不能跨文件系统建立，否则会出现inode num冲突

在inode里面添加一项refcnt，link时+1，unlink时-1，当refcnt = 0时才清除这个inode对应的file

struct inode
    integer block_nums[N]
    integer size
    integer type
    integer refcnt

link不能构成环，否则会导致内存泄漏，因此规定目录不能link，除了两个例外：.和 ..这两个hard link

renaming

编辑文件时会创建一个临时文件，重命名时，顺序为：

1. UNLINK(to_name)
2. LINK(from_name, to_name)
3. UNLINK(from_name)

但如果计算机在1和2之间突然断电呢？这会使得to_name丢失。因此要保证原子性操作

L6: absolute path name layer

引入根目录/，其中/.和/..依然是根目录

procedure GENERATEPATH_TO_INODE_NUMBER(string path) -> integer
    if path[0] = "/" return PATH_TO_INODE_NUMBER(path, 1)
    else return PATH_TO_INODE_NUMBER(path, wd)

参考一个例子来理解file system layers，约定俗成root在inode table的第一个位置

L7: symbolic link layer

区分hard link和soft link：

• hard link强调两个filename都指向同一个inode num，而soft link强调一个filename指向另一个filename，当文件被删除时，hard link连接的文件能够正常访问，而soft link连接的文件会打不开（注意谁指向谁）
• hard link不能跨文件系统建立，而soft link可以，甚至soft link可以指向不存在的文件，并同时新建一个inode

inode中有一个新的名叫symbolic link的type，该文件打开时显示的是指向的文件名，需要再一次打开指向的文件名，正如图片中的8代表/tmp/abc长8个字节，这是因为s-link文件存放的就是/tmp/abc这个文件名（查看时使用readlink或者ls -l指令，而cat会直接读取到被链接文件的内容）

假设有soft link: /CSE-web -> /Scholarly/programs/www，当我运行cd CSE-web后运行cd ..，是回到根目录，因为..被bash截获，记录old pwd，以实现human-friendly，如果不想通过逻辑路径而是通过物理路径，请使用cd -P ..

总结以下几点：

• file name不是file的一部分，而inode可以通过hard link而拥有多个名字
• hard link之间平等，没有先后顺序的区别
• directory的大小很小，这是因为directory只存放映射关系，而不是包含了里面所有文件的大小，应当认为folder是一种错误的理解