Non-uniform randomness with drifting

Hi,

If you boil it down, fio can basically do two types of random distributions (random_distribution=):

- Uniform, meaning we scatter evenly across the IO range.
- Or zipf/pareto, meaning that we have some notion of hotness of offsets that are hit more often than others.

zipf/pareto are often used to simulate real world access patterns, where, eg, 5% of the dataset is hit 95% of the time, and having a long tail of rarely accessed data.

Something that's bothered me for a while is that a zipf/pareto distribution remains static over the runtime of the job. Real world workloads would often see a shift in what appears hot/cold and what isn't. So the attached patch is a first crude attempt at implementing that, and I'm posting it here to solicit ideas on how best to express such a shift in access patterns. The patch attached defines the following options:

random_drift none, meaning the current behavior (static)
sudden, meaning a sudden shift in the hot data gradual, meaning a gradual shift in the hot data

random_drift_start_percentage 0..100%. For example, if set to 50%, the
hot/cold distribution would remain static until 50% of data has been accessed.

random_drift_percentage 0..100% For example, if set to 10%, the
hot/cold distribution would shift 10% of the total size for every 10% of the workload accessed.

I'm thinking that random_drift_percentage should be split in two, so that we could say "shift X percent every time Y percent of the data has been accessed". But apart from that, any input on this? I'm open to suggestions on how to improve this, I think it's a feature that people evaluating caching solutions would be interested in in using.

An example job file would contain:

random_distribution=zipf
random_drift=gradual
random_drift_start_percentage=50
random_drift_percentage=10

Jens Axboe

index f7a1eae14408..93f9ee737bcf 100644
@@ -95,6 +95,8 @@ struct fio_file {
 	uint64_t first_write;
 	uint64_t last_write;
 
+	uint64_t io_done;
+
 	/*
 	 * For use by the io engine
 	 */

@@ -120,6 +122,8 @@ struct fio_file {
 	 * Used for zipf random distribution
 	 */
 	struct zipf_state zipf;
+	uint64_t drift_offset;
+	unsigned int last_drift_perc;
 
 	int references;
 	enum fio_file_flags flags;

index be2f23aa9f76..b017d2e5926b 100644
@@ -642,6 +642,12 @@ enum {
 	FIO_RAND_DIST_PARETO,
 };
 
+enum {
+	FIO_RAND_DRIFT_NONE	= 0,
+	FIO_RAND_DRIFT_GRADUAL,
+	FIO_RAND_DRIFT_SUDDEN,
+};
+
 #define FIO_DEF_ZIPF		1.1
 #define FIO_DEF_PARETO		0.2
 

index c691bc51a5a5..1bfbcee2a549 100644
@@ -50,11 +50,12 @@ void zipf_init(struct zipf_state *zs, unsigned long nranges, double theta,
 	zipf_update(zs);
 }
 
-unsigned long long zipf_next(struct zipf_state *zs)
+unsigned long long zipf_next(struct zipf_state *zs, uint64_t offset)
 {
 	double alpha, eta, rand_uni, rand_z;
 	unsigned long long n = zs->nranges;
 	unsigned long long val;
+	uint64_t off = zs->rand_off + offset;
 
 	alpha = 1.0 / (1.0 - zs->theta);
 	eta = (1.0 - pow(2.0 / n, 1.0 - zs->theta)) / (1.0 - zs->zeta2 / zs->zetan);

@@ -69,7 +70,7 @@ unsigned long long zipf_next(struct zipf_state *zs)
 	else
 		val = 1 + (unsigned long long)(n * pow(eta*rand_uni - eta + 1.0, alpha));
 
-	return (__hash_u64(val - 1) + zs->rand_off) % zs->nranges;
+	return (__hash_u64(val - 1) + off) % zs->nranges;
 }
 
 void pareto_init(struct zipf_state *zs, unsigned long nranges, double h,

@@ -79,10 +80,11 @@ void pareto_init(struct zipf_state *zs, unsigned long nranges, double h,
 	zs->pareto_pow = log(h) / log(1.0 - h);
 }
 
-unsigned long long pareto_next(struct zipf_state *zs)
+unsigned long long pareto_next(struct zipf_state *zs, uint64_t offset)
 {
 	double rand = (double) __rand(&zs->rand) / (double) FRAND_MAX;
 	unsigned long long n = zs->nranges - 1;
+	uint64_t off = zs->rand_off + offset;
 
-	return (__hash_u64(n * pow(rand, zs->pareto_pow)) + zs->rand_off) % zs->nranges;
+	return (__hash_u64(n * pow(rand, zs->pareto_pow)) + off) % zs->nranges;
 }

index f98ad8182883..43edcc5e78d2 100644
@@ -15,9 +15,9 @@ struct zipf_state {
 };
 
 void zipf_init(struct zipf_state *zs, unsigned long nranges, double theta, unsigned int seed);
-unsigned long long zipf_next(struct zipf_state *zs);
+unsigned long long zipf_next(struct zipf_state *zs, uint64_t off);
 
 void pareto_init(struct zipf_state *zs, unsigned long nranges, double h, unsigned int seed);
-unsigned long long pareto_next(struct zipf_state *zs);
+unsigned long long pareto_next(struct zipf_state *zs, uint64_t off);
 
 #endif

index c5f098c4c606..273fc62f5fbc 100644
@@ -209,9 +209,9 @@ int main(int argc, char *argv[])
 		struct node *n;
 
 		if (dist_type == TYPE_ZIPF)
-			offset = zipf_next(&zs);
+			offset = zipf_next(&zs, 0);
 		else
-			offset = pareto_next(&zs);
+			offset = pareto_next(&zs, 0);
 
 		n = hash_lookup(offset);
 		if (n)

index 611f8e7376fa..6f5451428051 100644
@@ -127,6 +127,10 @@ struct thread_options {
 
 	unsigned int random_distribution;
 
+	unsigned int random_drift;
+	unsigned int drift_start_perc;
+	unsigned int drift_perc;
+
 	fio_fp64_t zipf_theta;
 	fio_fp64_t pareto_h;
 

@@ -353,7 +357,11 @@ struct thread_options_pack {
 	uint32_t bs_is_seq_rand;
 
 	uint32_t random_distribution;
-	uint32_t pad;
+
+	uint32_t random_drift;
+	uint32_t drift_start_perc;
+	uint32_t drift_perc;
+
 	fio_fp64_t zipf_theta;
 	fio_fp64_t pareto_h;
 

@@ -426,7 +434,7 @@ struct thread_options_pack {
 	uint64_t trim_backlog;
 	uint32_t clat_percentiles;
 	uint32_t percentile_precision;
-	uint32_t pad2;
+	uint32_t pad;
 	fio_fp64_t percentile_list[FIO_IO_U_LIST_MAX_LEN];
 
 	uint8_t read_iolog_file[FIO_TOP_STR_MAX];

@@ -482,7 +490,7 @@ struct thread_options_pack {
 
 	uint64_t latency_target;
 	uint64_t latency_window;
-	uint32_t pad3;
+	uint32_t pad2;
 	fio_fp64_t latency_percentile;
 } __attribute__((packed));
 

This is fantastic Jens! We use zipf for testing our cache tiering implementation in Ceph. I suspect that you are absolutely right that a slowly shifting distribution would be more accurate (and probably slower for us sadly). I don't think I really have anything to add as it seems like you've got the things I'd want covered. Good Job!

Thanks,
Mark

Jens,

This is an interesting proposal. Just to make sure if I understand your example correctly, in this example you are proposing Gradual shift in hot/cold Blocks after 50% of workload is generated. This shift then would be 10% total distribution for every 10% of remaining workload access. It that correct ?

If I understand this correctly, the workload randomness distribution would change after drift. For example if I start with zipf:1.2 initially, I would have different distribution after the drift which is hard to describe. Would it be still Zipf with what theta parameter ?

Having said that, It would be more interesting and practical if we can set specific distribution parameter for the drifted workload phases. For example, Would be nice to divide the workload into 4 phases, phase 1: workload start with zipf:1.2, phase 2: workload drift to zipf:1.4, phase 3: workload drift to pareto, phase 4:workload drift to uniform distribution.

With this approach, we have more control on the workload randomness distribution parameters for each gradual drift. Moreover, it would be more practical to characterize a real workload and extract distribution parameters for these phases and then feed them to fio for synthetic re-generation of such a workload.

Hope it helps.
--
Alireza

That is correct.

After the drift, the zipf distribution would still be 1.2, it would just be a different set of blocks in the bands. The way it's implemented, it basically just shifts the logical offset in the drift. An example - lets say we have set the zipf to have the following distribution, using a small range for ease of representation:

0..4 95% of hits
5..9 5% of hits
10..14 2%
15..19 1%
20..24 1%
25..29 0.5%

We'll use the drift parameters from above, so once we've done 50% of the workload, we'll drift 10%. Since N is 30 here, that's a drift of 3. When that 10% drift is done, the distribution will look like this:

27..29 and 0..1 95% of hits
2..6 5% of hits
7..11 2%
12..16 1%
17..21 1%
22..26 0.5%

In other words, the distribution is identical, it's just a different set of blocks in the range. Fio hashes the linear blocks, so it won't be 0 as the hottest, 1 as the next hottest, etc. That's just for simplicity in this example.

If you graph the distribution from 0..N, after the shift, the graph would look the same. It would just be offset to the right, with the long tail wrapped around.

I would not be adverse to drifting the zipf or pareto values, but I think it's orthogonal to this issue. You could imagine workloads where that is all you drift, or workloads where you both drift the LBA space and the zipf theta, for instance. Drifting between different distribution types (from zipf to pareto, or from pareto to uniform) is likely never going to be implemented, however.

Definitely, the better you understand the workload, the better you can model. The above description is a linear (or sudden) drift of hotness, and an easy implementation of zipf theta drift would also be linear. Since we do have support for evaluating math, it would not be impossible to support having a functional description of the drift. But I think we should just keep it simple and support linear shifts.

Jens Axboe

Thanks for describing the idea in the second example. I get a sense of what you proposing now. I am just now sure about the application of such a workload. From the caching point of view, it does not really matter which LBA ranges are in 95% hit range. Specially these days that caches are all fully associative and based on key-value store. That is my impression that might be wrong. I think am not convinced that 95% hit on 0-4 LBA range would have different caching behavior compared with 27-29 and 0-1 range.

I agree with you that this LBA drift does not change zipf distribution. But only if we look at certain portion of the workload. For example, in the first portion of workload, it was a zipf:1.2 and 95% hit on 0-4 range, in the second phase it is still zipf:1.2 with 95% hit on the other range. Therefore, if we look at the workload as a whole not just a portion of the workload, it would be a zipf that receive less than 95% hit on the 0-4 range because the hot range has been drifted in the second portion of the workload. Therefore, the workload as a whole does not maintain the original zipf:1.2 distribution since original 95% hit on 0-4 range has been distributed to other LBA ranges.

Would it be possible to define 4 workers and associate each one to a certain distribution then execute them in a sequence ? For example, worker 1 with zipf:1.2 start from beginning to 25% of workload, worker 2 with zipf:1.4 start from the 25% to 50% of workload time, worker 3 with pareto start from 50% to 75% of the workload time and finally worker 4 with uniform distribution start from 75% to the end of workload time.

My point is that for caching workload, change in hot LBA range is less important that change in distribution of requests to hot LBAs. For example, a VDI workload expose a great temporal locality in the morning during boot storm, then its temporal locality would reduce since all virtual desktops are running with different applications during normal business hours. Finally the temporal locality would reduce to zero or uniform distribution over the night since most of the clients are turned off or hybernated.

Lets take a classic example of having some slow big storage, with 5% of that capacity fronted by a much faster device. For that to be effective, you would assume that almost all the hot data access hits the faster caching device. If we drift the values that are accessed often, then we exercise the ability of the cache to adapt to the new working set.

Yes, that is definitely true. Lets say we use the same 10% drift for each time period, t. And lets say we have drifted 10 times, through periods t1..t10. Graphing the access pattern for the entire period of t1..t10 would yield a flat equal distribution, and that surely isn't zipf:1.2. That is unavoidable with a drift like that. The point is that the distribution for the time period t1 would be zipf:1.2, and the distribution for t2 would also be zipf:1.2, they would just not be the same sets of data. The distribution of data only makes sense within the defined period of time, and that is also true of the performance seen. You can't drift too quickly, or they would be no point in doing so, you might as well just do uniformly random IO at that point.

Sure, you could do that right now, just define the 4 jobs with the desired settings, and have them execute serially by placing a stonewall between them.

I don't think that is generally true. It's true for some types of caching workloads, like the VDI you describe below. If you're caching for a database workload, with the database holding store items or similar, a drift would more closely match. It's not quite perfect, but I'm not aiming for perfection here or we'd never get done. The drift expires everything in the hot end of the spectrum. For natural workloads, I would expect a decay of some of the hotter items, but some of them would likely persist over much longer intervals.

A workload like that isn't really something you'd model with a drift. That's essentially three separate phases of the workload. Phase 1, boot storm, could be described with a zipf/pareto distribution, fairly closely. Phase 2 is probably more uniformly random, data set is a lot larger, though some locality would still be expected (I bet they all run Office, for instance, but they save/open different files). So perhaps phase 2 would work as zipf/pareto as well, just with a different input value. Phase 3 is basically idle, systems are off outside of the few sad souls burning the midnight oil.

Jens Axboe

There are two dimensions of locality: spatial and temporal.

random_distribution= provides some spatial locality control. The zipf distribution is not as "bursty" as many application workloads.

There is no direct temporal locality control. rate= sets a maximum rate, which essentially inserts some idle time (but the same for the entire job).

A 2002 paper by Mengzhi Wang, et al. at CMU discussed the importance of spatio-temporal correlation, at least in a storage trace provided by HP Labs. They found "the intuition that requests arriving closely in time tend to access nearby objects" held true and proposed a model that incorporated that concept called PQRS.

2002 slides: http://www-cgi.cs.cmu.edu/~mzwang/research/pub/pqrs_slides.pdf
2002 paper: http://pdl.cmu.edu/PDL-FTP/Workload/performance02.pdf
2005 analysis slides: http://www.research.ibm.com/haifa/Workshops/systems-and-storage2005/papers/eitan_bachmat_pqrs.pdf
2005 analysis paper: http://www.cs.bgu.ac.il/~ebachmat/pqrs-14-4-2012.pdf

The new random_drift feature changes spatial locality over time (where time means % of data that has been accessed), so it provides some correlation control, but doesn't provide full temporal locality control.

Maybe it'd be worth trying to implement the PQRS model and see if that works well for both dimensions?

If running on huge devices with time_based=1, it can take a long time to reach a meaningful % of the total size. % of time might be better.

---
Rob Elliott HP Server Storage

Just to clarify, the temporal locality control that you are referring to is more like burst control. You are not interested in a fixed IO generation rate and interested to have dynamic IO rate changes. Is that correct ?

Yes. That kind of temporal locality is necessary for write buffer/caches that sit between a fast interface and a slow interface, where the buffer is continuously destaged. Assuming the long-term input rate matches the output/destage rate (otherwise the buffer will inevitably become full), the required buffer size to maintain maximum bandwidth depends on the length of the bursts between the idles.

A simple fixed rate generator has uses too, but it often leads to overloading the system or settling at less than the maximum possible rate. That's how the SPC-1 benchmarks are designed; find the heaviest workload for which the system maintains the targeted latency (fio's latency_target= option).

Great start to me, with a lot of use cases out-of-the-box. A concern, probably a minor one, is that drift is global and applies to all data directions and threads, while one might be interested to model read/write or per thread behavior differently in this regard.

Further down the line, I'd give a thought to turning the base of the distribution in use into a (say, uniform) random variable. start_percentage and percentage then become the moments of the distribution that models the base offset evolution in time (expressed in either units of time or data volume accessed). An obvious use case is modelling multiple clients with zipf distribution, with each zipf's base independently evolving in a random fashion (a realistic model of a file server load with multiple clients, each with a randomly moving hotspot).

Regards,
Andrey