Mardi Gras vs. SSD Garbage Collection

Silhouette of a hopping rabbitMardi Gras is a good time for The SSD Guy to bend your mind.  It’s the day before Ash Wednesday kicks off Lent, the penitential season leading up to Easter.

And it never seems to happen on the same date.

I will compare SSD garbage collection to the timing of the Lenten season and Easter.  There are surprising similarities.

Very few people understand why the exact date of Easter Sunday and the religious holidays that go around it seem to change dramatically from year to year.  The holidays I am talking about include Mardi Gras, Ash Wednesday, Good Friday, Holy Saturday, and Easter itself.  Note that these days always occur on the same day of the week: Easter is always Sunday, and Holy Saturday, Good Friday, Ash Wednesday, and Mardi Gras (Shrove Tuesday in English) are always on the days of the week that are in their names.  Note that “Mardi” is French for Tuesday.

All of these dates are set around Lent, the 40 days leading up to Easter, and Easter is always on a Sunday, so the holidays I named above always fall on the same days of the week.  They aren’t like New Year’s Day, which can fall on any of the seven days of the week.

Just to show how variable Easter’s dates are, I charted out the dates that Easter falls on, for the first quarter of this century.  It’s not pretty:

A scatter plot of Easter dates with years on the X-axis and dates and months on the vertical axis

But how is Easter Sunday scheduled?  Well a quick web search informs us that Easter is the first Sunday after the full Moon that occurs on or after the Vernal Equinox (the first day of spring).  If that doesn’t sound involved to you, then it soon will.

The Vernal Equinox, the day in spring when the day and night are of equal length, falls “around” the 21st of March.  It isn’t always the same date because our calendar is based on a 365-day year, but the earth really takes about 365.2425 days to orbit the sun, so the calendar date of the Vernal Equinox can change from year to year.  Still, it’s the most definite thing in the equation.  So the base point around which Easter is scheduled varies a bit.

Next we look for the first full moon after this varying date for the Equinox.  A lunar cycle, the time it takes for the moon to go from a full moon, to no moon, back to a full moon, is 29.53059 days.  So the first full moon after the Vernal Equinox could be the following day, or it could be as much as 29½ days later.  That adds nearly a month’s variance on the ever-changing date of the Equinox.

And then Easter is the Sunday after this particular full moon, which could be the following day, or it could be seven days later, depending on the year.

We have three independent variables: The date of the Vernal Equinox, the lunar cycle, and the asynchrony between the seven-day week and the 365¼-day year.

The net result is that Easter’s date can vary by as much as 38 days (if I got my math right).  So will the dates for Mardi Gras and all of those other holidays.

Moving to SSDs

So what does any of this have to do with SSD garbage collection?  (If you need a refresher on garbage collection here’s another SSD Guy blog post that will help.)

SSDs try to slip garbage collection events into idle periods between times of high I/O activity.  But the more an SSD fills up, the more often it will need to move data around to make room for new data.  The garbage collection frequency thus varies a good amount.

The time it take to complete a garbage collection task depends on how much valid data must be gathered together from mostly-invalidated blocks and moved to an erased block.  This adds another dimension of variability.  Furthermore, this chore involves flash writes, which are slower than reads and can consume a lot of time.

Sometimes a block will need to be erased to accommodate this data, in which case that block’s erase time must be added in.  This can be as much as a half second.

The scheduling of garbage collection depends on the SSD’s internal architecture.  Designers try to second-guess the best timing for garbage collection, and the host system can help by telling the SSD which data is safe to erase via the Trim command.  Still, different SSD designs will use different approaches to try to prevent garbage collection from interfering with the host’s requirements, and this adds another variable to the equation.

Meanwhile, the host, and its application programs, haven’t the vaguest idea what is happening inside the SSD.  (There is an exception, which The SSD Guy blog lightly covered in this post.)  This causes the host’s I/O requests to rarely be in synch with the SSD’s internal operations.  Some I/O transactions will occur seamlessly, while others will be delayed by garbage collection.

In summary, there’s no easy way to know how long an SSD I/O transaction will take, because none of these variables lines up with the others, just like there’s no easy way to know what date Mardi Gras will fall on in any given year!

Does your head hurt yet?  I have to admit that I have great admiration for the people who design SSDs around all of this uncertainty.