Infinite I/O

Under the Covers: How Infinio ensures your cache stays consistent

Posted by Vishal Misra on Aug 20, 2014
Find me on:

Maintaining consistency in any distributed system is a hard problem, and cache-coherency specifically is a very difficult problem to tackle. We all hear about ACID requirements and the CAP theorem all the time and the "C" there is always consistency.

 

So how does Infinio's distributed cache handle consistency and does our consistency protocol impose performance penalties? The answer to that is our architecture makes consistency in virtualized environments a non-issue for us, and consistency requirements have no effect whatsoever in our ability to scale.

 

Let me explain that a bit more. Infinio uses a content-based architecture, which means that rather than tracking locations that are commonly requested (like most other caches), we’re tracking the content that is commonly requested.

 

more-less-digest-1

 

Most caches work by maintaining an Address->Content map and saving that in memory or on SSD. In a shared, distributed system, if the Content on an Address is updated by a node, all cached copies of that map need to be updated simultaneously and there are cache coherency protocols that are tasked with maintaining consistency. This can present a scalability problem: as you add more nodes to the system, the time it takes to keep data consistent increases.

 

Infinio on the other hand maintains two maps, which are highlighted by the blue boxes in the two rows of Figure 1. The first map is the Address->Digest map (“A2D”), which maps addresses to the hash of the content at that address.  The other map is the Digest->Content map (“D2C”), which maps hashes to the content from which they were derived.  Our cache is composed of these two functionally and logically separate units. 

 

Each ESXi host maintains its own local A2D entries. Remember that on a per VMDK basis, ESX has single writer semantics (i.e. only a single hypervisor writes to a VMDK file) so there are no coherency issues. Two different servers ESX1 and ESX2 will never simultaneously open the same VMDK file for writing and hence will never simultaneously write at the same address. Whenever data in an address is overwritten, we update the local A2D map; since it is not shared with any other host, the notion of inconsistency is inapplicable.

 

The D2C map is our shared, distributed cache would be more likely to suffer from consistency issues. However, that's where the software's elegance shines through. Our architecture populates the D2C based on a cryptographically strong hash function, making it inherently consistent and requiring no additional overhead. If an entry exists, it is by definition unique and consistent (modulo hash collisions, but that is a hypothetical for another day).

 

To summarize, the A2D map can’t be inconsistent because it is local and VMware uses single-writer semantics. The shared and distributed part of the cache (the D2C map), is not inconsistent because it is based on a cryptographically strong hash function and hence is globally consistent by design.

 

Voila, no consistency issues.

 

If you're interested in further science behind Infinio, you can see my three-part series here.

____

Vishal is Founder and Chief Scientist of Infinio. You can follow his love for science and cricket on Twitter @vishalmisra

Topics: Talking Tech