RPC、线程与 Go 并发

6.5840 2026 Lecture 2: Threads and RPC

Topic: implementing distributed systems
  ... and Go programming for the labs
  Go threads, and the web crawler
  Go RPC
  Details are Go specific but the concepts are important and widely used

Why Go?
  good support for threads
  convenient RPC
  type- and memory- safe
  garbage-collected (no use after freeing problems)
    threads + GC is particularly attractive!
  not too complex
  Go is often used in distributed systems

After the tutorial, use https://golang.org/doc/effective_go.html

Threads
  a useful structuring tool, but can be tricky
  Go calls them goroutines; everyone else calls them threads

Thread = "thread of execution"
  threads allow one program to do many things at once
  each thread executes serially, just like a non-threaded program
  the threads share memory
  each thread includes some per-thread state:
    program counter, registers, stack

Why threads?
  I/O concurrency
    Client sends requests to many servers in parallel and waits for replies.
    Server processes many simultaneous client requests.
      Each request may block.
      While waiting for the disk to read data for client X,
        process a request from client Y.
  Multicore performance
    Execute code in parallel on several cores.
  Convenience
    In background, once per second, check whether each worker is still alive.

Is there an alternative to threads?
  Yes: write code that explicitly interleaves activities, in a single thread.
    Usually called "event-driven."
  Keep a table of state about each activity, e.g. each client request.
  One "event" loop that:
    checks for new input for each activity (e.g. arrival of reply from server),
    does the next step for each activity,
    updates state.
  Event-driven can get you I/O concurrency,
    and eliminates thread costs (which can be substantial),
    but doesn't get multi-core speedup,
    and is painful to program.

Threading challenges:
  sharing data safely
    what if two threads do n = n + 1 at the same time?
      or one thread reads while another increments?
    this is a "race"
      = two threads use same memory at same time, one (or both) writes
      often a bug
    -> use locks (Go's sync.Mutex)
    -> or avoid sharing mutable data
  coordination between threads
    one thread is producing data, another thread is consuming it
      how can the consumer wait (and release the CPU)?
      how can the producer wake up the consumer?
    -> use Go channels or sync.Cond or sync.WaitGroup
  deadlock
    a cycle of threads waiting for each other
    via locks, or channels, or RPC

Let's look at the tutorial's web crawler as a threading example.

What is a web crawler?
  goal: fetch all web pages, e.g. to feed to an indexer
  you give it a starting web page
  it recursively follows all links
  [diagram: pages, links, a DAG, a cycle]
  but don't fetch a given page more than once
    and don't get stuck in cycles

Crawler challenges
  Exploit I/O concurrency
    Network latency is more limiting than network capacity
      internet latency: maybe 0.1 seconds, due to speed of light &c
      internet throughput: maybe MB/sec or GB/sec
    Fetch many pages in parallel
      To increase URLs fetched per second
    => Use threads for concurrency
  Fetch each URL only *once*
    avoid wasting network bandwidth
    avoid link cycles
    be nice to remote servers
    => Need to remember which URLs visited
  Know when finished

We'll look at three solutions [crawler.go on schedule page]
  Serial
  Concurrent, coordination via shared data
  Concurrent, coordination via channels

Serial crawler:
  performs depth-first exploration via recursive Serial calls
  the "fetched" map avoids repeats, breaks cycles
    a single map, passed by reference, caller sees callee's updates
  finished when all [recursive] links are explored: easy
  but: fetches only one page at a time -- slow
    can we just put a "go" in front of the Serial() call?
    what will happen?
    let's try it... what happened?

ConcurrentMutex crawler:
  Creates a thread for each page fetch
    Many concurrent fetches, higher fetch rate
  the "go func" creates a goroutine and starts it running
    func... is an "anonymous function"
  The threads share the fs.fetched map
    So only one thread will fetch any given page
  Why the Mutex (Lock() and Unlock()) in testAndSet()?
    One reason:
      Two threads make simultaneous calls to ConcurrentMutex() with same URL
        Due to two different pages containing link to same URL
      T1 reads fetched[url], T2 reads fetched[url]
      Both see that url hasn't been fetched (fetched[url] = false)
      Both fetch, which is wrong
      The mutex causes one to wait while the other does both check and set
        So only one thread sees fetched[url]==false
      We say "the lock protects fs.fetched[]"
        But note Go does not enforce any relationship between locks and data!
      The code between lock/unlock is often called a "critical section"
    Another reason:
      Internally, map is a complex data structure (tree? expandable hash?)
      Concurrent update/update may wreck internal invariants
      Concurrent update/read may crash the read
    defer...
    What if I comment out Lock() / Unlock()?
      go run crawler.go
        Does it always work? Always fail? Why?
      go run -race crawler.go
        Detects races even when output is correct!
    What if I forget to Unlock()?  deadlock
  How does the ConcurrentMutex crawler decide it is done?
    sync.WaitGroup -- it's basically a counter
    Wait() waits for all Add()s to be balanced by Done()s
      i.e. waits for all child threads to finish
    [diagram: tree of goroutines, overlaid on cyclic URL graph]
    there's a WaitGroup per node in the tree
  How many concurrent threads might there be?

ConcurrentChannel crawler
  a Go channel:
    a channel is an object
      ch := make(chan int)
    a channel lets one thread send an object to another thread
    ch <- x
      the sender waits until some goroutine receives
    y := <- ch
      a receiver waits until some goroutine sends
    also: for y := range ch
    channels both communicate and synchronize
    several threads can send and receive on a channel
    send+recv takes less than a microsecond -- fairly cheap
    remember: sender blocks until the receiver receives!
      "synchronous"
      watch out for deadlock
  ConcurrentChannel coordinator()
    coordinator() creates a worker goroutine to fetch each page
    worker() sends slice of page's URLs on a channel
      multiple workers send on the single channel
    coordinator() reads URL slices from the channel
  At what line does the coordinator wait?
    Does the coordinator use CPU time while it waits?
  Note: there is no recursion here; coordinator() creates all workers.
  Note: no need to lock the fetched map, because it isn't shared!
  How does the coordinator know it is done?
    Keeps count of workers in n.
    Each worker sends exactly one item on channel.
  The channel does two things:
    1. communication of values.
    2. notification of events (e.g. thread termination).

Why is it safe for multiple threads use the same channel?

Is this a race:
  Worker thread modifies (creates) url slice, coordinator uses it?
  * worker only writes slice *before* sending
  * coordinator only reads slice *after* receiving
  So they can't use the slice at the same time, so there's no race.

Why does ConcurrentChannel() create a goroutine just for "ch <- ..."?
  Let's get rid of the goroutine...

When to use sharing and locks, versus channels?
  Most (all?) problems can be solved in either style
  What makes the most sense depends on how the programmer thinks
    state -- sharing and locks
    communication -- channels
  For the 6.824 labs, I recommend sync.Mutex/sync.Cond for shared state

Remote Procedure Call (RPC)
  a key piece of distributed system machinery; all the labs use RPC
  goal: easy-to-program client/server communication
  hide details of network protocols
  convert data (strings, arrays, maps, &c) to "wire format"
  portability / interoperability

RPC message diagram:
  Client             Server
    request--->
       <---response

Software structure
  client app        handler fns
   stub fns         dispatcher
   RPC lib           RPC lib
     net  ------------ net

Go example: kv.go on schedule page
  A toy key/value storage server -- Put(key,value), Get(key)->value
  Uses Go's RPC library
  Common:
    Declare Args and Reply struct for each server handler.
  Client:
    connect()'s Dial() creates a TCP connection to the server
    get() and put() are client "stubs"
    Call() asks the RPC library to perform the call
      you specify connection, function name, arguments, place to put reply
      library marshalls args, sends request, waits, unmarshalls reply
      return value from Call() indicates whether it got a reply
      usually you'll also have a reply.Err indicating service-level failure
  Server:
    Go requires server to declare an object with methods as RPC handlers
    Server then registers that object with the RPC library
    Server accepts TCP connections, gives them to RPC library
    The RPC library
      reads each request
      creates a new goroutine for this request
      unmarshalls request
      looks up the named object (in table create by Register())
      calls the object's named method (dispatch)
      marshalls reply
      writes reply on TCP connection
    The server's Get() and Put() handlers
      Must lock, since RPC library creates a new goroutine for each request
      read args; modify reply

A few details:
  Binding: how does client know what server computer to talk to?
    For Go's RPC, server name/port is an argument to Dial
    Big systems have some kind of name or configuration server
  Marshalling: format data into packets
    Go's RPC library can pass strings, arrays, objects, maps, &c
    Go passes pointers by copying the pointed-to data
    Cannot pass channels or functions
    Marshals only exported fields (i.e., fields w/ CAPITAL letter)

RPC problem: what to do about failures?
  e.g. lost packet, broken network, slow server, crashed server

What does a failure look like to the client RPC library?
  Client never sees a response from the server
  Client does *not* know if the server saw the request!
    [diagram of losses at various points]
    Maybe server never saw the request
    Maybe server executed, crashed just before sending reply
    Maybe server executed, but network died just before delivering reply
  Remote procedure call doesn't behave the same as procedure call on a single machine!
    A recurring challenge in implementing distributed systems

Simplest failure-handling scheme: "best-effort RPC"
  Call() waits for response for a while
  If none arrives, re-send the request
  Do this a few times
  Then give up and return an error

Q: is "best effort" easy for applications to cope with?

A particularly bad situation:
  client executes
    Put("k", 10);
    Put("k", 20);
  both succeed
  what will Get("k") yield?
  [diagram, timeout, re-send, original arrives late]

Q: is best effort ever OK?
   read-only operations
   operations that it's harmless to repeat
     e.g. DB checks if record has already been inserted

Other common semantics: at-most-once
  For example, Go RPC is a simple form of "at-most-once"
    open TCP connection
    write request to TCP connection
    Go RPC never re-sends a request
      So server won't see duplicate requests
    Go RPC code returns an error if it doesn't get a reply
      perhaps after a timeout (from TCP)
      perhaps server didn't see request
      perhaps server processed request but server/net failed before reply came back
  Labs explore others way of implementing at-most-once
    No retry is too restrictive for replicated servers
    Like to retry at another replica if first replica fails

package main

import (
    "fmt"
    "sync"
)

//
// Several solutions to the crawler exercise from the Go tutorial
// https://tour.golang.org/concurrency/10
//

//
// Serial crawler
//

func Serial(url string, fetcher Fetcher, fetched map[string]bool) {
    if fetched[url] {
        return
    }
    fetched[url] = true
    urls, err := fetcher.Fetch(url)
    if err != nil {
        return
    }
    for _, u := range urls {
        Serial(u, fetcher, fetched)
    }
}

//
// Concurrent crawler with shared state and Mutex
//

type fetchState struct {
    mu      sync.Mutex
    fetched map[string]bool
}

func (fs *fetchState) testAndSet(url string) bool {
    fs.mu.Lock()
    defer fs.mu.Unlock()
    r := fs.fetched[url]
    fs.fetched[url] = true
    return r
}

func ConcurrentMutex(url string, fetcher Fetcher, fs *fetchState) {
    if fs.testAndSet(url) {
        return
    }
    urls, err := fetcher.Fetch(url)
    if err != nil {
        return
    }
    var done sync.WaitGroup
    for _, u := range urls {
        done.Add(1)
        go func(u string) {
            ConcurrentMutex(u, fetcher, fs)
            done.Done()
        }(u)
    }
    done.Wait()
}

func makeState() *fetchState {
    return &fetchState{fetched: make(map[string]bool)}
}

//
// Concurrent crawler with channels
//

func worker(url string, ch chan []string, fetcher Fetcher) {
    urls, err := fetcher.Fetch(url)
    if err != nil {
        ch <- []string{}
    } else {
        ch <- urls
    }
}

func coordinator(ch chan []string, fetcher Fetcher) {
    n := 1
    fetched := make(map[string]bool)
    for urls := range ch {
        for _, u := range urls {
            if fetched[u] == false {
                fetched[u] = true
                n += 1
                go worker(u, ch, fetcher)
            }
        }
        n -= 1
        if n == 0 {
            break
        }
    }
}

func ConcurrentChannel(url string, fetcher Fetcher) {
    ch := make(chan []string)
    go func() {
        ch <- []string{url}
    }()
    coordinator(ch, fetcher)
}

//
// main
//

func main() {
    fmt.Printf("=== Serial===\n")
    Serial("http://golang.org/", fetcher, make(map[string]bool))

    fmt.Printf("=== ConcurrentMutex ===\n")
    ConcurrentMutex("http://golang.org/", fetcher, makeState())

    fmt.Printf("=== ConcurrentChannel ===\n")
    ConcurrentChannel("http://golang.org/", fetcher)
}

//
// Fetcher
//

type Fetcher interface {
    // Fetch returns a slice of URLs found on the page.
    Fetch(url string) (urls []string, err error)
}

// fakeFetcher is Fetcher that returns canned results.
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
    body string
    urls []string
}

func (f fakeFetcher) Fetch(url string) ([]string, error) {
    if res, ok := f[url]; ok {
        fmt.Printf("found:   %s\n", url)
        return res.urls, nil
    }
    fmt.Printf("missing: %s\n", url)
    return nil, fmt.Errorf("not found: %s", url)
}

// fetcher is a populated fakeFetcher.
var fetcher = fakeFetcher{
    "http://golang.org/": &fakeResult{
        "The Go Programming Language",
        []string{
            "http://golang.org/pkg/",
            "http://golang.org/cmd/",
        },
    },
    "http://golang.org/pkg/": &fakeResult{
        "Packages",
        []string{
            "http://golang.org/",
            "http://golang.org/cmd/",
            "http://golang.org/pkg/fmt/",
            "http://golang.org/pkg/os/",
        },
    },
    "http://golang.org/pkg/fmt/": &fakeResult{
        "Package fmt",
        []string{
            "http://golang.org/",
            "http://golang.org/pkg/",
        },
    },
    "http://golang.org/pkg/os/": &fakeResult{
        "Package os",
        []string{
            "http://golang.org/",
            "http://golang.org/pkg/",
        },
    },
}

package main

import (
    "fmt"
    "log"
    "net"
    "net/rpc"
    "sync"
)

//
// Common RPC request/reply definitions
//

type PutArgs struct {
    Key   string
    Value string
}

type PutReply struct {
}

type GetArgs struct {
    Key string
}

type GetReply struct {
    Value string
}

//
// Client
//

func connect() *rpc.Client {
    client, err := rpc.Dial("tcp", ":1234")
    if err != nil {
        log.Fatal("dialing:", err)
    }
    return client
}

func get(key string) string {
    client := connect()
    args := GetArgs{ key }
    reply := GetReply{}
    err := client.Call("KV.Get", &args, &reply)
    if err != nil {
        log.Fatal("error:", err)
    }
    client.Close()
    return reply.Value
}

func put(key string, val string) {
    client := connect()
    args := PutArgs{ key, val }
    reply := PutReply{}
    err := client.Call("KV.Put", &args, &reply)
    if err != nil {
        log.Fatal("error:", err)
    }
    client.Close()
}

//
// Server
//

type KV struct {
    mu   sync.Mutex
    data map[string]string
}

func server() {
    kv := &KV{data: map[string]string{}}
    rpcs := rpc.NewServer()
    rpcs.Register(kv)
    l, e := net.Listen("tcp", ":1234")
    if e != nil {
        log.Fatal("listen error:", e)
    }
    go func() {
        for {
            conn, err := l.Accept()
            if err == nil {
                go rpcs.ServeConn(conn)
            } else {
                break
            }
        }
        l.Close()
    }()
}

func (kv *KV) Get(args *GetArgs, reply *GetReply) error {
    kv.mu.Lock()
    defer kv.mu.Unlock()

    reply.Value = kv.data[args.Key]

    return nil
}

func (kv *KV) Put(args *PutArgs, reply *PutReply) error {
    kv.mu.Lock()
    defer kv.mu.Unlock()

    kv.data[args.Key] = args.Value

    return nil
}

//
// main
//

func main() {
    server()

    put("subject", "6.5840")
    fmt.Printf("Put(subject, 6.5840) done\n")
    fmt.Printf("get(subject) -> %s\n", get("subject"))
}

Go FAQ

Q: Why does 6.5840 use Go for the labs?

A: Until a few years ago 6.5840 used C++, which worked well. Go works a
little better for 6.5840 labs for a couple of reasons. Go is garbage
collected and type-safe, which eliminates some common classes of bugs.
Go has good support for threads (goroutines), and a nice RPC package,
which are directly useful in 6.5840. Threads and garbage collection
work particularly well together, since garbage collection can
eliminate programmer effort to decide when the last thread using an
object has stopped using it. There are other languages with these
features that would probably work fine for 6.5840 labs, such as Java.

Q: are there any tips/tricks for building an intuition of how to build
effective Go code?

A: Get experience by writing Go code and reading other's people go
code.  This page has many useful tips: https://go.dev/doc/effective_go

Q: Do goroutines run in parallel? Can you use them to increase
performance?

A: Go's goroutines are the same as threads in other languages. The Go
runtime executes goroutines on all available cores, in parallel. If
there are fewer cores than runnable goroutines, the runtime will
pre-emptively time-share the cores among goroutines.

Q: How do Go channels work? How does Go make sure they are
synchronized between the many possible goroutines?

A: You can see the source at https://golang.org/src/runtime/chan.go,
though it is not easy to follow.

At a high level, a chan is a struct holding a buffer and a lock.
Sending on a channel involves acquiring the lock, waiting (perhaps
releasing the CPU) until some thread is receiving, and handing off the
message. Receiving involves acquiring the lock and waiting for a
sender. You could implement your own channels with Go sync.Mutex and
sync.Cond.

Q: I'm using a channel to wake up another goroutine, by sending a
dummy bool on the channel. But if that other goroutine is already
running (and thus not receiving on the channel), the sending goroutine
blocks. What should I do?

A: Try condition variables (Go's sync.Cond) rather than channels.
Condition variables work well to alert goroutines that may (or may
not) be waiting for something. Channels, because they are synchronous,
are awkward if you're not sure if there will be a goroutine waiting at
the other end of the channel.

Q: How can I have a goroutine wait for input from any one of a number
of different channels? Trying to receive on any one channel blocks if
there's nothing to read, preventing the goroutine from checking other
channels.

A: Try creating a separate goroutine for each channel, and have each
goroutine block on its channel. That's not always possible, but when
it works it's often the simplest approach.

Otherwise try Go's select.

Q: When should we use sync.WaitGroup instead of channels? and vice versa?

A: WaitGroup is fairly special-purpose; it's only useful when waiting
for a bunch of activities to complete. Channels are more
general-purpose; for example, you can communicate values over
channels. You can wait for multiple goroutines using channels, though it
takes a few more lines of code than with WaitGroup.

Q: I need my code to perform a task once per second. What's the
easiest way to do that?

A: Create a goroutine dedicated to that periodic task. It should have
a loop that uses time.Sleep() to pause for a second, and then do the
task, and then loop around to the time.Sleep().

Q: How do we know when the overhead of spawning goroutines exceeds
the concurrency we gain from them?

A: It depends! If your machine has 16 cores, and you are looking for
CPU parallelism, you should have roughly 16 executable goroutines. If
it takes 0.1 second of real time to fetch a web page, and your network
is capable of transmitting 100 web pages per second, you probably need
about 10 goroutines concurrently fetching in order to use all of the
network capacity. Experimentally, as you increase the number of
goroutines, for a while you'll see increased throughput, and then
you'll stop getting more throughput; at that point you have enough
goroutines from the point of view of performance.

Q: How would one create a Go channel that connects over the Internet?
How would one specify the protocol to use to send messages?

A: A Go channel only works within a single program; channels cannot be
used to talk to other programs or other computers.

Have a look at Go's RPC package, which lets you talk to other Go
programs over the Internet:

  https://golang.org/pkg/net/rpc/

Q: What are some important/useful Go-specific concurrency patterns to know?

A: Here's a slide deck on this topic, from a Go expert:

https://talks.golang.org/2012/concurrency.slide

Q: How are slices implemented?

A: A slice is an object that contains a pointer to an array and a start and
end index into that array. This arrangement allows multiple slices to
share an underlying array, with each slice perhaps exposing a different
range of array elements.

Here's a more extended discussion:

  https://blog.golang.org/go-slices-usage-and-internals

I use slices often, and arrays never. A Go slice is more flexible than
a Go array since an array's size is part of its type, whereas a
function that takes a slice as argument can take a slice of any
length.

Q: What are common debugging tools people use for Go?

A: fmt.Printf()

As far as I know there's not a great debugger for Go, though gdb can be
made to work:

https://golang.org/doc/gdb

In any case, for most bugs I've found fmt.Printf() to be an extremely
effective debugging tool.

Q: When is it right to use a synchronous RPC call and when is it right to
use an asynchronous RPC call?

A: Most code needs the RPC reply before it can proceed; in that case it
makes sense to use synchronous RPC.

But sometimes a client wants to launch many concurrent RPCs; in that
case async may be better. Or the client wants to do other work while it
waits for the RPC to complete, perhaps because the server is far away
(so speed-of-light time is high) or because the server might not be
reachable so that the RPC suffers a long timeout period.

I have never used async RPC in Go. When I want to send an RPC but not
have to wait for the result, I create a goroutine, and have the
goroutine make a synchronous Call().

Q: Is Go used in industry?

A: Yes. You can see an estimate of how much different programming
languages are used here:

https://www.tiobe.com/tiobe-index/

Q: What are common problems that developers face when starting with Go?

A:  Here are a few:

- Not protecting maps with locks when there is concurrent access. Use
  Go's race detector!

- Deadlocks with channels.

- Not capturing a variable when creating a goroutine.

- Leaking goroutines.

Q: Does Go support inheritance? (In the Java/C++ kind of "extends" way?)

A: Go doesn't support C++ style inheritance but has generics,
interfaces, and embedded structs, which allow you to do many things
for which you would use inheritance in C++.

Q: The thing I found most confusing about the Go tutorial was that
goroutines don't continue executing after the main thread has
completed. I don't think this was mentioned explicitly anywhere in the
tutorial; I figured it out through debuging the crawler exercise.

A: Yes, I don't think it is in the tutorial, but the language spec is
explicit about this: https://golang.org/ref/spec (see Program
execution).

Q: I'm still a little confused about when to choose value or pointer
receivers. Can you provide any concrete/real-world examples of when we
would choose one over the other?

A: When you want to modify the state of the receiver, you have to use
pointer receivers.  If the struct is very big, you probably want to
use a pointer receiver because value receivers operate on a copy.  If
neither applies, you can use a value receiver.  However, be careful
with value receivers; e.g., if you have a mutex in a struct, you
cannot make it a value receiver, because the mutex would be copied,
defeating its purpose.