perf: faster table/block cache

[petermattis]

The existing block cache implementation uses the Clock-PRO replacement policy. The block cache is important for performance. The raw speed of accessing the block cache is an important component of read performance. Concurrency of the block cache directly affects concurrent read performance. There are three areas worth exploring here:

1. Should the block cache be placed outside of the visibility of the Go GC. This could be accomplished by implementing our own hash table on top of arena allocated memory.
2. Improve the concurrency of the block cache, either via sharding or lock-free approaches.
3. Use a better cache replacement policy such as TinyLFU. See also Caffeine, a high-performance Java caching library.

[olekukonko]

I believe the dgraph team wants to implement a caffeine port https://blog.dgraph.io/post/caching-in-go/

[petermattis]

Pebble, like RocksDB, contains two primary caches: the block cache and the table cache. The table cache (implemented by tableCache) caches sstable.Readers. Performance experiments are currently demonstrating lock contention in the tableCache under concurrent read workloads. The tableCache internally contains an LRU list, and manipulation of the list is the problematic bit that requires mutual exclusion. The ristretto project is looking to use the same technique as Caffeine and BP-Wrapper: record page accesses in a lock-free (or thread-local) structure and then apply them in batch. Some hacky experimentation in this direction showed a 25% speedup in a concurrent scan workload.

For tableCache.findNode, we'd have a fast-path check for when the table is already in the cache that uses a RWMutex instead of a Mutex. Something like:

func (c *tableCache) findNode(meta *fileMetadata) *tableCacheNode {
	c.mu.RLock()
	if n := c.mu.nodes[meta.fileNum]; n != nil {
		atomic.AddInt32(&n.refCount, 1)
		c.mu.RUnlock()
		// TODO(peter): record access of `n`.
		return n
	}
	c.mu.RUnlock()

	c.mu.Lock()
	defer c.mu.Unlock()
	// Handle miss: we need to check c.mu.nodes again...
}

[petermattis]

Should the block cache be placed outside of the visibility of the Go GC. This could be accomplished by implementing our own hash table on top of arena allocated memory.

This is being done in #523.