(use a markdown extension to view, like Markdown Reader or Markview in chrome)

# Distributed systems

Decentralized:
- no single master, point-of-failure
- local control/autonomy

(often)P2P:
- all are peers
- peers are basically the same.
- file-sharing:
  - sometimes means data dist, control central

Distribution:
- distance (latency, no simultaneity, agreement difficult)
- "a DS is one where networked computers coordinate activity only by passing messages"
  - Internet, intranets, mobile devices


```
small, fast (bus-based)   <---------------------> big slow networks
    
low latency                                       high
high bandwidth                                    low
secure, reliable interconnect                     autonomous
dependent failures                                unreliable network
coordinated resources                             fear and distrust
                                                  independent failures
                                                  decentralized administration
```


### Challenges:
- private comm over public networks
  - who sent it (auth), integrity, privacy

- building reliable systems from unreliable components
  - indep failures
  - Leslie Lamport:
      
      
      A distributed system is one in which the failure of a
      machine I have never heard of can prevent me from doing my work.

- location
  - placement for efficient sharing, 
  - finding it later

- coordination and shared state
  - what should "we" do, and when?
  - can we agree on what we've done?
  - who is this "we" you speak of?


## Consequences of distribution
- concurrent processes
  - user work independently
  - non-determinism, raceconditions, sync, deadlocks, liveness
- no global clock
  - coordination through messages
  - clock sync works, but only to a degree
- no global state
  - no single process has knowledge of entire state of the system
- failures
  - node failures
  - network partitions


# Learn by building!

- Project 1: Chunks
- Project 2: Permanodes, Chunking
- Project 3: Indexer
- Project 4: File System
- Project 5: Anti-Entropy
- Project 6: Consensus



# Go

dudes at Bell labs:
- Ken Thompson		unix, turing award winner
- Rob Pike

now at google.

New *systems* programming language.

Pain points:
- slow builds
- dependency explosion - 
  /sys/stat.h included 37 times  (1984 test, probably much worse now)
  google build of a binary that totaled 4.2 MB of source turned into 8GB seen by compiler
- concurrency, multi-core support built-in
- memory allocation

## Brief tour

(from perspective of C)

- package/include system
- interfaces  
- features
  - slices
  - maps
- typesafe
- gothreads
- channels
- garbage collection

## Preliminaries:
- everything in GOPATH
- go build/install/get/run/...
- emacs go-mode comes w/ distribution

### Gotchas:
- all passed by values: pointers, but also stucts, arrays (use slices)
- no pointer arith
- ++ exists, but not expression
- no implicit conversions, but int(4.3)
- no type aliases
  - `type dint int` now distinct types
  - can add methods to user-defined types
- no ternary

**And**:
- no constructors/destructors
- no default args
- no exceptions
- no arrays of mixed type


## Packages:
- everything is part of a package
- variables, methods exported by starting with capitalized name


    package "dss"
    
    func invisible(int one) {
        ...
    }
    
    
    func Visible(int one) {
        ...
    }


called: 

    import "blah/pete/dss"
    
    dss.Visible(...)


## Memory allocation
- allocation:
  - new() zeros,
  - make() initializes, for channels, maps, slices...


## Arrays
- fixed size
- passed by value to funcs

## Slices!

	sl := arr[0:2]
	fmt.Println(sl)

	sl2 := []int{4, 5, 6}
	fmt.Println(sl2)

	sl3 := append(sl2, 7, 8)
	fmt.Println(sl3)

	sl2 = append(sl2, 9, 10)
	fmt.Println(sl2)
	fmt.Println(sl3)

[play](https://play.golang.org/p/eMseomDmtBl)

## Maps

    type Vertex struct {
         Lat, Lon, float64
    }
    
    m := map[string] Vertex {
      "one" : {40.8, -74.5},
      "two" : {41.8, -75.5},
    }

keys can be anything that can be sorted (strings, int..)

              = m["four"]
    m["four"] = ...

Returns default value if no exist.

    m["four"], ok = ...

"ok" *true* if in map


## Functions:
       func blah(i int...) int {
       func blah(i int...) (int, int) {
### Methods:
       func (d *Myobj) blah(i int...) (int, int) {


### Interfaces:
- not objects
- just method signatures
- implicit


    type Shape interface {
      func Area() int
    }

ANY type that implements the 'Area' method is implicitly a Shape

How?

Let's say I have another object:

    type Circle struct {
         radius	int
         ....
    }

Now I define:

    func (n *Circle) Area() int {	// receiver/name/args/return
         ....
    }

A Circle is now a Shape!
       - implicit (Duck typing)
       - variables

    c := new(Circle)
    
    var s Shape
    s = c

Can also define:

    func (n *Rect) Area() int ...

    var r      Rect
    s = &r


And a Rect is now a shape.



### Why maybe no good?


Cool things: stack is in the heap, so:


Allocation!

    func() *int {
           id := 2
           return &id
    }

### Anonymous functions == Closures!

    func intSeq() func() int {
         i := 0
         return func() int {
         	i += 1
    	    return i
         }
    }
    
    func main() {
         nextInt := intSeq()
         fmt.Println(nextInt())
         fmt.Println(nextInt())
         fmt.Println(nextInt())
    }
[play](https://play.golang.org/p/KIefyeKFEP)


### More fun: fib!

    func fib() func() int {
         i1, i2 := 0, 1
         return func() (r int) {
             r = i1
        	 i1, i2 = i2, i1+i2
        	 return
         }
    }
    
    func main() {
         f := fib()
         for i := 0; i < 10; i++ {
         	 fmt.Println(f())
         }
    }
[play](https://play.golang.org/p/jLDSk4Wend)


## Goroutines
Lightweight threads:

    f(x,y)
    go f(x,y)

Channels:

      ch := make(chan int, 1)
      ch <- v
      v := <-ch
      close(ch)

[play](https://play.golang.org/p/1yaX8fHrEU)

blocking sends, receives until other side ready

sync w/o explicit locks!

    ch := make(chan int, 5)		// buffered

sync library

## Homework

[copy your solution into a fresh playground, and send me the "Share" url before class Thursday](https://play.golang.org/p/dRzHYw9C0LV)


## TODO before Thursday's class
- look at the p1 description, set up your environment, look at Project 1
- solve the puzzle, send me a URL w/ a playground 


