CS262A: Advanced Topics in Computer Systems

Joe Hellerstein and Timothy Roscoe

UC Berkeley

Fall, 2005

Lecture 7




Lots of good, sensible ideas in this paper.  A nice simple design as well.  (Mothy may have more to say there.)


Attractive CS262 paper: OS community learning lessons from the DB experiences – inability to influence page replacement policy in the VM. Not all apps are well served by a single policy, should be extensible/configurable.


Then again, maybe not!  Dysfunctional interaction between OS and DB communities?  Many misconceptions about DBMSs here!  Exposes deeper questions! 


Exploring this kind of tension is just what we’re supposed to do in this class.


ACPM Background


First, let’s revisit some of V++’s basic storage units and metaphors:



V++’s ACPM is targeted at exposing the following main issues to application level:


DBMS Buffer Management Background

An aside: how do DBMSs manage their memory, and what do they stick into that memory? 


Two/Three pools of heap memory:

  1. Buffer pool: At boot time, allocate a buffer pool in virtual memory to serve as a cache for database blocks.  This is usually sized to a large fraction of the physical memory on the machine.
  2. Query workspace: Space for memory-intensive query processing operations like sorting and hashing (e.g. for joins). 
  3. Miscellaneous heap space: E.g. the query parser needs some heap space, the query optimizer consumes a nontrivial amount of memory for dynamic programming, the DBMS lock table sits on the heap, etc. (As an aside, most DBMSs implement a region-based memory manager to allow for efficient allocation and leak-free deallocation of such heap space.  A discussion of its own!)


DBMSs make heavy use of virtual memory, but a well-administered DBMS never causes VM to page.  Why?

  1. DBMSs are expensive servers, run on a dedicated machine (since the dawn of time!)  No multiprogramming of note.
  2. Buffer pool and query workspace sizes set to fit in physical memory.  Combined with (1), basically never pages.


ACPM is most relevant to the DBMS buffer pool.  Here’s how buffer pools work in traditional OS contexts:


Returning to ACPM…

Could we implement the DBMS buffer pool using V++ VM?  You bet!


But, DB misconceptions rife in the paper:


So, how much does ACPM help the DBMS?


Conclusion: there’s little here that makes a DBMS writer’s life much easier.  I suspect the same complaint applies to scientific and other applications.  Basic issue is one of metaphor and API:


Lessons here in trying to please people without understanding their pain.  Or more likely, hammers in search of nails.


5 Minute Rule

Why read this paper?

  1. Expose you to a style of trend-driven systems thinking.  A way to identify research opportunities!
  2. Sensitize you to choosing relevant, portable/scalable metrics of performance.
  3. Expose you to the disk access issues that matter to DB applications – and discuss the way they affect buffer replacement and prefetching.


Trend-Driven problem identification

Jim Gray and Dave Patterson seem to push these the hardest.


Performance Metrics



Access patterns in a DBMS (detail courtesy Chou/DeWitt):

Š       Straight Sequential: LocSet size = 1. Replace that page as soon as needed.

Š       Clustered Sequential: LocSet size = (#tuples in largest cluster)/(# of tuples per page). FIFO or LRU replacement work.

Š       Looping Sequential: LocSet size = size of relation (“file”). MRU is best.

Š       Independent Random: odds of revisit are low, so LocSet either 1, or the magic number b from the "Yao" formula.

Š       Clustered Random: Just like CS, but pages are not packed onto blocks. So it’s just # of tuples in largest cluster. LRU or FIFO replacement.

Š       Straight Hierarchical, Hierarchical/Straight Sequential: like Straight Sequential.

Š       Hierarchical/Clustered Sequential: like CS, but replace tuples with (key,ptr) pairs


Fully-specified models a la DBMIN?  Simple stochastic models a la LRU, LRU-k?  Something in between (“gray-box systems”)?