j********x
发帖数: 2330 | 1 关键是要有taste
这个确实是某个大牛教授说过的，大意就是做computer system（包括architecture，
distribute system）很依赖研究者的taste；品味很重要。
提升品位最简单的办法就是多看好东西、多吃好东西，那么很显然的办法就是看看论文：
NSDI
OSDI
SOSP
基本上你能想到的流行软件系统基本上都能在这些会议里找到原型或者是类似的系统。
每天抽出上网的时间，浏览一下paper list，找几篇自己感兴趣的看看，时间一长，品
味就出来了。 | g*********e
发帖数: 14401 | | d********w
发帖数: 363 | 3 品味来了。
Basics and Algorithms
The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of
Thumb (1997): This paper (and the original one proposed 10 years earlier)
illustrates a quantitative formula to calculate whether a data page should
be cached in memory or not. It is a delight to read Jim Gray approach to an
array of related problems, e.g. how big should a page size be.
AlphaSort: A Cache-Sensitive Parallel External Sort (1995): Sorting is one
of the most essential algorithms in databases, as it is used to do joins,
aggregations, and sorts. In algorithms 101 class, CS students are asked to
reason about big O complexity and ignore the constant factor. In practice,
however, the change in constant from L2 cache can be as big as two or three
orders of magnitude. This is a good paper to learn about all the tricks fast
sorting implementations use.
Patience is a Virtue: Revisiting Merge and Sort on Modern Processors (2014):
Sorting revisited. Actually also a good survey on sorting algorithms used
in practice and their trade-offs.
Essentials of Relational Databases
Architecture of a Database System (2007): Joe Hellerstein's great overview
of relational database systems. This essay walks readers through all
components essential to relational database systems.
A Relational Model of Data for Large Shared Data Banks (1970): Codd's
argument for data independence (from 1970), a fundamental concept in
relational databases. Despite the current NoSQL trend, I believe ideas from
this paper are becoming increasingly important in massively parallel data
systems.
ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and
Partial Rollbacks Using Write-Ahead Logging (1992): The first algorithm
that actually works: it supports concurrent execution of transactions
without losing data even in the presence of failures. This paper is very
hard to read because it mixes a lot of low level details in the explanation
of the high level algorithm. Perhaps try understand ARIES (log recovery) by
reading a database textbook before attempting to read this paper.
Efficient Locking for Concurrent Operations on B-Trees (1981) and The R*-
tree: An Efficient and Robust Access Method for Points and Rectangles (1990)
optimized and has a low read amplification factor for random lookups of on-
disk data. R-tree is an extension of B-tree to support lookups of multi-
dimensional data, e.g. geodata.
Improved Query Performance with Variant Indexes (1997): Analytical databases
and OLTP databases require different trade-offs. These are reflected in the
choices of indexing data structures. This paper talks about a number of
index data structures more suitable for analytical databases.
On Optimistic Methods for Concurrency Control (1981): There are two ways to
support concurrency. The first is the pessimistic way, i.e. to lock shared
data preemptively. This paper explains an alternatively to locking called
Optimistic Concurrency Control. Optimistic approaches assume conflicts are
rare and executes transactions without acquiring locks. Before committing
the transactions, the database system checks for conflicts and aborts/
restarts transactions if conflicts arise.
Access Path Selection in a Relational Database Management System (1979): The
basics of query optimization. SQL is declarative, i.e. you specify using a
query language what data you want, not how you want it. There are usually
multiple ways (query plans) of executing a query. The database system
examines multiple plans and decides on an optimal one (best-effort). This
process is called query optimization. The traditional way of doing query
optimization is to have a cost-model for different access methods and query
plans. This paper explains the cost-model and a dynamic programming
algorithm to pick the best plan.
Eddies: Continuously Adaptive Query Processing (2000): Traditional query
optimization (and the cost model used) is static. There are two problems
with the traditional model. First, it is hard to build the cost model absent
of data statistics. Second, query execution environment might change in
long running queries and a static approach cannot capture the change.
Analogous to fluid dynamics, this paper proposes a set of techniques that
optimize query execution dynamically. I don't think ideas in Eddies have
made their way into commercial systems yet, but the paper is very refreshing
to read and might become more important now.
Classic System Design
A History and Evaluation of System R (1981): There were System R from IBM
and Ingres from Berkeley, two systems that showed relational database was
feasible. This paper describes System R. It is impressive and scary to note
that the internals of relational database systems in 2012 look a lot like
System R in 1981.
The Google File System (2003) and Bigtable: A Distributed Storage System for
Structured Data (2006): Two core components of Google's data infrastructure
. GFS is an append-only distributed file system for large sequential reads (
data-intensive applications). BigTable is high-performance distributed data
store that builds on GFS. One way to think about it is that GFS is optimized
for high throughput, and BigTable explains how to build a low-latency data
store on top of GFS. Some of these might have been replaced by newer
proprietary technologies internal to Google, but the ideas stand.
Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications (
2001) and Dynamo: Amazon’s Highly Available Key-value Store (2007): Chord
was born in the days when distributed hash tables was a hot research. It
does one thing, and does it really well: how to look up the location of a
key in a completely distributed setting (peer-to-peer) using consistent
hashing. The Dynamo paper explains how to build a distributed key-value
store using Chord. Note some design decisions change from Chord to Dynamo, e
.g. finger table O(logN) vs O(N), because in Dynamo's case, Amazon has more
control over nodes in a data center, while Chord assumes peer-to-peer nodes
in wide area networks.
Columnar Databases
Columnar storage and column-oriented query engine are critical to analytical
workloads, e.g. OLAP. It's been almost 15 years since it first came out (
the MonetDB paper in 1999), and almost every commercial warehouse database
has a columnar engine by now.
C-Store: A Column-oriented DBMS (2005) and The Vertica Analytic Database: C-
Store 7 Years Later (2012): C-Store is an influential, academic system done
by the folks in New England. Vertica is the commercial incarnation of C-
Store.
Column-Stores vs. Row-Stores: How Different Are They Really? (2012):
Discusses the importance of both the columnar storage and the query engine.
Dremel: Interactive Analysis of Web-Scale Datasets (2010): A jaw-dropping
paper when Google published it. Dremel is a massively parallel analytical
database used at Google for ad-hoc queries. The system runs on thousands of
nodes to process terabytes of data in seconds. It applies columnar storage
to complex, nested data structures. The paper talks a lot about the nested
data structure support, and is a bit light on the details of the query
execution. Note that a number of open source projects are claiming they are
building "Dremel". The Dremel system achieves low-latency through massive
parallelism and columnar storage, so the model doesn't necessarily make
sense outside Google since very few companies in the world can afford
thousands of nodes for ad-hoc queries.
Data-Parallel Computation
MapReduce: Simplified Data Processing on Large Clusters (2004): MapReduce is
both a programming model (borrowed from an old concept in functional
programming) and a system at Google for distributed data-intensive
computation. The programming model is so simple yet expressive enough to
capture a wide range of programming needs. The system, coupled with the
model, is fault-tolerant and scalable. It is probably fair to say that half
of the academia are now working on problems heavily influenced by MapReduce.
Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory
Cluster Computing (2012): This is the research paper behind the Spark
cluster computing project at Berkeley. Spark exposes a distributed memory
abstraction called RDD, which is an immutable collection of records
distributed across a cluster's memory. RDDs can be transformed using
MapReduce style computations. The RDD abstraction can be orders of magnitude
more efficient for workloads that exhibit strong temporal locality, e.g.
query processing and iterative machine learning. Spark is an example of why
it is important to separate the MapReduce programming model from its
execution engine.
Shark: SQL and Rich Analytics at Scale (2013): Describes the Shark system,
which is the SQL engine built on top of Spark. More importantly, the paper
discusses why previous SQL on Hadoop/MapReduce query engines were slow.
Spanner (2012): Spanner is "a scalable, multi-version, globally distributed,
and synchronously replicated database". The linchpin that allows all this
functionality is the TrueTime API which lets Spanner order events between
nodes without having them communicate. There is some speculation that the
TrueTime API is very similar to a vector clock but each node has to store
less data. Sadly, a paper on TrueTime is promised, but hasn't yet been
released.
Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks (
2007): Dryad is a programming model developed at Microsoft that enables
large scale dataflow programming. "The fundamental difference between the [
MapReduce and Dryad] is that a Dryad application may specify an arbitrary
communication DAG rather than requiring a sequence of map/distribute/sort/
reduce operations".
Consensus and Consistency
Paxos Made Simple (2001): Paxos is a fault-tolerant distributed consensus
protocol. It forms the basis of a wide variety of distributed systems. The
idea is simple, but notoriously difficult to understand (perhaps due to the
way the original Paxos paper was written).
The Raft Consensus Algorithm (2014) : Raft is a consensus algorithm designed
as an alternative to Paxos. It was meant to be more understandable than
Paxos by means of separation of logic, but it is also formally proven safe
and offers some new features.[1] Raft offers a generic way to distribute a
state machine across a cluster of computing systems, ensuring that each node
in the cluster agrees upon the same series of state transitions.
CAP Twelve Years Later: How the "Rules" Have Changed (2012): The CAP theorem
, proposed by Eric Brewer, asserts that any net-worked shared-data system
can have only two of three desirable properties: Consistency, Availability,
and Partition-Tolerance. A number of NoSQL stores reference CAP to justify
their decision to sacrifice consistency. This is Eric Brewer's writeup on
CAP in retrospective, explaining "'2 of 3' formulation was always misleading
because it tended to oversimplify the tensions among properties."
Trends (Cloud Computing, Warehouse-scale Computing, New Hardware)
A View of Cloud Computing (2010): This is THE paper on Cloud Computing. This
paper discusses the economics and obstacles of cloud computing (referring
to the elasticity of resources, not the consumer-facing "cloud") from a
technical perspective. The obstacles presented in this paper will impact
design decisions for systems running in the cloud.
The Datacenter as a Computer: An Introduction to the Design of Warehouse-
Scale Machines: Google's Luiz André Barroso and Urs Hölzle explains
the basics of data center hardware and software for warehouse-scale
computing. There is an accompanying video. The video talks about the
importance of cutting long-tail latency in massively parallel systems. The
other key idea is the disaggregation of resources. Technologies such as GFS/
HDFS already disaggregate disks because of high network bandwidth, but yet
to see the same trend applying to DRAMs because that'd require low-latency
networking.
Miscellaneous
Reflections on Trusting Trust (1984): Ken Thompson's Turing Award acceptance
speech in 1984, describing black box backdoor issues and pointing out trust
is not absolute.
External Reading Lists
A number of schools have their own reading lists for graduate students in
databases.
Berkeley: http://www.eecs.berkeley.edu/GradAffairs/CS/Prelims/db.html
Brown: http://www.cs.brown.edu/courses/cs227/papers.html
Stanford: http://infolab.stanford.edu/db_pages/infoqual.html
Wisconsin: http://www.cs.wisc.edu/sites/default/files/db.reading.pdf
MIT: Database Systems 6.830 from 2014 http://db.csail.mit.edu/6.830/sched.html and from 2010 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-830-database-systems-fall-2010/readings/ (more summarized reading list)
The reading list for Joseph Hellerstein's graduate course in database
systems at Berkeley. It is more comprehensive than this list, but there is
substantial overlap.
，
文： | j********x
发帖数: 2330 | 4 Chord
Dynamo
Dryad
Rdd,spark挺无聊 dag的基本框架套上一个rdd的皇帝新衣服。。。不推荐阅读。。。 | h*****a
发帖数: 52 | 5 赞好paper
an
【在 d********w 的大作中提到】
: 品味来了。
: Basics and Algorithms
: The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of
: Thumb (1997): This paper (and the original one proposed 10 years earlier)
: illustrates a quantitative formula to calculate whether a data page should
: be cached in memory or not. It is a delight to read Jim Gray approach to an
: array of related problems, e.g. how big should a page size be.
: AlphaSort: A Cache-Sensitive Parallel External Sort (1995): Sorting is one
: of the most essential algorithms in databases, as it is used to do joins,
: aggregations, and sorts. In algorithms 101 class, CS students are asked to
| s******c
发帖数: 1920 | 6 如果是关于research，说的很好。system research就靠选题的taste。
如果只是为了求职，有点overkill了。其实面试设计题的面试官只有一小部分听说过这
几个会议，更小一部分读过它们的论文。
，
文：
【在 j********x 的大作中提到】
: 关键是要有taste
: 这个确实是某个大牛教授说过的，大意就是做computer system（包括architecture，
: distribute system）很依赖研究者的taste；品味很重要。
: 提升品位最简单的办法就是多看好东西、多吃好东西，那么很显然的办法就是看看论文：
: NSDI
: OSDI
: SOSP
: 基本上你能想到的流行软件系统基本上都能在这些会议里找到原型或者是类似的系统。
: 每天抽出上网的时间，浏览一下paper list，找几篇自己感兴趣的看看，时间一长，品
: 味就出来了。
| y**********a
发帖数: 824 | |
|
