Parallelism & Gamma


Parallelism research happened along multiple tracks.  OS/Compilers/Scientific community was one track in the 80's.  Parallel DBMS was another.  It's worth noting that mainframes were parallel computers long before it was sexy...though the parallelism was used mostly just for multitasking.

A pattern in parallel systems research?

  1. Explore specialized hardware to give better performance through parallelism
  2. Move parallelism ideas into software running over commodity hardware
  3. Along the way, better understanding of algorithms, pounding down of architectural bottlenecks
  4. Drive for performance and scale leads to reliability/maintainability research

The database machine
(Boral/DeWitt '83, "Database Machines: An Idea Whose Time has Passed?")
All mixed up: trying to make storage devices faster, and do "more of the work".  Something of a hodgepodge of extra processors and novel storage devices, and combinations of the two.

All failed.  Why? Is it time to revisit all this??

Parallel DB 101

Performance metrics: 2 kinds of data parallelism 3 barriers to linearity: 3 basic architectures.

DeWitt et al., GAMMA DB Machine

Query Execution Concurrency and Recovery Availability, Fault Tolerance: Chained Declustering Performance Results Missing Research Issues (biggies!):

Some Themes in Parallel DBs

That distinguish them from other parallel programming tasks.

Exchange: Encapsulation of Parallelism

And comm & connecting push/pull.


Background: NOW-Sort was a CS286 project that ended up being the world's fastest sorting machine for 2 years, generating a number of papers.  It was an amazing feat, but they could only get it to run at record speed late at night, with much hand-holding.  The problems were in the (sometimes transient) performance heterogeneity of machines. So, a cluster-based I/O intensive system should be tolerant to performance heterogeneity.  River was an attempt to do that.  It used two mechanisms:
  1. For balancing different rates of data consumption, a distributed queue (DQ) allows workers to consume data at varying rates (like two people on a date, "slurping a single milkshake from two straws").  Comes from shared-memory work.
  2. For balancing different rates of data production, the graduated declustering (GD) scheme generalized gamma's "chained declustering" to handle slow-downs, not just failures, and ensure that each disk feeds its natural share of the data.
The DQ mechanism is based on a very simple randomized "push" scheme, in which each producer randomly picks a destination for the next datum, subject to a constraint on the number of outstanding unconsumed items at each destination. Note that DQ's are encapsulated into the equivalent of local "exchange" operators (DQsend modules and DQrecv modules)

The GD mechanism uses a more sophisticated feedback mechanism for each producer to generate data at the appropriate relative rates.