2/17

• Collin is continuing with Map-Reduce implementation
  • Unclear if rules-based code will provide full benefit
  • Seems like most "faults" arise "synchronously" so far in his case, so he could handle them by propagating them rather than having to poll for failures.
• TODO(stutsman): Move Survey of DCFT Systems up to Section 2; start writing up the Replica Manager in the paper draft
  • Concise, but complete description
  • No need to give reasons for details (segments have ordering constraints, don't explain why)
  • Eventually section will want several other short examples
    • Some from in and out of RAMCloud
  • John will do write up of the ServerList
• Interesting point to try to work in: based on Sparrow feedback
  • Everyone starts without handling faults
  • The hope is that adding fault-handling is a matter of adding try/catch.
  • Turns out it has resulted in complete rework for a us a few times.
• Another point: want to avoid rules-based programming whenever possible
  • It's less efficient, and it is hard
  • That's one reason why it's great that it is easy to intermix with threaded/imperative code
  • In several places in RAMCloud we contain fault-handling complexity within a subsystem and then the rest of the code that interacts with the system is easy

2/10 Meeting - Conversation about Actors

Similarities to Actors

• Prescriptive, constrained approach (even more so)
• Sacrifice some efficiency for ease of reasoning
• Rules -> Message Handlers (Behaviors)
• Tasks -> Actors
• Pools -> Pools (called "Frameworks" in some Actor systems)
• Both use messages to notify of failures

Differences to Actors

• Constrained so one message is handled per Actor at a time
• Shared state is disallowed, except when manipulated explicitly via messages
• Actors react to messages, not state
  • Could convert messages to state, then fire a message to induce rule recheck
• Problem: often want to trigger rules when no state updates (messages) are left
  • May be solved by doing everything with actors?
• Priority inversion issues on messages

Sound Bytes

• Rules-based code is internally synchronous, but the system is externally asynchronous. Would like a synchronous world, so we convert the async world into something synchronous. But, there are limits, which is why rules have to stay small.
• Actors: everything is asynchronous all the time; can't even get safe access to shared state.
• Question that arose: what's really the best case for Actor performance with all of the message passing?
  • Is there an efficient Actor implementation?
  • stutsman: Probably worth looking at the ('06?) Scala actor paper.
• TODO(stutsman): Read Needham, Lauer duality paper
• TODO(stutsman): Read up a bit on Actors; Hewitt papers of 60s, 70s
  • More recent canonical discussion seems to be Agha dissertation
  • Looked through that quite a bit pulled a few interesting bits out of it (see below)

Fragments from Agha Dissertation

1/27 Meeting 

TODO

• Work up an outline of the paper; send around (stutsman)
• Gather data
  • Fix TableManager in RAMCloud (stutsman)
  • Redo HDFS
    • Block replication management on NameNode
    • And/Or DataNode to DataNode block replication
  • Does Sparrow have DCFT? Could parts of it be reworked?
  • Need a strong non-RAMCloud example
    • One possibility: a system that already (implicitly) uses rules.
    • Another possibility: show a system that's a mess and show how rules clean it up.

Sound Bytes

• Think as rules rather than as algorithms
  • What is the difference to thinking in terms of threads or in terms of events?
• Claim: we don't believe a problem this hard/diverse has a one-size-fits-all solution; hence, we've tried to extract the core concepts. Implementation of the concepts will look different under contexts and requirements. The power is in the fact that the same approach can be applied to all fault-tolerant code regardless of platform, programming language, network/protocols, or even the specific types of faults that occur.
• Position strongly as a concept/experience paper
  • Probably want the word "Experience" in the title like the monitors paper
  • "Experiences with Rules-driven Programming for Fault-tolerant Systems" etc.
• Claim: several modules in RAMCloud were attempted in "traditional" threaded style, and they ended up needing to be reworked. Often, there was a tendency to want to write really simple looping, blocking, or locking code somewhere deep in places that looked like it didn't matter (success seemed guaranteed, locks seems short, etc). These were a constant thorn. We should try to list as many as we can think of.
  • BackupSelector was an offender on many occasions. Each time we'd make it a little better, without going the whole way, and each time we'd have to come back and fix it up.
    • One of the constant temptations was to "spin" in the selector waiting for new backups to get added to the list. But this prevented higher-level error handling cases from kicking in.
  • TableManager
  • BackupRecoveryManager
  • ServerList management
  • (add more as we think of them)
• Recomputing what to do next from scratch is the key to making things easier to reason about; relying in the PC is efficient, but it's burdened with assumptions that make it difficult to use effectively.
  • The rules-based approach unapologetically less efficient.
  • On the other hand, we've used it to great effect in our high-performance system.
• Rules become really critical when failure-handling may involve failure-handling. Even more so, when failure handling may be recursive, mutually-recursive, or iterative.

Collin's Random Notes

WIP distillation of thoughts on DCFT.

Hadoop MapReduce Walkthrough

MRAppMaster.java

1354: main starts here

1385: MRAppMaster constructed as appMaster

1409: initAndStartAppMaster called on appMaster

1450: initAndStartAppMaster starts here

1479: appMaster init and start, MRAppMaster is CompositeService is AbstractService, init calls serviceInit and start calls serviceStart

252: serviceInit start creates a whole bunch of event handlers that I don't what understand yet.  There are also a bunch of "Dispatchers" who's only job is to call the handle method on the correct handler object.

1019: serviceStart starts calls createJob and startJobs

632: createJob constructs a JobImpl

1251: startJobs gets the ball rolling by generating the first startJobEvent and calls the handler.

JobImpl.java

967: handle method calls doTransition on the stateMachine

299: SetupCompletedTransition()

1560: scheduleTasks

958: Issue new task event

TaskImpl.java

157: InitialScheduleTransition

879: addAndScheduleAttempt

588: Creates new TaskAttempt which is a TaskAttemptImpl and send a TA_SCHEDULE event.

TaskAttemptImpl.java

StateMachineFactory.java

This describes how the state machine works internally.  What is important to know is that the addTransition method takes the preState, postState, eventType, and transition.  The transition is an object whose transition method will be called during the doTransition method (called by the event handler).

Hadoop MapReduce State Machine Redundancy

JobImpl

TaskImpl

TaskAttemptImpl

Additional Notes:

• Event "ignore" lists is necessary in this implementation for events that come in that shouldn't affect the state machine.

No support list in Python MapReduce

• Diagnostics/Logs
• Counters
• Doesn't support reboot