Reigning in the Memory Manager

Hi, I'm Amit from MemCachier

MemCachier is...

• ...a cloud caching service
• ...written in Go
• ...manages many users' cache in unified large clusters
  • Easier to allocate resources to users
  • Easier to manage
  • Better utilization

Basically, we're multi-tenant memcached

Why we care about GC performance

MemCachier is latency sensitive. We need to answer queries...

• ...many times faster than a web server
• ...faster than a database
• ...within microseconds on average
• ...within milliseconds at the tail

Our servers are heavily loaded:

• ~15GB per machine
• >1GB per server process
• Millions of entries per server process

GC pauses are a killer!

The GC in Action

The GC in Action: End-to-end benchmark

    type User struct {
      entries map[string]*CacheValue
      ...metadata...
    }

    type Cache map[username]*User
  

At 1.6GB

• Steady-state GC is nearly 100ms
• Max GC is over a second!

Why is this happening?

The garbage collector has two phases:

    mark(toplevelPointers)

    func mark(ps []Pointer) {
      for _,p := range(ps) {
        setLiveBit(p)
        mark(p.Children())
      }
    }
  

    cur := firstPointerInHeap
    while cur != nil {
      next := cur.next
      if !cur.Live() {
        free(cur)  
      }
      cur = next
    }
  

The GC in Action

Lots of garbage

The GC in Action

The GC in Action: Effect of Heap Size

• As expected, GC pause time grows with heap size
• But not so bad...
  • 128MB heap size → 1-2ms pause
  • 1GB heap size → >10ms pause
• Pretty hard to avoid (but we'll address it)

The GC in Action: Effect of # Live Objects

• As expected, GC pause time grows # of live objects
• More accute problem than heap size:
  • Up to 10,000 in under 1ms
  • On the order of seconds for large numbers of pointers
• Each MemCachier server holds millions of entries → many millions of pointers

We have to get around the garbage collector...

The unsafe package

    type Pointer *ArbitraryTypepre

    1) A pointer value of any type can be converted to a Pointer.
    2) A Pointer can be converted to a pointer value of any type.
    3) A uintptr can be converted to a Pointer.
    4) A Pointer can be converted to a uintptr.
  

We can use unsafe.Pointer to do out own memory management!

For example...

type CacheValue {
  ...bunch of metadata...  
}

var greatBigSlice []byte = make([]byte, 4GB)

func Get(offset int) (*CacheValue) {
  return (*CacheValue)(unsafe.Pointer(&greatBigSlice[offset]))
}

OK, well not exactly...

The problem is that CacheValue actually looks like this:

  type CacheValue struct {
    Key          []byte
    Value        []byte
    Flags        []byte
    Expiration   time.Time
    Version      uint64        
  }
  

• The value in these fields is just a pointer
• Won't get serilized to the []byte
• It's still controlled by the memory manager

• Luckily, these happen to be the same type as the big slice
• If we just keep track of the offsets, we can store them directly

A Slab Memory Allocator

A slab memory-allocator stores memory objects in fix sized bins.

Why?

• Easier to find space to fit a new object
• Deleted items are trivial to recycle
• Can avoid compaction in many cases
• Trade internal fragmentation for external fragmentation

A Slab Memory Allocator

A Chunk represents an application-level item in the allocator

A Page is a 1MB region containing Chunks of one size.

Slabs manage pages for the same chunk sizes.

type Chunk []byte
 
type Page []byte

type Slab struct {
  Pages     []Page
  FreePage  uint16 // Next free page
  FreeItem  uint16 // Next free item slot
  ChunkSize ByteSize
}
  

A Slab Allocator

Structure of the top level Slab-based cache.

type Cache struct {
  // 15 pointers
  Slabs   [MAX_FACTOR - MIN_FACTOR + 1]Slab

  // Protects access to each slab meta data
  Slabtex [MAX_FACTOR - MIN_FACTOR + 1]sync.Mutex

  // Stores the memory location of the beginning of a chain
  // for hashed keys.
  Keys    [HASH_SLOTS]MemRef

  // Protects linked chains in the hash-map.
  Keytex  [HASH_SLOTS]sync.Mutex
}

A Slab Memory Allocator

To get data in and out of the allocator:

func (ptr MemRef) toChunk(c *Cache) Chunk {
  slab := c.GetSlab(ptr.Slab)
  page := slab.Pages[ptr.Page]
  chunkNum := ByteSize(ptr.Chunk)
  return Chunk(page[slab.ChunkSize * chunkNum:][:slab.ChunkSize])
}

func (ptr MemRef) toHeader(c *Cache) (*ItemHeader) {
  chunk := ptr.toChunk(c)
  return (*ItemHeader)(unsafe.Pointer(&chunk[0]))
}

Some cute hacks...

Cute hacks - inline assembly

Use native operations instead of log functions on Floats

TEXT ·log2Floor(SB),7,$0
	BSRQ 8(SP), AX  // 8(SP) is the first argument
	MOVQ AX, 16(SP) // store result
	RET

About an order of magnitude faster, used many times per Get/Set

Cute hacks - saving a few bytes

Instead of 64-bit pointers, we use a struct with three 16-bit indexes.

Doesn't matter alone, but helps save 4 bytes here and there when reused in other structs.

type MemRef struct {
  Slab    uint16
  Page    uint16
  Chunk   uint16
}

An end-to-end benchmark (Remember this?)

The GC with slab based version:

• Constant vs. number of MemCachier entries
• ~5-7ms in steady-state
• ~25ms maximum

Compare this to ~100ms in steady-state and 1 secondmaximum for 1GB

OK, I lied...

Use Mmap to directly allocate memory

When using make to allocate []byte, GC pauses still grew to 20ms steady state and 500ms max.

    page, err := syscall.Mmap(-1, 0, int(PAGE_SIZE),
                              syscall.PROT_READ|syscall.PROT_WRITE|syscall.PROT_EXEC,
                              syscall.MAP_ANON | syscall.MAP_PRIVATE)
  

This makes the GC totally ignore this part of the heap.

Thanks!

Check us out! memcachier.com

Contact:

• amitlevy.com
• amit@memcachier.com

Be excellent to each other!