UCB CS262A：高级计算机系统专题讲座，融合操作系统与数据库研究

需积分: 9 66 浏览量更新于2024-07-20 收藏 2.93MB PDF 举报

"高级计算机系统课程（UCB CS262A）讲座笔记提供了深入探讨计算机系统领域的前沿话题，由埃里克·布赖尔（Eric Brewer）教授和乔·赫勒斯坦（Joe Hellerstein）共同执教。这门课程是UCB计算机科学专业的一年长期深入研究课程的一部分，旨在弥合操作系统（OS）和数据库研究之间的传统界限。课程的核心目标在于建立一个通用的理论基础，让这两个领域能够更好地交流和合作。以往，尽管OS和数据库研究在目标和理念上有许多重叠，但它们通常使用独立的专业术语，且各自有各自的经典论文库。在操作系统领域，数据库常常被视为"只是一个应用"，导致两个社区之间的知识交流有限。在本课程中，学生将接触到一系列当前操作系统研究的重点课题，如互联网系统、移动计算、安全性和并行计算。这些主题不仅涵盖了操作系统设计和优化的各个方面，还将扩展到数据库系统的研究，如数据管理、声明式网络编程等。课程要求不高，虽然今年不设入门考试，但建议学生复习 undergraduate（本科）阶段的相关知识，以确保有足够的基础知识来应对复杂的系统研究问题。此外，262A课程本身足以满足软件学科的广泛性要求，表明其深度和广度并重，旨在培养学生的系统级思考和跨学科研究能力。通过本课程的学习，学生将学会如何进行操作系统和数据库的创新研究，打破传统壁垒，促进两个领域之间的知识融合。这不仅有助于个人学术发展，也对未来信息技术的交叉创新产生了深远的影响。"

FFS/LFS

utilization.

o Always start by looking for segment with utilization=0, since those are trivial to clean...

o If utilization of segments being cleaned is U:

• write cost = (total bytes read & written)/(new data written) = 2/(1-U). (unless U is 0).

• write cost increases as U increases: U = .9 => cost = 20!

• need a cost of less than 4 to 10; => U of less than .75 to .45.

How to clean a segment?

o Segment summary block contains map of the segment. Must list every i-node and file

block. For file blocks you need {i-number, block #}

o To clean an i-node: just check to see if it is the current version (from i-node map). If

not, skip it; if so, write to head of log and update i-node map.

o To clean a file block, must figure out it if is still live. First check the UID, which only

tells you if this file is current (UID only changes when is deleted or has length zero).

Note that UID does not change every time the file is modified (since you would have to

update the UIDs of all of its blocks). Next you have to walk through the i-node and any

indirect blocks to get to the data block pointer for this block number. If it points to this

block, then move the block to the head of the log.

Simulation of LFS cleaning:

o Initial model: uniform random distribution of references; greedy algorithm for segment-

to-clean selection.

o Why does the simulation do better than the formula? Because of variance in segment

utilizations.

o Added locality (i.e. 90% of references go to 10% of data) and things got worse!

o First solution: write out cleaned data ordered by age to obtain hot and cold segments.

• What prog. language feature does this remind you of? Generational GC.

• Only helped a little.

o Problem: even cold segments eventually have to reach the cleaning point, but they drift

down slowly. tying up lots of free space. Do you believe that’s true?

o Solution: it’s worth paying more to clean cold segments because you get to keep the

free space longer.

o Better way to think about this: don’t clean segments that have a high d-free/dt (first

derivative of utilization). If you ignore them, they clean themselves! LFS uses age as an

approximation of d-free/dt, because the latter is hard to track directly.

o New selection function: MAX(T*(1-U)/(1+U)).

• Resulted in the desired bi-modal utilization function.

• LFS stays below write cost of 4 up to a disk utilization of 80%.

FFS/LFS

A Lesson: Rethink your basic assumptions about what’s primary and what’s secondary in a design. In this

case, they made the log become the truth instead of just a recovery aid.

IV. Analysis and Evolution of Journaling File Systems

Journaling file systems:

o Write-ahead logging: commit data by writing it to log, synchronously and sequentially

o Unlike LFS, then later moved data to its normal (FFS-like) location; this write is called

checkpointing and like segment cleaning, it makes room in the (circular) journal

o Better for random writes, slightly worse for big sequential writes

o All reads go the the fixed location blocks, not the journal, which is only read for crash

recovery and checkpointing

o Much better than FFS (fsck) for crash recovery (covered below) becuase it is much

faster

o Ext3 filesystem is the main one in Linux; RieserFS was becoming popular

Three modes:

o writeback mode: journal only metadata, write back data and metadata independently

metadata may thus have dangling references after a crash (if metadata written before the

data with a crash in between)

o ordered mode: journal only metadata, but always write data blocks before their

referring metadata is journaled. This mode generally makes the most sense and is used

by Windows NTFS and IBM’s JFS.

o data journaling mode: write both data and metadata to the journal

Huge increase in journal traffic; plus have to write most blocks twice, once to the

journal and once for checkpointing (why not all?)

Crash recovery:

o Load superblock to find the tail/head of the log

o Scan log to detect whole commited transactions (they have a commit record)

o Replay log entries to bring in-memory data structures up to date

This is called “redo logging” and entries must be “idempotent”

o Playback is oldest to newest; tail of the log is the place where checkpointing stopped

o How to find the head of the log?

Some fine points:

o Can group transactions together: fewer syncs and fewer writes, since hot metadata may

changes several times within one transaction

o Need to write a commit record, so that you can tell that all of the compound transaction

made it to disk

o ext3 logs whole metadata blocks (physical logging); JFS and NTFS log logical records

instead, which means less journal traffic

o head of line blocking: compound transactions can link together concurrent streams (e.g.

剩余104页未读，继续阅读

绝不原创的飞龙

粉丝: 4w+

UCB CS262A：高级计算机系统专题讲座，融合操作系统与数据库研究

GeeksForGeeks Operating Systems Lecture Notes

Advanced Topics in Computer Systems Reading List (UCB CS262A)

Data Structures Lecture Notes (UCB CS61b)

Operating Systems Lecture Notes (Stanford CS140)

MIT 6.858 Computer Systems Security Lecture Notes

Functional Systems In Haskell Lecture Notes(Stanford CS240h)

Stanford CS109 Probability for Computer Scientists Lecture Notes

GeeksForGeeks Computer Network Lecture Notes

Great Ideas in Theoretical Computer Science Lecture Notes (MIT 6.045)

Operating Systems Lecture Notes (UMD CMSC412)

最新资源