JavaSpaces Principles, Patterns and Practice

Uit Aardnoot
Ga naar: navigatie, zoeken

JavaSpaces Principles, Patterns and Practice (The Jini Technology Series) by Eric Freeman, Susanne Hupfer and Ken Arnold.

A very clear and exciting book. TMO a must for anyone in computer science. Mandatory literature on distributed computing. "Evergreen". Clearly written, accessible, and with a lot of simple, yet good examples. Elegant and simple.

Oh yes, one final remark: I especially liked the many forward refererences (small jumps) that kept me focused on the issue at hand, yet very curious about what would be described next. Hard to close the book and get some sleep…

Buy it at Amazon: http://www.amazon.com/exec/obidos/ASIN/0201309556/martienfvansteen

My kick in life? See http://Martien.van.Steenbergen.nl/Thriller/

JavaSpaces Patterns Summary

Building Blocks

Shared Variable—concurrent access, atomic modifications

  • operations: read, update, increment, decrement
  • example: concurrent tellers access deposit in bank account
  • example: web counter

Bags—unordered collection of objects

  • operations: put, get
  • task bags & result bags
  • master/worker pattern

Distributed Array—ordered distributed data structure

  • operations: create, Start, End, increment, decrement, append, size, readElement
  • include position field in entries

Synchronization Patterns

Sempahore—synchronization construct

  • operations: create, up, down
  • example: license/token manager
  • watch out for deadlock: get A, get B & get B, get A & solve by allow only n - 1 getters enter (the room)
  • watch out for starvation; solve by queueing (nummertje pakken)

Round-robin synchronization

  • processes are in a ring
  • each process unique number (0...n-1), wait for your number
  • when finished, increment service number (give next in ring turn)

Barrier synchronization—synchronize a group of processes

  • a barrier is a particular point in a distributed computation that every process must reach before any process can proceed furhter
  • implemented using a shared variable: read and wait until it becomes n (n == #processes); each process increments counter upon completion

Readers/Writers

  • resource may be accessed by multiple readers or a single

writer at a given time, but not both

  • no read requests or write requests may not be postponed indefinitely
  • example: airline reservation system: seat availability: prohibit readers access during update to avoid inconsistent information
  • readers & writers are in line; when reader gets turn, immediately says to next in line" it's your turn; writer waits until all readers in front are finished, and when done gives turn to next in line; rest in line wait until writer's done
  • implementation: ticket dispenser, counter of active readers, counter whose turn it is

Communication Patterns

Building loosely coupled communication patterns.

Basic message passing:

  • pass entries from one process to another
  • sender uses write(), receiver uses take()
  • example: ping-pong (throw, catch)
  • message can be "empty" (message == ball), or contain time stamp or chess move, etc.

Characteristics of tightly coupled communication:

  • for successful rendez-vous, who, where, when must be known:
  • must know each other's identity (e.g. process ID)
  • must know each other's precise location (e.g. network address)
  • must exist at the same time

Characteristics of loosley coupled communication

  • successful rendez-vous can be anyone, anywhere, anytime
  • independent of time *and* space
  • anyone: senders and receivers don't need to know each other's identity; communicate anonymously; you don't care who picks up the message; you don't care to whom you send it
  • anywhere: as long as they can find the space for exchanging messages, senders and receivers can be anywhere; supports roaming
  • anytime: entries persist in space, so sender and receiver need not exist at same time (e.g. pong taking a break to eat)
  • any other combination is also viable: this process/anywhere/anytime, etc.
  • facilitates adding components w/o redesigning whole application
  • promotes re-use: plug in replacement player if current one is "cut off" as long as it adheres to protocol

Channels or streams

  • information conduit takes series of messages at one end, and deliver them at other end, while maintaining order
  • one or many "input" processes (writers)
  • one or many "output" processes (takers)
  • create, message position, channel tail, increment, getPosition, increment, append
  • late joiners still see "old" messages
  • bounded channels: limit number of messages to be written to channel (resource fairness reasons)
  • example: chat application, pager service

Application Patterns

Replicated-worker pattern:

  • master-worker pattern
  • parallel computing (ray tracing, encryption cracking)
  • master divides task into smaller tasks, and depositis into space (task bag)
  • workers take smaller task from space, compute result and put result back in space (result bag)
  • master collects results into meaningful overall solution
  • example: computing Mandelbrot set

Command pattern:

  • simple execute() method
  • generalized replicated-worker
  • power comes from being able to drop *object* (== state + behaviour) into a space
  • makes it easy to change between Mandelbrot and Julia computation
  • worker: startWork, execute
  • master: init, run, generateTasks, collectResults, writeTask, takeResult

Marketplace pattern:

  • producers and consumers of resources interact with each other to find the best deal (buyer/seller pattern)
  • resources can be anything: bandwidth, computing cycles, compact discs, automobiles, etc.
  • buyers specify preferences and requests bids
  • sellers specify preferences, and review requests, and make bids
  • buyers can accept bid(s)

Specialist pattern:

  • opposite of replicated-worker pattern
  • uses workers *specialized* at task (e.g. building a house requires plumbers, carpenters, foundation, roof, wiring, etc.)

Blackboard pattern:

  • specialists continually observe blackboard and raise their hands if something comes up that matches their expertise and they want to add, erase or update data
  • teacher selects expert to make a modification and decides if state of blackboard represents a solution yet or not; if not, process continues until a solution is found

Trellis pattern:

  • hierarchical graph of processes
  • to break a large problem: break problem into low-level, mid-level and high-level problems
  • information flows from low-level processes at bottom of graph and filters or percolates upwards via the mid-level processes and emerges as a birds-eye analysis by the high-level processes
  • example: add clicks % generates sales, top sight gives management information

Collaborative pattern:

  • like multiuser chat example
  • Workflow pattern: when one person finishes a piece of information, it must be copied to one or more others, etc.
  • tend to be highly specific to domain and organization
  • most collaborative patterns are custom-built for the use at hand

Leases:

  • allocate a resource for a fixed period of time
  • facilitates partial failure
  • leases can be granted (or not), renewed, cancelled, expire

Lease Maps:

  • manage may leases in a convenient way
  • e.g. renewing or cancelling a collection of leases with one operation

Automated lease renewal:

  • either because you don;t know *a priori* how long you will need aparticular resource,
  • or a space may not be willing to grant you a resource for the entire time you request

Distributed events

  • notify method
  • easier to build reactive programming style
  • can be used by non-space-based programs to react to arrival of entries in space
  • facilitates *remote* events (as opposed to inter-VM events)
  • register interest in certain events
  • example: relayer: two channels will continually receive new messages; whenever a message is received on either channel, all existing messages are transferred to a third channel

Transactions

  • fundamental tool to deal with partial failure
  • either all or non of sub-actions are completed
  • result is consistency
  • perform operations *under* a transaction
  • operation overseen by a transaction manager
  • if a transactions *commits* succesfully, *all* operations performed under transaction under it occur
  • if problems arise (like partial failure), the transaction is *aborted* and *none* of the operations occur
  • uses two-phase commit protocol
  • ACID properties: Atomicity, Consistency, Isolation, Durability
  • Atomicity: either all or non of the changes occur (read, write, take, notify)
  • if your program is correct, space will always be consistent
  • Isolation: while many transaction occur concurrently, it appears to each transaction that all other transactions complete either before or after it, but not both; i.e. two transactions should not effect each other
  • Durability changes to a space will survive failures. this requirement is loosened in Jini Transaction model
  • read vs. readIfExists

JavaSpaces Principles, Patterns and Practice [Summary] Composed and CC-BY-NC-SA 1999 by Martien van Steenbergen