Implementation and Performance of Munin

buzzword

• multiple consistency protocols
• release consistency
• shared program variables
  1. requires memory to be consistent only at the specific synchronization points
• delayed update queue
  1. buffers and merges pending outgoing writes
• prototype
  1. preprocessor
  2. modified linker
  3. library routines
  4. os
• Protocol Parameters & Sharing Annotations
• distributed queue-based synchronization protocol
• Data Object Directory
• Delayed Update Queue

Brief Summary

Instead of one big, expensive shared-memory multiprocessor, data center with many inexpensive shared-memory multiprocessors is now an difficult while hot approach. The distributed shared memory is one choice, while conventional DSM providing strong consistency is not performed well, such as the high memory latency and the high cost of sending messages.

This paper introduces a model named Munin different from conventional one in term of two parts:

• Multiple consistency protocols
• Release consistency

This paper may not be quite famous in terms of its ideas on cluster computing where MapReduce and Spark win a lot while it provides a nice usage of release consistency, which is somehow similar to Golang\’s memory model.

Strength of paper and mechanisms

• Optimized implementations for particular sharing patterns. It\’s common that one consistency can\’t fit all situations, so Munin chooses a multiple consistency model to solve this problem.
• Fix false sharing and write amplification use write diff, use hidden copy and diff to reduce the message passing overhead.
• Release consistency is an interesting idea on cluster computing. Relax consistency is required for high performance, The the primary idea is to use synchronization which sends out diff on release of lock.

Weaknesses of paper and mechanisms

• Focus too much on existing threaded code is not a long-term win. It\’s clear in Spark paper that fine-grained access is hard to optimize some fields like checkpoint and WAL.
• Fault tolerate is hard to design, according to Spark\’s paper\’s introduction, DSM style system is hard to implement fault tolerant. The typical way is a checkpoint, while it is still hard to implement.
• The high-level programmers need to know lots of related rules to do their jobs which don\’t give a good abstraction like MapReduce and Spark.

Detailed comments

The challenge of cluster computing has been extremely tough during that years. Lots of interesting ideas spring up and some implements have become extremely influential. This paper\’s idea of release consistency is influential at that time which implements a nice distributed shared memory model and relaxes the conventional distributed memory model a lot.

I like the DSM model a lot, which give programmers lots of abstraction that makes programming much easier. While the performance is not quite nice, so the tradeoff between performance and abstraction is always a hot debate. The successors like MapReduce and Spark do both parts well while restricting some programming interface which gives us much inspiration about the choice for implementing a system.

Ideas for improvement

• Maybe a leader-follower based protocol gives a new idea on how to implements a shared memory just like what GFS like.

Paper learned

• some paper is nice for some influential ideas just like the release consistency in Munin.
• The tradeoff between abstraction, consistency and even restriction should be thought a lot.