Different people have made different tradeoffs.
That’s really what we’re going to be talking about today, is, “Here are the tradeoffs
we made.
Here are the choices that we made.
Here’s why we did them, and here’s the benefits that we get for our customers and
use cases.”
First, a disclaimer.
This is based on public sources for each company.
I only work for one of these companies, so I have to go off of what they publicly say
about their architecture.
If it’s wrong, I either read the source wrong or they didn’t actually disclose it
accurately.
We won’t be covering every all-flash array architecture, because, quite frankly, some
of the ones that are out there are not all that different from traditional arrays.
Other ones don’t have a rich set of features, and so frankly, their architecture just doesn’t
have that much to talk about.
Some just aren’t that well documented.
There are just some out there that they haven’t really disclosed anything about the architecture,
so I can’t really talk about it.
All right.
Data organization and IO paths.
This is where we go real deep in the weeds in these systems.
How is data organized, placed, and located within the storage system?
This is very heavily influenced by the implementation of deduplication.
This is also a lot more complex, in most cases, than a traditional disk-based array because
of the amount of metadata involved to do the data reduction.
We saw earlier today a little bit about how XtremIO does it.
Let’s actually talk a little bit about how Pure does it.
Again, this is not saying they really talk [inaudible 00:01:26] a lot of detail.
They talk about the feature, not really how it’s done.
The primary data structure for them, the primary piece of metadata they store, is basically
a key-value store that maps from a LUN and LBA … so from a block address … to a location
in their storage for that piece of data.
You can have multiple LUNs and LBAs pointing to the same location, sharing that same piece
of data.
That’s, obviously, at some level, how sharing of data is accomplished in the system.
They need a bunch of other metadata structures to actually make all the functionality that
they want work, as well.
One is that they have something called a link table.
This is another key-value store.
What this does is keep track of those cases where you actually have multiple people all
pointing to the same block, so that when one of them overwrites the block, you don’t
actually nuke everybody else’s data.
They use a link table to keep track of that.
They use a deduplication table or deduplication hint index that keeps a abbreviated list of
checksums that are used to very quickly determine, when a block comes in, if somebody else might
already have that same block of data.
If they do, then they can address their pointers to point to that existing block.
They keep a truncated list of checksums, so they have to do a read/compare, because they’re
not using a cryptographically secure hash.
They do read/compare to make sure the block is actually correct and then update their
link table to point to that data.
Then the last piece they have, which is really complex, is this medium table.
This is really used for sharing ranges of blocks between volumes.
If I have a snapshot, and most of its data is the same as this other thing, they use
a medium table to keep track of that.
If I copy a range of blocks from one volume to another using something like X copy, they
can annotate that in this medium table rather than have to update all of their metadata,
so a shortcut to keeping track of that.
All of their metadata is stored in SSDs, in the same SSDs as the rest of their data.
They partially cache the metadata in memory.
That’s important, because it actually does mean some of their metadata lookups that they’re
actually doing in the data path actually cause a hit to the SSD to look up that metadata.
They claim it’s a relatively low percentage, but there can be some variability as a result
in terms of how many IOs you have to do to actually get to a piece of data.
If you look at their data paths … and again, this is from their presentation on this … a
read is fairly straightforward.
They basically go through their medium graph to figure out which key-value table to use.
They look up, in a tiered list of those metadata entries, the segment and offset.
Then they read that data off of the actual SSD.
On our right is a little bit more complexity.
They first walk through this medium table to figure out what metadata they’re going
to update.
They do their pattern recognition, which basically means, “Is this block all zeros?”, and
they don’t have to do anything.
They also do their dedup lookup in their hint table, reading off of the SSD to validate
it if they need to.
Once they’re sure it’s a unique block, they persist it to NVRAM, return successes
to user.
Then in the background, all of that gets compacted.
The alternate approach that SolidFire and XtremIO take is, rather than what I would
call a location-addressed approach where you’re keeping track of the location of blocks, both
of these systems use a content-based approach.
You still have something where the volume metadata is a key-value store, but instead
of mapping the LUN and LBA to a physical location somewhere, it maps the LUN and LBA to a unique
content fingerprint … we call these block IDs in our system.
I’m not sure what XtremIO calls them, but … a unique content fingerprint that’s
generated using a hash algorithm.
Obviously, multiple block locations can map to the same fingerprint, if they’re mapping
to the same piece of data.
Then you have a second metadata structure that keeps track of which block ID is located
at which location.
Typically, this metadata structure is partitioned and distributed across your cluster.
This is how you get that scale-out capability in both of these systems.
As you partition the range of block identifiers into some number of arbitrary partitions … we
call these partitions “bins” … and you distribute the hash space, if you will, across
the cluster, as your cluster expands or contracts, you can redistribute that hash space and redistribute
the blocks accordingly.
In both of these systems, all the metadata is stored on the SSD, and both of them keep
the active metadata in memory at runtime.
There’s not an additional IO to access any of the metadata.
The data paths for these are both actually fairly similar.
If you want to do a read, you look up your block ID in the volume metadata.
Again, this is in memory.
You then route your read request to the node that is responsible for that partition or
that range of block data.
In memory again, you look up the location of that block ID in the block metadata.
You read the block from SSD … in our case, we decompress it, because we actually compress
our data … and return the block to the user.
On our right, you first hash the block to compute the block identifier.
In SolidFire’s case, we compress the data.
We then store it to NVRAM.
We don’t actually do any lookups.
We don’t hit the SSD.
We don’t do anything on the right path.
We store it in NVRAM.
We replicate it to a second NVRAM on another node.
In XtremIO’s case, it’s a second controller, and it’s DRAM instead of NVRAM, but we’ll
cover that later.
Then acknowledge the right to the user.
In the background, we flush the data out of the NVRAM.
We route it to the node that’s responsible for that block ID, update our metadata, and
store it on the SSD.
Contrasting these two approaches, the biggest difference that I would call out here is that
in location-addressed, you have to keep a separate table for a deduplication hint index,
and that has to be accessible.
That hint index has to be accessible anywhere IO is coming in to be able to consult it.
With content-addressed, the deduplication is inherent to the data placement.
It’s inherent to where the data is routed in the cluster, which means that you don’t
need a centralized index for deduplication.
Really what that means is this architecture is much better to something where you want
to distribute an architecture, where you want to scale out architecture, or you want to
get to very large scales.
This architecture is fine where you can have all of the metadata, all of your tables, essentially
globally accessible.
On a dual-controller, tightly coupled architecture where you can have them all essentially globally
accessible, that works fine.
It really falls apart when you try to do scale-out with it.
All right.
Next up, eliminating unreferenced data.
How do you get rid of data that’s no longer referenced in the system?
Interestingly, this is one of the things that people don’t like to talk about.
The reason is that in a traditional block-based system, you don’t have to think about it.
In a block-based system, there is no unreferenced data.
You just overwrite data.
There’s a block.
It lives on a disk at this point.
If you overwrite it, it just overwrites that data.
Once you get into global deduplication, once you get into very heavily snapshot-optimized
architectures, there’s a lot more complexity to actually manage overwriting and figuring
out if data’s no longer used.
Interestingly, this is a place where all three systems use different approaches with different
things that they’re optimizing for.
In Pure’s case, they do their own garbage collection on the drives.
We call it recycling, because we have a different thing that refers to garbage collection in
our system.
Basically, during their own cleanup of the SSD, they would go through the SSDs, and they,
for each block on that drive, will check their mapping table that we talked about.
They basically will do a reverse lookup into their mapping table to see if that block is
still referenced.
Is this referenced in my mapping table?
Is it referenced in the link table?
Because again, I could have had other guys that came in and pointed to that same block.
If it is still referenced there, great.
It gets re-compacted with the other valid data and written back out to the SSD.
If it’s not referenced, it can be eliminated.
That’s pretty much all there is to it.
XtremIO uses an approach called reference counting.
If you recall, there’s this block metadata table that maps a block ID to the location.
It’s distributed across the nodes based on the hashes.
In that block metadata, they have a reference count.
Every time a block is written, if that block was already stored, it doesn’t have to store
it again, but it does have to update the reference count in this metadata so it knows somebody,
somewhere, is referencing it again.
When you overwrite a block, it basically goes out and tells the old block location to decrement
that reference count.
If that reference count gets down to zero, then it basically marks the space that that
block consumed as available for reuse.
They have a whole sorting algorithm they use to figure out which RAID stripes have the
most blocks available for reuse, and that’s where they write data.
Then when you have operations that trigger significant data changes … so if you delete
a volume, for example … I’ve got to go change the reference counts for every block
in that volume now.
If I do a clone of a volume, or I make a copy of that metadata, or if I do an X copy where
I’m copying a range of blocks from volume to another, they actually do a background
operation to update their reference counts.
Because that’s a lot of reference counts that need to get updated, they actually send
that off in the background and do it in the background somehow.
SolidFire uses a third approach.
We don’t use reference counting.
The main reason we don’t use reference counting is it is very error-prone when you have a
more loosely coupled system like we do.
When you have a shared-nothing system, when you have replicas that are in different locations,
if those reference counts get off, very bad things happen.
You lose data.
That’s pretty much the end of it.
In a distributed system, ensuring the consistency of those replicas is very hard.
There are computer science algorithms that will do it, but you have to implement them
properly, and they’re not particularly fast.
XtremIO doesn’t have that problem, because they have all their individual blocks of data
only exist in one location, as we talked about.
It’s in that disk shelf.
That’s the only location.
That reference count for that one location has to be correct, but that’s the only location.
We have data in at least two locations.
We have to keep, if we did reference counting, those reference counts in sync, so we don’t
do that.
Instead, the approach we use is a garbage collection approach.
It’s similar to what a Java memory manager does or a .NET memory manager, or really any
kind of managed memory system.
Basically what it does is, rather than keep a reference count, we simply keep an in-use
flag in our metadata.
On a regular interval, we run a garbage collection process.
What does that garbage collection process do?
It marks every block as not in use, and then it has the volume metadata, the ones that
actually know which block IDs are actually referenced in the metadata, communicate to
the block layer which blocks are in use.
It does this using a data structure called a Bloom filter.
This is a very computer-science thing, but basically it’s a way you compress all of
that information into a very, very compact list that we can do membership testing on
to understand which blocks are actually used in that Bloom filter, and mark those blocks
are in use.
Once we marked all the blocks are in use, anything that’s not in use can be recovered
through our recycling process.
It’s a very straightforward process, but the nice thing about it is it’s very easy
to be deterministically correct about it.
We can tell, if we processed and received all the Bloom filters we need to know, to
know that all of the blocks are accounted for.
If something goes wrong in the system, if something blows up in the middle of this process,
we just don’t do the garbage collection that cycle, and we take no chances about actually
losing data.
It’s a much safer process when you have a distributed system where things can be failing
at different times.
Looking at some of the tradeoffs between these, reference [verication 00:12:37], again, it’s
something that works well if you’ve got a very tight coupling between the storage
layer and metadata layer, because you have to be able to bounce very quickly between
them to do that reference verification.
In a distributed system, that’s nearly impossible to do correctly.
Reference counting, again, when you’ve got what I call a single source of truth for your
metadata, because you only have a single copy of that data, it works relatively well for
that.
You still have to get it perfect.