Immutability in Go

Blockchains from close up

Attempts at uncorruptible shared truths

• Conceptually a global decentralized database
• Updates periodically aggregated and broadcast
• Eventual consistency only due to competing truths

Blockchains from the inside

Most toxic ecosystems in technology... (⊙_⊙)

• Network secured through monetary incentives
• Financial value creates crypto-currency markets
• Unregulated markets incentivize malicious actors

So... where's the connection to dotGo?

Where blockchain meets Go

"Ethereum is a decentralized platform that runs smart contracts: applications that run exactly as programmed without any possibility of downtime, censorship, fraud or third party interference."

• Most complex blockchain system in production
• Second highest valuation at $1.1B (Bitcoin $9.7B)
• Network majority running the Go implementation

Where blockchain meets dotGo

19th September, 4 in the morning

• Attacker found sloppy caching in go-ethereum
• Hand crafted suite of malicious smart contracts
• 70% of Ethereum nodes simultaneously crashed

Ethereum's current state is a 2.8M node trie

• Updates, forks and rollbacks every 15 seconds
• Mutable data structures are hard to reason about

Sharing memory the Go way – Communication

Slight caveats with this model

• Sharing data via communication takes time (1)
• Maintaining superfluous copies wastes memory (2)
• Mutating local or global state prevents versioned data (3)

Sharing through immutability

Back to basics – String vs. []byte

Slices can change, but strings are immutable¹

• Strings are safe to share between goroutines
• Substrings reference the same backing memory
• Passing strings around require only shallow copies

Userspace immutability

Custom structs can be made immutable

• All fields private (irrelevant of mutability)
• Members initialized on construction
• No setters or mutators allowed

Data purity must be preserved

• External mutables copied on init
• Internal mutables copied on retrieve

Userspace immutability – Gopher

⁣

type Gopher struct {
    name    string // Immutable type
    picture []byte // Mutable type
}

func NewGopher(name string, pic []byte) *Gopher {
    g := &Gopher{
        name:    name,                   // Shallow copy immutable
        picture: make([]byte, len(pic)), // Deep copy mutable
    }
    copy(g.picture, pic)
    return g
}

func (g *Gopher) Name() string    { return g.name } // Shallow copy immutable
func (g *Gopher) Picture() []byte {                 // Deep copy mutable
    pic := make([]byte, len(g.picture))
    copy(pic, g.picture)
    return pic
}

Object composition

Arbitrarily complex object hierarchy

• Preserves all immutability benefits
• Allows intertwined memory sharing

Immutable objects need to remain light

• Immutable composition relies on copies
• Assignment and dereference must be cheap
• Nested objects better off as pointers or interfaces

Object composition – Gopher family tree

⁣

type Gopher struct {
    name    string
    picture []byte
    parents [2]*Gopher // Lightweight immutables
}

func NewGopher(name string, pic []byte, parents []*Gopher) *Gopher {
    // [...] Init basic fields as previously

    for i, parent := range parents { // Dereference any pointers
        cpy := *parent
        g.parents[i] = &cpy
    }
    return g
}

func (g *Gopher) Parent(idx int) *Gopher {
    cpy := *g.parents[idx] // Internal pointers never escape
    return &cpy
}

Structure mutation

Updates can be done (only) via recompositions

• Hierarchy unwinded until mutated object
• New immutable object created in place
• Recombine with stable fields upward

Mutations always result in new objects

• Deep updates hit the garbage collector
• Both old and new objects are valid versions

Structure mutation – Gopher family tree (1)

func ExtendFamilyTree(gopher, ancestor *Gopher, ancestry []int) *Gopher {
    mutable := *gopher // Reconstruct all objects on the update path

    if len(ancestry) == 0 {
        // Mutate the object at the deepest level
        if mutable.parents[0] == nil {
            mutable.parents[0] = ancestor
        } else {
            mutable.parents[1] = ancestor
        }
    } else {
        // Unwind and recombine objects on the update path
        index := ancestry[0]
        parent := mutable.parents[ancestry[0]]

        mutable.parents[index] = ExtendFamilyTree(parent, ancestry[1:], ancestor)
    }
    return &mutable
}

Structure mutation – Gopher family tree (2)

Lightweight object trees

• Immutable and concurrent
• Memory shared between versions

Epilogue

Data structure immutability is nice

• Enables lock free concurrent access
• Allows memory sharing via composition
• Permits easier reasoning about complexity

Data structure immutability is hard

• Go lacks supporting language constructs
• Immutables have performance and GC implications

Thank you