go.talks: add two talks by rsc
LGTM=adg
R=adg, dvyukov
CC=golang-codereviews
https://golang.org/cl/61570044
diff --git a/2013/distsys.slide b/2013/distsys.slide
new file mode 100644
index 0000000..dc1acd4
--- /dev/null
+++ b/2013/distsys.slide
@@ -0,0 +1,446 @@
+Go, for Distributed Systems
+
+Russ Cox
+Google
+
+* About the Talk
+
+I gave variants of this talk three times in 2013, once at SOSP's Programming Languages and Operating Systems (PLOS) workshop, once at MIT Lincoln Lab's annual Software Engineering Symposium, and once at Twitter's Cambridge, Massachusetts office.
+
+The talk assumes an audience familiar with the basic problems of building distributed systems. It presents Go's approach to solving some of those problems.
+
+* Go
+
+Go is an open source programming language that makes it easy to build simple, reliable, and efficient software.
+
+* History
+
+Design began in late 2007.
+
+- Robert Griesemer, Rob Pike, Ken Thompson
+- Ian Lance Taylor, Russ Cox
+
+Became open source in November 2009.
+
+Developed entirely in the open; very active community.
+Language stable as of Go 1, early 2012.
+
+* Motivation
+
+Started as an answer to software problems at Google:
+
+- multicore processors
+- networked systems
+- massive computation clusters
+- scale: 10⁷ lines of code
+- scale: 10³ programmers
+- scale: 10⁶⁺ machines (design point)
+
+* Go
+
+A simple but powerful and fun language.
+
+- start with C, remove complex parts
+- add interfaces, concurrency
+- also: garbage collection, closures, reflection, strings, ...
+
+For more background on design:
+
+- [[http://commandcenter.blogspot.com/2012/06/less-is-exponentially-more.html][Less is exponentially more]]
+- [[http://talks.golang.org/2012/splash.article][Go at Google: Language Design in the Service of Software Engineering]]
+
+* This Talk
+
+Engineering
+
+Interfaces
+
+Concurrency
+
+* Engineering
+
+* Engineering: Imports
+
+.play distsys/hello0.go
+
+import "fmt" guaranteed to read exactly one file.
+
+* Engineering: Imports
+
+ $ go get github.com/golang/glog
+
+.play distsys/hello1.go
+
+Still guaranteed to read exactly one file.
+
+Import name space is decentralized.
+
+* Engineering: Program Rewrites
+
+ $ gofmt -r 'glog.Infof -> glog.Errorf' hello1.go
+ package main
+
+ import (
+ "flag"
+ "github.com/golang/glog"
+ )
+
+ func main() {
+ flag.Set("logtostderr", "true")
+ glog.Errorf("hello, world")
+ }
+ $
+
+* Engineering: Garbage Collection
+
+In C and C++, too much programming _and_ API design is about memory management.
+
+Go has garbage collection, only.
+
+Fundamental for interfaces: memory management details do not bifurcate otherwise-similar APIs.
+
+Fundamental for concurrency: too hard to track ownership otherwise.
+
+Of course, adds cost, latency, complexity in run time system.
+
+* Engineering: Garbage Collection
+
+Experience with Java: Uncontrollable cost, too much tuning.
+
+Go lets you limit allocation by controlling memory layout.
+
+Examples:
+
+ type Ring struct {
+ R, W int
+ Data [512]byte
+ }
+
+ type Point struct {
+ X, Y int
+ }
+
+ type Rectangle struct {
+ Min, Max Point
+ }
+
+* Engineering: Garbage Collection
+
+Garbage collector implementation remains an active area of work and research.
+
+Design decision: Interior pointers are allowed, as are foreign pointers.
+
+- Cannot reuse Java GC algorithms directly.
+- But gives _programmer_ more control over allocation.
+
+Current design: parallel mark-and-sweep.
+With care to use memory wisely, works well in production.
+
+* Interfaces
+
+* Interfaces
+
+An interface defines a set of methods.
+
+ package io
+
+ type Writer interface {
+ Write(data []byte) (n int, err error)
+ }
+
+* Interfaces
+
+A type implements the interface by implementing the methods.
+
+ package bytes
+
+ type Buffer struct {
+ ...
+ }
+
+ func (b *Buffer) Write(data []byte) (n int, err error) {
+ ...
+ }
+
+* Interfaces
+
+An implementation of an interface can be assigned to a variable of that interface type.
+
+ package fmt
+
+ func Fprintf(w io.Writer, format string, args ...interface{})
+
+* Interfaces
+
+.play distsys/writebuffer.go /^func.main/+1,/^}/-1
+
+* Interfaces
+
+Reader is the obvious counterpart.
+
+ package io
+
+ type Reader interface {
+ Read(data []byte) (n int, err error)
+ }
+
+ func Copy(dst Writer, src Reader) (n int64, err error)
+
+* Interfaces
+
+.play distsys/writebuffer2.go /^func.main/+1,/^}/-1
+
+* Interfaces
+
+Reader and Writer turn out to be very useful.
+
+Adapters
+
+ package io
+
+ func MultiWriter(writers ...Writer) Writer
+ MultiWriter creates a writer that duplicates its writes to all the
+ provided writers, similar to the Unix tee(1) command.
+
+Chaining
+
+ package gzip // compress/gzip
+
+ func NewWriter(w io.Writer) *Writer
+
+Also: buffered writers, encrypted writers, limited writers, HTTP responses.
+
+* Interfaces
+
+Networking:
+
+ package net
+
+ type Conn interface {
+ Read(b []byte) (n int, err error)
+ Write(b []byte) (n int, err error)
+ Close() error
+
+ LocalAddr() Addr
+ RemoteAddr() Addr
+
+ SetDeadline(t time.Time) error
+ SetReadDeadline(t time.Time) error
+ SetWriteDeadline(t time.Time) error
+ }
+
+ func Dial(network, address string) (Conn, error)
+
+* Interfaces
+
+Networking example:
+
+.play distsys/finger.go /^func.finger/+1,/^}/-1
+
+* Interfaces
+
+Networking client as adapter function:
+
+ package smtp
+
+ func NewClient(conn net.Conn, host string) (*Client, error)
+
+Other implementations of net.Conn: testing, SSL, ...
+
+* Interface Lessons
+
+Key advantages:
+
+- no dependence between interface and implementation
+- expressive composition
+- easy testing
+- avoids overdesign, rigid hierarchy of inheritance-based OO
+
+The source of all generality in the Go language.
+
+* Concurrency
+
+* Concurrency vs Parallelism
+
+Concurrency is about dealing with lots of things at once.
+
+Parallelism is about doing lots of things at once.
+
+Concurrency is about structure, parallelism is about execution.
+
+Concurrency provides a way to structure a solution to solve a problem that may be parallelizable (or not).
+
+* Concurrency vs Parallelism
+
+Concurrent: mouse, keyboard, display, and disk drivers in operating system.
+
+Parallel: vector dot product, matrix multiply.
+
+Concurrency can enable parallelism but is useful on its own: modern programs must deal with many things at once.
+
+* Concurrency
+
+Go provides two important concepts:
+
+A goroutine is a thread of control within the program, with its own local variables and stack. Cheap, easy to create.
+
+A channel carries typed messages between goroutines.
+
+* Concurrency
+
+.play distsys/hello.go
+
+* Concurrency: CSP
+
+Channels adopted from Hoare's Communicating Sequential Processes.
+
+- Orthogonal to rest of language
+- Can keep familiar model for computation
+- Focus on _composition_ of regular code
+
+Go _enables_ simple, safe concurrent programming.
+It doesn't _forbid_ bad programming.
+
+Caveat: not purely memory safe; sharing is legal.
+Passing a pointer over a channel is idiomatic.
+
+Experience shows this is practical.
+
+* Concurrency
+
+Sequential network address resolution, given a work list:
+
+.play distsys/addr1.go /lookup/+1,/^}/-1
+
+* Concurrency
+
+Parallel network address resolution, given a work list:
+
+.play distsys/addr2.go /lookup/+1,/^}/-1
+
+* Concurrency
+
+Aside: can abstract this pattern.
+
+.play distsys/addr3.go /lookup/+1,/^}/-1
+
+* Concurrency
+
+Aside: can abstract this pattern further (hypothetical):
+
+ var par ParallelDo
+
+ for _, w := range worklist {
+ w := w // copy iteration variable
+ par.Do(func() {
+ w.addrs, w.err = net.LookupHost(w.host)
+ })
+ )
+
+ par.Wait()
+
+But it's still useful to be able to construct alternate patterns.
+
+* Concurrency
+
+Bounded parallelism:
+
+.play distsys/addr4.go /lookup/+1,/^}/-1
+
+* Concurrency
+
+Bounded parallelism, 2:
+
+.play distsys/addr5.go /lookup/+1,/^}/-1
+
+* Concurrency:
+
+Aside: can abstract (still hypothetical):
+
+ par.Limit(10)
+
+ for _, w := range work {
+ w := w // copy iteration variable
+ par.Do(func() {
+ w.addrs, w.err = net.LookupHost(w.host)
+ })
+ )
+
+ par.Wait()
+
+* Concurrency
+
+Example: replicated storage with read and write quorums.
+
+ const (
+ F = 2
+ N = 5 // >= 2F + 1
+ ReadQuorum = F + 1
+ WriteQuorum = N - F
+ )
+
+* Concurrency
+
+Replicated write, returning after enough writes have succeeded.
+
+.play distsys/replwrite.go /^func.Write/+2,/if.delay/-2/
+
+* Concurrency
+
+Replicated read, returning after enough reads have been gathered.
+
+.play distsys/replread.go /^func.Read/+2,/if.delay/-2/
+
+* Concurrency
+
+Select allows choosing between multiple channel operations.
+
+Example, chat program:
+
+ for {
+ select {
+ case event := <-ui:
+ // process user interface event
+ case msg := <-server:
+ // process server message
+ case t := <-tick:
+ // time has elapsed
+ }
+ }
+
+* Concurrency Lessons
+
+- Key feature for building distributed systems.
+- Supported by closures and garbage collection.
+- Message passing inside program, also outside program.
+
+Most important:
+
+- Do not communicate by sharing memory.
+- Instead, share memory by communicating.
+
+* Production Use
+
+vitess/vtocc, MySQL query balancer
+
+- serves all of YouTube's MySQL queries
+- months of crash-free and leak-free operation
+
+groupcache
+
+- distributed in-memory immutable key-value cache
+- used by (parts of) dl.google.com, Blogger, Google Code, Google Fiber, production monitoring systems
+
+* More information and related talks
+
+http://golang.org/
+
+rsc@golang.org
+
+Videos:
+
+- Concurrency is not parallelism [[http://vimeo.com/49718712][video]]
+- Go concurrency patterns [[http://www.youtube.com/watch?v=f6kdp27TYZs][video]]
+- Advanced Go concurrency patterns [[http://www.youtube.com/watch?v=QDDwwePbDtw][video]]
+
+Questions?
diff --git a/2013/distsys/addr1.go b/2013/distsys/addr1.go
new file mode 100644
index 0000000..eec6605
--- /dev/null
+++ b/2013/distsys/addr1.go
@@ -0,0 +1,81 @@
+package main
+
+import (
+ "fmt"
+ "math/rand"
+ "time"
+)
+
+func lookup() {
+ for _, w := range worklist {
+ w.addrs, w.err = LookupHost(w.host)
+ }
+}
+
+func main() {
+ rand.Seed(time.Now().UnixNano())
+
+ t0 := time.Now()
+ lookup()
+
+ fmt.Printf("\n")
+ for _, w := range worklist {
+ if w.err != nil {
+ fmt.Printf("%s: error: %v\n", w.host, w.err)
+ continue
+ }
+ fmt.Printf("%s: %v\n", w.host, w.addrs)
+ }
+ fmt.Printf("total lookup time: %.3f seconds\n", time.Since(t0).Seconds())
+}
+
+var worklist = []*Work{
+ {host: "fast.com"},
+ {host: "slow.com"},
+ {host: "fast.missing.com"},
+ {host: "slow.missing.com"},
+}
+
+type Work struct {
+ host string
+ addrs []string
+ err error
+}
+
+func LookupHost(name string) (addrs []string, err error) {
+ t0 := time.Now()
+ defer func() {
+ fmt.Printf("lookup %s: %.3f seconds\n", name, time.Since(t0).Seconds())
+ }()
+ h := hosts[name]
+ if h == nil {
+ h = failure
+ }
+ return h(name)
+}
+
+type resolver func(string) ([]string, error)
+
+var hosts = map[string]resolver{
+ "fast.com": delay(10*time.Millisecond, fixedAddrs("10.0.0.1")),
+ "slow.com": delay(2*time.Second, fixedAddrs("10.0.0.4")),
+ "fast.missing.com": delay(10*time.Millisecond, failure),
+ "slow.missing.com": delay(2*time.Second, failure),
+}
+
+func fixedAddrs(addrs ...string) resolver {
+ return func(string) ([]string, error) {
+ return addrs, nil
+ }
+}
+
+func delay(d time.Duration, f resolver) resolver {
+ return func(name string) ([]string, error) {
+ time.Sleep(d/2 + time.Duration(rand.Int63n(int64(d/2))))
+ return f(name)
+ }
+}
+
+func failure(name string) ([]string, error) {
+ return nil, fmt.Errorf("unknown host %v", name)
+}
diff --git a/2013/distsys/addr2.go b/2013/distsys/addr2.go
new file mode 100644
index 0000000..2f4c3e3
--- /dev/null
+++ b/2013/distsys/addr2.go
@@ -0,0 +1,90 @@
+package main
+
+import (
+ "fmt"
+ "math/rand"
+ "time"
+)
+
+func lookup() {
+ done := make(chan bool, len(worklist))
+
+ for _, w := range worklist {
+ go func(w *Work) {
+ w.addrs, w.err = LookupHost(w.host)
+ done <- true
+ }(w)
+ }
+
+ for i := 0; i < len(worklist); i++ {
+ <-done
+ }
+}
+
+func main() {
+ rand.Seed(time.Now().UnixNano())
+
+ t0 := time.Now()
+ lookup()
+
+ fmt.Printf("\n")
+ for _, w := range worklist {
+ if w.err != nil {
+ fmt.Printf("%s: error: %v\n", w.host, w.err)
+ continue
+ }
+ fmt.Printf("%s: %v\n", w.host, w.addrs)
+ }
+ fmt.Printf("total lookup time: %.3f seconds\n", time.Since(t0).Seconds())
+}
+
+var worklist = []*Work{
+ {host: "fast.com"},
+ {host: "slow.com"},
+ {host: "fast.missing.com"},
+ {host: "slow.missing.com"},
+}
+
+type Work struct {
+ host string
+ addrs []string
+ err error
+}
+
+func LookupHost(name string) (addrs []string, err error) {
+ t0 := time.Now()
+ defer func() {
+ fmt.Printf("lookup %s: %.3f seconds\n", name, time.Since(t0).Seconds())
+ }()
+ h := hosts[name]
+ if h == nil {
+ h = failure
+ }
+ return h(name)
+}
+
+type resolver func(string) ([]string, error)
+
+var hosts = map[string]resolver{
+ "fast.com": delay(10*time.Millisecond, fixedAddrs("10.0.0.1")),
+ "slow.com": delay(2*time.Second, fixedAddrs("10.0.0.4")),
+ "fast.missing.com": delay(10*time.Millisecond, failure),
+ "slow.missing.com": delay(2*time.Second, failure),
+}
+
+func fixedAddrs(addrs ...string) resolver {
+ return func(string) ([]string, error) {
+ return addrs, nil
+ }
+}
+
+func delay(d time.Duration, f resolver) resolver {
+ return func(name string) ([]string, error) {
+ time.Sleep(d/2 + time.Duration(rand.Int63n(int64(d/2))))
+ return f(name)
+ }
+}
+
+func failure(name string) ([]string, error) {
+ return nil, fmt.Errorf("unknown host %v", name)
+}
diff --git a/2013/distsys/addr3.go b/2013/distsys/addr3.go
new file mode 100644
index 0000000..b1a1c5c
--- /dev/null
+++ b/2013/distsys/addr3.go
@@ -0,0 +1,90 @@
+package main
+
+import (
+ "fmt"
+ "math/rand"
+ "sync"
+ "time"
+)
+
+func lookup() {
+ var group sync.WaitGroup
+
+ for _, w := range worklist {
+ group.Add(1)
+ go func(w *Work) {
+ w.addrs, w.err = LookupHost(w.host)
+ group.Done()
+ }(w)
+ }
+
+ group.Wait()
+}
+
+func main() {
+ rand.Seed(time.Now().UnixNano())
+
+ t0 := time.Now()
+ lookup()
+
+ fmt.Printf("\n")
+ for _, w := range worklist {
+ if w.err != nil {
+ fmt.Printf("%s: error: %v\n", w.host, w.err)
+ continue
+ }
+ fmt.Printf("%s: %v\n", w.host, w.addrs)
+ }
+ fmt.Printf("total lookup time: %.3f seconds\n", time.Since(t0).Seconds())
+}
+
+var worklist = []*Work{
+ {host: "fast.com"},
+ {host: "slow.com"},
+ {host: "fast.missing.com"},
+ {host: "slow.missing.com"},
+}
+
+type Work struct {
+ host string
+ addrs []string
+ err error
+}
+
+func LookupHost(name string) (addrs []string, err error) {
+ t0 := time.Now()
+ defer func() {
+ fmt.Printf("lookup %s: %.3f seconds\n", name, time.Since(t0).Seconds())
+ }()
+ h := hosts[name]
+ if h == nil {
+ h = failure
+ }
+ return h(name)
+}
+
+type resolver func(string) ([]string, error)
+
+var hosts = map[string]resolver{
+ "fast.com": delay(10*time.Millisecond, fixedAddrs("10.0.0.1")),
+ "slow.com": delay(2*time.Second, fixedAddrs("10.0.0.4")),
+ "fast.missing.com": delay(10*time.Millisecond, failure),
+ "slow.missing.com": delay(2*time.Second, failure),
+}
+
+func fixedAddrs(addrs ...string) resolver {
+ return func(string) ([]string, error) {
+ return addrs, nil
+ }
+}
+
+func delay(d time.Duration, f resolver) resolver {
+ return func(name string) ([]string, error) {
+ time.Sleep(d/2 + time.Duration(rand.Int63n(int64(d/2))))
+ return f(name)
+ }
+}
+
+func failure(name string) ([]string, error) {
+ return nil, fmt.Errorf("unknown host %v", name)
+}
diff --git a/2013/distsys/addr4.go b/2013/distsys/addr4.go
new file mode 100644
index 0000000..5c6bb9e
--- /dev/null
+++ b/2013/distsys/addr4.go
@@ -0,0 +1,95 @@
+package main
+
+import (
+ "fmt"
+ "math/rand"
+ "time"
+)
+
+func lookup() {
+ const max = 2
+
+ done := make(chan bool, len(worklist))
+ limit := make(chan bool, max)
+
+ for _, w := range worklist {
+ go func(w *Work) {
+ limit <- true
+ w.addrs, w.err = LookupHost(w.host)
+ <-limit
+ done <- true
+ }(w)
+ }
+
+ for i := 0; i < len(worklist); i++ {
+ <-done
+ }
+}
+
+func main() {
+ rand.Seed(time.Now().UnixNano())
+
+ t0 := time.Now()
+ lookup()
+
+ fmt.Printf("\n")
+ for _, w := range worklist {
+ if w.err != nil {
+ fmt.Printf("%s: error: %v\n", w.host, w.err)
+ continue
+ }
+ fmt.Printf("%s: %v\n", w.host, w.addrs)
+ }
+ fmt.Printf("total lookup time: %.3f seconds\n", time.Since(t0).Seconds())
+}
+
+var worklist = []*Work{
+ {host: "fast.com"},
+ {host: "slow.com"},
+ {host: "fast.missing.com"},
+ {host: "slow.missing.com"},
+}
+
+type Work struct {
+ host string
+ addrs []string
+ err error
+}
+
+func LookupHost(name string) (addrs []string, err error) {
+ t0 := time.Now()
+ defer func() {
+ fmt.Printf("lookup %s: %.3f seconds\n", name, time.Since(t0).Seconds())
+ }()
+ h := hosts[name]
+ if h == nil {
+ h = failure
+ }
+ return h(name)
+}
+
+type resolver func(string) ([]string, error)
+
+var hosts = map[string]resolver{
+ "fast.com": delay(10*time.Millisecond, fixedAddrs("10.0.0.1")),
+ "slow.com": delay(2*time.Second, fixedAddrs("10.0.0.4")),
+ "fast.missing.com": delay(10*time.Millisecond, failure),
+ "slow.missing.com": delay(2*time.Second, failure),
+}
+
+func fixedAddrs(addrs ...string) resolver {
+ return func(string) ([]string, error) {
+ return addrs, nil
+ }
+}
+
+func delay(d time.Duration, f resolver) resolver {
+ return func(name string) ([]string, error) {
+ time.Sleep(d/2 + time.Duration(rand.Int63n(int64(d/2))))
+ return f(name)
+ }
+}
+
+func failure(name string) ([]string, error) {
+ return nil, fmt.Errorf("unknown host %v", name)
+}
diff --git a/2013/distsys/addr5.go b/2013/distsys/addr5.go
new file mode 100644
index 0000000..159f9cc
--- /dev/null
+++ b/2013/distsys/addr5.go
@@ -0,0 +1,96 @@
+package main
+
+import (
+ "fmt"
+ "math/rand"
+ "time"
+)
+
+func lookup() {
+ const max = 2
+
+ n := 0
+ done := make(chan bool, max)
+
+ for _, w := range worklist {
+ if n++; n > max {
+ <-done
+ n--
+ }
+ go func(w *Work) {
+ w.addrs, w.err = LookupHost(w.host)
+ done <- true
+ }(w)
+ }
+ for ; n > 0; n-- {
+ <-done
+ }
+}
+
+func main() {
+ rand.Seed(time.Now().UnixNano())
+
+ t0 := time.Now()
+ lookup()
+
+ fmt.Printf("\n")
+ for _, w := range worklist {
+ if w.err != nil {
+ fmt.Printf("%s: error: %v\n", w.host, w.err)
+ continue
+ }
+ fmt.Printf("%s: %v\n", w.host, w.addrs)
+ }
+ fmt.Printf("total lookup time: %.3f seconds\n", time.Since(t0).Seconds())
+}
+
+var worklist = []*Work{
+ {host: "fast.com"},
+ {host: "slow.com"},
+ {host: "fast.missing.com"},
+ {host: "slow.missing.com"},
+}
+
+type Work struct {
+ host string
+ addrs []string
+ err error
+}
+
+func LookupHost(name string) (addrs []string, err error) {
+ t0 := time.Now()
+ defer func() {
+ fmt.Printf("lookup %s: %.3f seconds\n", name, time.Since(t0).Seconds())
+ }()
+ h := hosts[name]
+ if h == nil {
+ h = failure
+ }
+ return h(name)
+}
+
+type resolver func(string) ([]string, error)
+
+var hosts = map[string]resolver{
+ "fast.com": delay(10*time.Millisecond, fixedAddrs("10.0.0.1")),
+ "slow.com": delay(2*time.Second, fixedAddrs("10.0.0.4")),
+ "fast.missing.com": delay(10*time.Millisecond, failure),
+ "slow.missing.com": delay(2*time.Second, failure),
+}
+
+func fixedAddrs(addrs ...string) resolver {
+ return func(string) ([]string, error) {
+ return addrs, nil
+ }
+}
+
+func delay(d time.Duration, f resolver) resolver {
+ return func(name string) ([]string, error) {
+ time.Sleep(d/2 + time.Duration(rand.Int63n(int64(d/2))))
+ return f(name)
+ }
+}
+
+func failure(name string) ([]string, error) {
+ return nil, fmt.Errorf("unknown host %v", name)
+}
diff --git a/2013/distsys/finger.go b/2013/distsys/finger.go
new file mode 100644
index 0000000..f1fd110
--- /dev/null
+++ b/2013/distsys/finger.go
@@ -0,0 +1,55 @@
+package main
+
+import (
+ "bufio"
+ "io"
+ "log"
+ "net"
+ "os"
+ "os/exec"
+)
+
+func main() {
+ if len(os.Args) > 1 && os.Args[1] == "serve" {
+ serve()
+ }
+ finger()
+}
+
+func finger() {
+ c, err := net.Dial("tcp", "localhost:finger")
+ if err != nil {
+ log.Fatal(err)
+ }
+ io.WriteString(c, "rsc\n")
+ io.Copy(os.Stdout, c)
+}
+
+func serve() {
+ l, err := net.Listen("tcp", "localhost:finger")
+ if err != nil {
+ log.Fatal(err)
+ }
+ for {
+ c, err := l.Accept()
+ if err != nil {
+ log.Fatal(err)
+ }
+ go serveConn(c)
+ }
+}
+
+func serveConn(c net.Conn) {
+ defer c.Close()
+
+ b := bufio.NewReader(c)
+ l, err := b.ReadString('\n')
+ if err != nil {
+ return
+ }
+
+ cmd := exec.Command("finger", l[:len(l)-1])
+ cmd.Stdout = c
+ cmd.Stderr = c
+ cmd.Run()
+}
diff --git a/2013/distsys/hello.go b/2013/distsys/hello.go
new file mode 100644
index 0000000..e7b4c83
--- /dev/null
+++ b/2013/distsys/hello.go
@@ -0,0 +1,12 @@
+package main
+
+import "fmt"
+
+func main() {
+ c := make(chan string)
+ go func() {
+ c <- "Hello"
+ c <- "World"
+ }()
+ fmt.Println(<-c, <-c)
+}
diff --git a/2013/distsys/hello0.go b/2013/distsys/hello0.go
new file mode 100644
index 0000000..c2fbf9c
--- /dev/null
+++ b/2013/distsys/hello0.go
@@ -0,0 +1,7 @@
+package main
+
+import "fmt"
+
+func main() {
+ fmt.Printf("hello, world\n")
+}
diff --git a/2013/distsys/hello1.go b/2013/distsys/hello1.go
new file mode 100644
index 0000000..4b560f3
--- /dev/null
+++ b/2013/distsys/hello1.go
@@ -0,0 +1,11 @@
+package main
+
+import (
+ "flag"
+ "github.com/golang/glog"
+)
+
+func main() {
+ flag.Set("logtostderr", "true")
+ glog.Infof("hello, world")
+}
diff --git a/2013/distsys/replread.go b/2013/distsys/replread.go
new file mode 100644
index 0000000..aae6dbe
--- /dev/null
+++ b/2013/distsys/replread.go
@@ -0,0 +1,152 @@
+package main
+
+import (
+ "fmt"
+ "math"
+ "math/rand"
+ "sync"
+ "time"
+)
+
+const (
+ F = 2
+ N = 5
+ ReadQuorum = F + 1
+ WriteQuorum = N - F
+)
+
+var delay = false
+
+type Server struct {
+ mu sync.Mutex
+ data map[string]*Data
+}
+
+type Data struct {
+ Key string
+ Value string
+ Time time.Time
+}
+
+func (srv *Server) Delay() {
+ if delay == false {
+ return
+ }
+ time.Sleep(time.Duration(math.Abs(rand.NormFloat64()*1e9 + 0.1e9)))
+}
+
+func (srv *Server) Write(req *Data) {
+ t0 := time.Now()
+ defer func() {
+ if delay {
+ fmt.Printf("write took %.3f seconds\n", time.Since(t0).Seconds())
+ }
+ }()
+
+ srv.mu.Lock()
+ defer srv.mu.Unlock()
+ srv.Delay()
+
+ if srv.data == nil {
+ srv.data = make(map[string]*Data)
+ }
+ if d := srv.data[req.Key]; d == nil || d.Time.Before(req.Time) {
+ srv.data[req.Key] = req
+ }
+}
+
+func (srv *Server) Read(key string) *Data {
+ t0 := time.Now()
+ defer func() {
+ fmt.Printf("read took %.3f seconds\n", time.Since(t0).Seconds())
+ }()
+
+ srv.mu.Lock()
+ defer srv.mu.Unlock()
+ srv.Delay()
+
+ return srv.data[key]
+}
+
+func better(x, y *Data) *Data {
+ if x == nil {
+ return y
+ }
+ if y == nil || y.Time.Before(x.Time) {
+ return x
+ }
+ return y
+}
+
+func Write(req *Data) {
+ t0 := time.Now()
+ done := make(chan bool, len(servers))
+
+ for _, srv := range servers {
+ go func(srv *Server) {
+ srv.Write(req)
+ done <- true
+ }(srv)
+ }
+
+ for n := 0; n < WriteQuorum; n++ {
+ <-done
+ }
+
+ if delay {
+ fmt.Printf("write committed at %.3f seconds\n", time.Since(t0).Seconds())
+ }
+ for n := WriteQuorum; n < N; n++ {
+ <-done
+ }
+ if delay {
+ fmt.Printf("all replicas written at %.3f seconds\n", time.Since(t0).Seconds())
+ }
+}
+
+func Read(key string) {
+ t0 := time.Now()
+ replies := make(chan *Data, len(servers))
+
+ for _, srv := range servers {
+ go func(srv *Server) {
+ replies <- srv.Read(key)
+ }(srv)
+ }
+
+ var d *Data
+ for n := 0; n < ReadQuorum; n++ {
+ d = better(d, <-replies)
+ }
+
+ if delay {
+ fmt.Printf("read committed at %.3f seconds\n", time.Since(t0).Seconds())
+ }
+
+ for n := ReadQuorum; n < N; n++ {
+ <-replies
+ }
+ if delay {
+ fmt.Printf("all replicas read at %.3f seconds\n", time.Since(t0).Seconds())
+ }
+}
+
+var servers []*Server
+
+func main() {
+ servers = make([]*Server, N)
+ for i := range servers {
+ servers[i] = new(Server)
+ }
+
+ rand.Seed(time.Now().UnixNano())
+
+ delay = false
+ Write(&Data{"hello", "there", time.Now()})
+ time.Sleep(1 * time.Millisecond)
+
+ Write(&Data{"hello", "world", time.Now()})
+
+ delay = true
+ Read("hello")
+}
diff --git a/2013/distsys/replwrite.go b/2013/distsys/replwrite.go
new file mode 100644
index 0000000..a91603f
--- /dev/null
+++ b/2013/distsys/replwrite.go
@@ -0,0 +1,152 @@
+package main
+
+import (
+ "fmt"
+ "math"
+ "math/rand"
+ "sync"
+ "time"
+)
+
+const (
+ F = 2
+ N = 5
+ ReadQuorum = F + 1
+ WriteQuorum = N - F
+)
+
+var delay = false
+
+type Server struct {
+ mu sync.Mutex
+ data map[string]*Data
+}
+
+type Data struct {
+ Key string
+ Value string
+ Time time.Time
+}
+
+func (srv *Server) Delay() {
+ if delay == false {
+ return
+ }
+ time.Sleep(time.Duration(math.Abs(rand.NormFloat64()*1e9 + 0.1e9)))
+}
+
+func (srv *Server) Write(req *Data) {
+ t0 := time.Now()
+ defer func() {
+ if delay {
+ fmt.Printf("write took %.3f seconds\n", time.Since(t0).Seconds())
+ }
+ }()
+
+ srv.mu.Lock()
+ defer srv.mu.Unlock()
+ srv.Delay()
+
+ if srv.data == nil {
+ srv.data = make(map[string]*Data)
+ }
+ if d := srv.data[req.Key]; d == nil || d.Time.Before(req.Time) {
+ srv.data[req.Key] = req
+ }
+}
+
+func (srv *Server) Read(key string) *Data {
+ t0 := time.Now()
+ defer func() {
+ fmt.Printf("read took %.3f seconds\n", time.Since(t0).Seconds())
+ }()
+
+ srv.mu.Lock()
+ defer srv.mu.Unlock()
+ srv.Delay()
+
+ return srv.data[key]
+}
+
+func better(x, y *Data) *Data {
+ if x == nil {
+ return y
+ }
+ if y == nil || y.Time.Before(x.Time) {
+ return x
+ }
+ return y
+}
+
+func Write(req *Data) {
+ t0 := time.Now()
+ done := make(chan bool, len(servers))
+
+ for _, srv := range servers {
+ go func(srv *Server) {
+ srv.Write(req)
+ done <- true
+ }(srv)
+ }
+
+ for n := 0; n < WriteQuorum; n++ {
+ <-done
+ }
+
+ if delay {
+ fmt.Printf("write committed at %.3f seconds\n", time.Since(t0).Seconds())
+ }
+ for n := WriteQuorum; n < N; n++ {
+ <-done
+ }
+ if delay {
+ fmt.Printf("all replicas written at %.3f seconds\n", time.Since(t0).Seconds())
+ }
+}
+
+func Read(key string) {
+ t0 := time.Now()
+ replies := make(chan *Data, len(servers))
+
+ for _, srv := range servers {
+ go func(srv *Server) {
+ replies <- srv.Read(key)
+ }(srv)
+ }
+
+ var d *Data
+ for n := 0; n < ReadQuorum; n++ {
+ d = better(d, <-replies)
+ }
+
+ if delay {
+ fmt.Printf("read committed at %.3f seconds\n", time.Since(t0).Seconds())
+ }
+
+ for n := ReadQuorum; n < N; n++ {
+ <-replies
+ }
+ if delay {
+ fmt.Printf("all replicas read at %.3f seconds\n", time.Since(t0).Seconds())
+ }
+}
+
+var servers []*Server
+
+func main() {
+ servers = make([]*Server, N)
+ for i := range servers {
+ servers[i] = new(Server)
+ }
+
+ rand.Seed(time.Now().UnixNano())
+
+ delay = false
+ Write(&Data{"hello", "there", time.Now()})
+ time.Sleep(1 * time.Millisecond)
+
+ delay = true
+ Write(&Data{"hello", "world", time.Now()})
+
+ // Read("hello")
+}
diff --git a/2013/distsys/writebuffer.go b/2013/distsys/writebuffer.go
new file mode 100644
index 0000000..0f00a9c
--- /dev/null
+++ b/2013/distsys/writebuffer.go
@@ -0,0 +1,18 @@
+package main
+
+import (
+ "bytes"
+ "fmt"
+ "io"
+ "os"
+)
+
+var _ = io.Copy
+
+func main() {
+ b := new(bytes.Buffer)
+ var w io.Writer
+ w = b
+ fmt.Fprintf(w, "hello, %s\n", "world")
+ os.Stdout.Write(b.Bytes())
+}
diff --git a/2013/distsys/writebuffer2.go b/2013/distsys/writebuffer2.go
new file mode 100644
index 0000000..90d9d5a
--- /dev/null
+++ b/2013/distsys/writebuffer2.go
@@ -0,0 +1,14 @@
+package main
+
+import (
+ "bytes"
+ "fmt"
+ "io"
+ "os"
+)
+
+func main() {
+ b := new(bytes.Buffer)
+ fmt.Fprintf(b, "hello, %s\n", "world")
+ io.Copy(os.Stdout, b)
+}
diff --git a/2014/research.slide b/2014/research.slide
new file mode 100644
index 0000000..4498d7c
--- /dev/null
+++ b/2014/research.slide
@@ -0,0 +1,323 @@
+The Research Problems of Implementing Go
+
+Russ Cox
+Google
+
+http://golang.org/
+
+* About the Talk
+
+I gave this talk at Google's Cambridge, Massachusetts office at an event for area Ph.D. students. The purpose of the event and the talk was to give a sense of some of the research that goes on at Google. The talk presents some research questions motivated by Go. We have answered some well, but others remain open.
+
+* About Go
+
+Go is an open source programming language that makes it easy to build simple, reliable, and efficient software.
+
+Design began in late 2007.
+
+- Robert Griesemer, Rob Pike, Ken Thompson
+- Russ Cox, Ian Lance Taylor
+
+Became open source in November 2009.
+
+Developed entirely in the open; very active community.
+Language stable as of Go 1, early 2012.
+Work continues.
+
+* Motivation for Go
+
+.image ../2012/splash/datacenter.jpg
+
+* Motivation for Go
+
+Started as an answer to software problems at Google:
+
+- multicore processors
+- networked systems
+- massive computation clusters
+- scale: 10⁷ lines of code
+- scale: 10³ programmers
+- scale: 10⁶⁺ machines (design point)
+
+Deployed: parts of YouTube, dl.google.com, Blogger, Google Code, Google Fiber, ...
+
+* Go
+
+A simple but powerful and fun language.
+
+- start with C, remove complex parts
+- add interfaces, concurrency
+- also: garbage collection, closures, reflection, strings, ...
+
+For more background on design:
+
+- [[http://commandcenter.blogspot.com/2012/06/less-is-exponentially-more.html][Less is exponentially more]]
+- [[http://talks.golang.org/2012/splash.article][Go at Google: Language Design in the Service of Software Engineering]]
+
+* Research and Go
+
+Go is designed for building production systems at Google.
+
+- Goal: make that job easier, faster, better.
+- Non-goal: break new ground in programming language research
+
+Plenty of research questions about how to implement Go well.
+
+- Concurrency
+- Polymorphism
+- Garbage collection
+- Program translation
+
+* Concurrency
+
+* Concurrency
+
+Go provides two important concepts:
+
+A goroutine is a thread of control within the program, with its own local variables and stack. Cheap, easy to create.
+
+A channel carries typed messages between goroutines.
+
+* Concurrency
+
+.play ../2013/distsys/hello.go
+
+* Concurrency: CSP
+
+Channels adopted from Hoare's Communicating Sequential Processes.
+
+- Orthogonal to rest of language
+- Can keep familiar model for computation
+- Focus on _composition_ of regular code
+
+Go _enables_ simple, safe concurrent programming.
+It doesn't _forbid_ bad programming.
+
+Caveat: not purely memory safe; sharing is legal.
+Passing a pointer over a channel is idiomatic.
+
+Experience shows this is practical.
+
+* Concurrency
+
+Sequential network address resolution, given a work list:
+
+.play ../2013/distsys/addr1.go /lookup/+1,/^}/-1
+
+* Concurrency
+
+Parallel network address resolution, given a work list:
+
+.play ../2013/distsys/addr2.go /lookup/+1,/^}/-1
+
+* Implementing Concurrency
+
+Challenge: Make channel communication scale
+
+- start with one global channel lock
+- per-channel locks, locked in address order for multi-channel operations
+
+Research question: lock-free channels?
+
+* Polymorphism
+
+* Interfaces
+
+An interface defines a set of methods.
+
+ package io
+
+ type Writer interface {
+ Write(data []byte) (n int, err error)
+ }
+
+* Interfaces
+
+A type implements the interface by implementing the methods.
+
+ package bytes
+
+ type Buffer struct {
+ ...
+ }
+
+ func (b *Buffer) Write(data []byte) (n int, err error) {
+ ...
+ }
+
+* Interfaces
+
+An implementation of an interface can be assigned to a variable of that interface type.
+
+ package fmt
+
+ func Fprintf(w io.Writer, format string, args ...interface{})
+
+* Interfaces
+
+.play ../2013/distsys/writebuffer.go /^func.main/+1,/^}/-1
+
+* Interface Advantages
+
+- no dependence between interface and implementation
+- easy testing
+- avoids overdesign, rigid hierarchy of inheritance-based OO
+
+The source of all generality in the Go language.
+
+* Implementing Interfaces
+
+How do you make method dispatch efficient?
+
+ b := new(bytes.Buffer)
+ var w io.Writer
+ w = b
+ fmt.Fprintf(w, "hello, %s\n", "world")
+ ... w.Write(text) // what happens here?
+
+At w.Write call, how does the runtime find the method to call?
+
+* Implementing Interfaces
+
+How do you make method dispatch efficient?
+
+ b := new(bytes.Buffer)
+ var w io.Writer
+ w = b // do the work here!
+ fmt.Fprintf(w, "hello, %s\n", "world")
+ ... w.Write(text) // plain indirect function call
+
+Interface holds two words: "itable" and actual value (or pointer to value).
+
+Itable contains type information plus list of function pointers for methods in interface.
+
+ w.itable.fn[1](w.data, text)
+
+Conversion sites usually trivial to cache.
+
+* Interfaces for Algorithms
+
+ package sort
+
+ type Interface interface {
+ Len() int // return number of elements, len(x)
+ Less(i, j int) bool // report whether x[i] < x[j]
+ Swap(i, j int) // x[i], x[j] = x[j], x[i]
+ }
+
+ func Sort(data Interface)
+
+Requires some boilerplate for each use:
+
+ type bySubject []Thread
+
+ func (x bySubject) Less(i, j int) bool { return x[i].Subject < x[j].Subject }
+ func (x bySubject) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
+ func (x bySubject) Len() int { return len(x) }
+
+ sort.Sort(bySubject(threads))
+
+* Polymorphism: Can we do better?
+
+ func Sort(data []T, less func(x, y *T) bool)
+
+ sort.Sort(threads, func(x, y *Thread) bool {
+ return x.Subject < y.Subject
+ })
+
+Research question: what's a reasonable semantics?
+Research question: what's a reasonable implementation?
+
+- C says don't bother.
+- C++ makes many copies of the same function.
+- Java boxes everything implicitly: one function, but expensive data model.
+- Java discards run-time type information.
+
+Do you want slow programmers, slow compilers and bloated binaries, or slow execution?
+
+* Garbage Collection
+
+* Garbage Collection
+
+Garbage collection simplifies APIs.
+
+- In C and C++, too much API design (and too much programming effort!) is about memory management.
+
+Fundamental to concurrency: too hard to track ownership otherwise.
+
+Fundamental to interfaces: memory management details do not bifurcate otherwise-similar APIs.
+
+Of course, adds cost, latency, complexity in run time system.
+
+* Avoiding Garbage Collection
+
+Observation: garbage collection is a service, and like any service it can be overloaded, oversubscribed.
+
+Go lets you limit allocation by controlling memory layout.
+
+ type Point struct {
+ X, Y int
+ }
+
+ type Rectangle struct {
+ Min, Max Point
+ }
+
+* Implementing Garbage Collection
+
+Language decision: interior pointers are allowed, as are foreign pointers
+
+- Cannot reuse Java GC algorithms directly.
+- But gives _programmer_ more control over allocation.
+
+Allocator: objects are allocated in pages with other objects of the same size.
+
+Current GC: stop the world, parallel mark, start the world, background sweep.
+
+Research question: how to make collector lower latency, possibly incremental?
+
+* Program Translation
+
+* Program Translation
+
+Go programs can be parsed without context (unlike C and C++).
+Go ships with a standard program formatter.
+
+Makes automated edits indistinguishable from manual edits.
+
+ $ cat x.go
+ package main
+
+ var b bytes.Buffer
+
+ $ gofmt -r 'bytes.Buffer -> bytes.Writer' x.go
+ package main
+
+ var b bytes.Writer
+
+ $
+
+More advanced rewrites: "go fix" for API adjustments.
+
+* Program Translation
+
+Research Question: What about translating other programs to Go?
+
+Exploring the conversion of C programs to Go today.
+
+- Decide return type (for example, int vs bool).
+- Decide which variables are pointers vs arrays.
+- Decide which functions are really methods.
+- Decide natural package boundaries.
+
+What about other languages?
+
+* Research and Go
+
+Plenty of research questions about how to implement Go well.
+
+- Concurrency
+- Polymorphism
+- Garbage collection
+- Program translation
+
