自從計算機問世以來,計算機系統(tǒng)結構的研究重點發(fā)生了很多變化,這讓一些希望從事這方面研究的新手覺得很難入門。作者根據多年從事研究和指導研究生的經驗,把計算機系統(tǒng)研究中最常用的原理和關鍵技術匯集在一起。在基本知識部分,作者描述了從事系統(tǒng)結構研究的基本要領,包括如何讀、寫、說,以及英文寫作最常見的問題,并給出了12個最經典的設計原理和經驗。在關鍵技術部分,作者從建模、設計、實現(xiàn)和性能評測方面選擇了15個關鍵技術進行了詳細的討論和描述,每一個關鍵技術的題目都經過精心挑選,并且提供多個實例分析。《計算機系統(tǒng)研究基礎(英文版)》可供計算機系統(tǒng)結構初學者使用,也可供高年級本科生和研究生在學習有關課程時參考。
The field of computer systems is the core of computer science, and is concerned with how todesign and implement a \"good\" system that is able to satisfy a variety of requirements and needsfrom end users and applications. The definition of \"good\" depends on to whom we are talking,and it could\" mean one or several of these basic requirements, to name a few: reliability, scalability,availability, usability, adaptability, agility, dependability, and performability. We envision that moreand more new requirements will emerge as computing becomes more and more transparent andembedded in our daily life. This unstoppable trend, however, brings great challenge to futurecomputer systems designers and practitioners. There is a gap between what the students learnedin the classroom and what they are going to build in the real world. The goal of this book is topresent the fundamental knowledge and techniques by laying out the foundations for the studentswho want to become researchers in the general area of computer systems. The book is intended forboth senior undergraduate students and junior graduate students in the fields of computer scienceand computer engineering. Practitioners and systems designers in industry and research laboratorieswill find the book a very useful reference. One important principle guiding the writing of this bookis that it should contain the material I would want my own students to learn before beginning theirresearch.
The focus of systems research has changed considerably since the inception of computers. How-ever, we have witnessed that several fundamental techniques and principles have been frequentlyused in systems research in the last fifty years. The goal of this book is to provide beginning com-puter systems researchers enough background for undertaking further systems research in theircareer path. The philosophy of this book is foundation, in other words, only the techniques thatwill at least survive for more than 10 years are selected.
施巍松,美國韋恩州立大學計算機科學系副教授,移動和因特網系統(tǒng)結構實驗室主任,可持續(xù)計算實驗室主任。美國國家科學基金會杰出青年教授獎獲得者,全國百篇優(yōu)秀博士論文獲得者。IEEE資深會員,IEEE Internet Computing及Joumal of Parallel and Distriibuted Computinq客座編輯,Journal of Computer Scierice and Techology及International Journal of Sensor Networks編委。施巍松博士的研究興趣包括計算機系統(tǒng)和可持續(xù)計算等。
Part I General
Elements
1.1 Top Systems Conferences/Journals
1.2 How to Read a Research Paper
1.3 How to Write a Research Paper
1.3.1 Abstract
1.3.2 Introduction
1.3.3 Background Information/Problem Statement
1.3.4 Your Approach
1.3.5 Implementation
1.3.6 Performance Evaluation
1.3.7 Related Work
1.3.8 Conclusions
1.3.9 Acknowledgement
1.3.10 References
1.3.11 Most Common Mistakes in Paper Writing
1.4 How to Give a Presentation
1.4.1 General Approach
1.4.2 Understanding the Paper
1.4.3 Adapting the Paper for Presentation
1.4.4 Slides
1.4.5 The Dry-Run
1.4.6 To Memorize or not to Memorize?
1.4.7 You Are on the Stage
1.4.8 Interacting with the Audience and Dealing with Questions
1.5 Final Words: On Being a Scientist
References
2 Rules of Thumb
2.1 Rules of Thumb
2.2 Further Readings
References
Part Ⅱ Design
3 Bloom Filters
3.1 Introduction
3.2 Standard Bloom Filters
3.2.1 Basic Idea of Bloom Filters
3.2.2 False Positive Rate Estimation
3.2.3 Optimal Number of Hash Functions
3.2.4 Another Method of Implementing
3.3 Counting Bloom Filters
3.4 Compressed Bloom Filters
3.5 D-left Counting Bloom Filters
3.5.1 D-left Hashing
3.5.2 D-left Counting Bloom Filters
3.5.3 Performance
3.6 Spectral Bloom Filters
3.6.1 Basic Principle of SBF
3.6.2 SBF Frequency Query Optimization
3.7 Dynamic Counting Bloom Filters
3.8 Case Studies
3.8.1 Case Study 1: Summary Cache
3.8.2 Case Study 2: IP Traceback
3.9 Conclusion.
References
4 Distributed Hash Tables
4.1 Introduction
4.2 An Overview of DHT
4.3 The Overlay Network of DHT
4.4 Chord: An Implementation of DHT.
4.4.1 Topology of Chord
4.4.2 Key Lookup in Chord
4.4.3 Dynamic Updates and Failure Recovery
4.5 Case Study 1: Cooperative Domain Name System (CoDoNS)
4.5.1 Background and Motivation
4.5.2 Overview of the System
4.5.3 DHT in CoDoNS
4.5.4 Evaluation
4.6 Case Study 2: Cooperative File System (CFS)
4.6.1 Background and Motivation.
4.6.2 Overview of the System
4.6.3 DHT in CFS
4.6.4 Evaluation
References
5 Locality Sensitive Hashing
5.1 Introduction
5.1.1 Basic Idea of LSH
5.1.2 The Origin of LSH
5.2 Overview.
5.2.1 The Definition
5.2.2 Properties of LSH
5.2.3 Several LSH Families
5.2.4 Approximate Nearest Neighbor
5.3 Case Study 1: Large-Scale Sequence Comparison
5.3.1 Theory
5.3.2 Algorithm Complexity
5.3.3 Implementation Details
5.3.4 Results
5.4 Case Study 2: Image Retrieval
5.4.1 Motivation
5.4.2 The Problems of Existing Approaches
5.4.3 The System
5.4.4 Results
References
6 XOR Operations
6.1 Introduction
6.2 XOR Operation
6.2.1 Truth Table
6.2.2 Set Diagrams
6.3 XOR Properties
6.4 Compress with XOR
6.4.1 Case Study 1: XOR-linked list
6.4.2 Case Study 2: XOR swap algorithm.
6.5 Fault Tolerance
6.5.1 Case Study 3: Hamming (7,4) code
6.5.2 Hamming Codes with Additional Parity
6.5.3 Case Study 4: RAID
6.6 Case Study 5: Feistel Cipher
6.7 Case Study 6: Kademlia
6.7.1 XOR Metric in Kademlia
6.7.2 Routing Table in Kademlia
6.7.3 Kademlia Protocol
6.8 Conclusion.
References
7 Adaptation
8 Optimistic Replication.
9 Reputation and Trust
10 Moving Average
Part Ⅲ Implementation
Part Ⅳ Evalution