improve space utilization on off-sized raid devices

I wrote a small patch to improve allocation on differently sized raid d= evices.

With 2.6.38 I frequently ran into a no space left error that I attribut= e to
this. But I'm not entierly sure. The fs was an 8 device -d raid0 -m rai= d10.
The used space was the same across all devices. 5 were full and 3 bigge= r ones still had plenty of space.
I was unable to use the remaning space and a balance did not fix it for long.

Now I tried to avoid getting there again.

The basic idea to not allocate space on the devices with the least free space. The amount of devices to leave out is calculated on each allocat= ion
to ajust to changing circumstances. It leaves the minimum number that s= till
can achieve full space usage.

Additionally I tought leaving at least one out might be of use in devic= e removal.

Please take extra care with this. I'm new to btrfs, kernel and C in gen= eral.
It was written and tested with 3.0.0.

@@ -2329,6 +2329,8 @@ static int __btrfs_alloc_chunk(struct bt
        u64 stripe_size;
        u64 num_bytes;
        int ndevs;
+       u64 fs_total_avail;
+       int opt_ndevs;
        int i;
        int j;

=20
@@ -2404,6 +2406,7 @@ static int __btrfs_alloc_chunk(struct bt

         * about the available holes on each device.
         */
        ndevs =3D 0;
+       fs_total_avail =3D 0;
        while (cur !=3D &fs_devices->alloc_list) {
                struct btrfs_device *device;
                u64 max_avail;
@@ -2448,6 +2451,7 @@ static int __btrfs_alloc_chunk(struct bt
                devices_info[ndevs].total_avail =3D total_avail;
                devices_info[ndevs].dev =3D device;
                ++ndevs;
+               fs_total_avail +=3D total_avail;
        }
=20
        /*

@@ -2456,6 +2460,20 @@ static int __btrfs_alloc_chunk(struct bt
sort(devices_info, ndevs, sizeof(struct btrfs_device_info),
btrfs_cmp_device_info, NULL);
=20
+ /*

+        * do not allocate space on all devices
+        * instead balance free space to maximise space utilization
+        * (this needs tweaking if parity raid gets implemented
+        * for n parity ignore the n first (after sort) devs in the sum=

and division)
+ */
+ opt_ndevs =3D fs_total_avail / devices_info[0].total_avail;
+ if (opt_ndevs >=3D ndevs)
+ opt_ndevs =3D ndevs - 1; //optional, might be used for =
faster dev remove?
+ if (opt_ndevs < devs_min)
+ opt_ndevs =3D devs_min;
+ if (ndevs > opt_ndevs)
+ ndevs =3D opt_ndevs;
+

        /* round down to number of usable stripes */
        ndevs -=3D ndevs % devs_increment;

--=20
NEU: FreePhone - 0ct/min Handyspartarif mit Geld-zur=C3=BCck-Garantie! =
=09
Jetzt informieren: http://www.gmx.net/de/go/freephone
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" = in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Did you also test with 3.0? In 3.0, the allocation strategy changed vastly. In your setup, it should stripe to all 8 devices until the 5 smaller ones are full, and from then on stripe to the 3 remaining devices. See commit

commit 73c5de0051533cbdf2bb656586c3eb21a475aa7d

Author: Arne Jansen <[email protected]>
Date:   Tue Apr 12 12:07:57 2011 +0200

btrfs: quasi-round-robin for chunk allocation

Also using raid1 instead of raid10 will yield a better space utilization.

-Arne

-------- Original-Nachricht --------

No I did not test if the problem occoured in vanilla 3.0.0. I only did compare the code and saw no reason why behavior should have changed (for my case).
The sorting is the base of my idea. But the order does not matter if you allocate on all devices anyway (as with an even number of devs).

Afaik the behavior you describe is exactly the problem.
It wants to continuing with 3 devices, but according to the code raid10 requires 4.

I can't use the actual fs (or devs) the problem happened on but I will try a small scale test on some files. As I currently have my patch in use I will have to wait till I can reboot.

Empfehlen Sie GMX DSL Ihren Freunden und Bekannten und wir
belohnen Sie mit bis zu 50,- Euro! https://freundschaftswerbung.gmx.de

Right you are. So you want to sacrifice stripe size for space efficiency. Why don't you just use RAID1?
Instead of reducing the stripe size for the majority of writes, I'd prefer to allow RAID10 to go down to 2 disks. This should also solve it.

-------- Original-Nachricht --------

Yes, that's my trade.
With my patch I still have striping across 6 devices for meta (6-7 for data) which is faster then the 2 raid1 would give me. Since 6 drives allready saturate my bus it's a very good trade in my case.

While implementing your "degenerated raid0/10" would somewhat lessen the problem (and fix it for me), it would not fix it in general. But implementing it might is still be a good idea.

Consider a 4 dev setup: 3 1TB drives and 1 2TB using -m raid1 -d raid0: 80% capacity striped 4 way.
-d single: 100% but no striping.
My patch: 100% striped 3 way, a good trade imho.

I don't think such a setup is unlikely enough to ignore, a home user will simply buy the drive with the best space/cost whenever he needs space, leading exactly to the described situation. Adding a newly bought 2T drive to my 3x1T setup, only to see that only half of it can be used would really piss me off.

Note that if the (optional) first "if" is removed I only reduce width if it is required to reach 100% capacity. At least thats the intention, it might need some tweaking.
According to the (hackish) simulator I used to test this, typically the average stripe width sacrificed on setups of 5+ unmatched devices is below 2

Empfehlen Sie GMX DSL Ihren Freunden und Bekannten und wir
belohnen Sie mit bis zu 50,- Euro! https://freundschaftswerbung.gmx.de

Yes, it appears that btrfs's current idea of raid10 is actually raid0+1, not raid10. If it were proper raid10, it could use the remaining space on the 3 larger disks for a raid10 metadata chunk.

As RAID0 is already not a strict 'all disks or none', I like the idea to have it even more dynamic to reach full optimization. But I'd like to see some properties conserved:
a) In case of even size disks, the stripes should always be full size, not n - 1
b) Minor variations in the used space per disk due to metadata chunks should not lead to deviation from a)
c) The algorithms should not give weird results under unconventional setups. Some theoretical background would be nice :)

It might well be that your algorithm is already close :)

-Arne

Sorry to only get back to you now, I must have missed your mail somehow.

The problem is the shrinking stripe width with unmatched devices. Once it hits devs_min-1 it's over. My solution is to try to keep the stripe width constant. The sorting then takes care of selecting the right devices.

It's simply: space / min-hight = max-width
a) is dictated by math
Since circumstances change (add, rm devs, rounding, ...) it is calculated again at every allocation. The result is then rounded to the nearest multiple of devs_increment. This takes care of b).

The code may look wiered but should be identical to the mathematical
floor(Space / min-hight + increment/2) if considered together with the round down already present in the line after my patch.

The two ifs should safeguard against weird stuff by limiting the result to sane values.

I include an updated patch below. It's again written for and tested with 3.0.0 but diff3 worked nicely for applying it to 3.3-rc1.

@@ -2329,6 +2329,8 @@
 	u64 stripe_size;
 	u64 num_bytes;
 	int ndevs;
+	u64 fs_total_avail;
+	int opt_ndevs;
 	int i;
 	int j;
 

@@ -2448,6 +2450,7 @@
 		devices_info[ndevs].total_avail = total_avail;
 		devices_info[ndevs].dev = device;
 		++ndevs;
+		fs_total_avail += total_avail;
 	}
 
 	/*

@@ -2456,6 +2459,16 @@
 	sort(devices_info, ndevs, sizeof(struct btrfs_device_info),
 	     btrfs_cmp_device_info, NULL);
 
+	/*
+	* do not allocate space on all devices
+	* instead balance free space to maximise space utilization
+	*/
+	opt_ndevs = (fs_total_avail*2 + devs_increment*devices_info[0].total_avail) / (devices_info[0].total_avail*2);
+	if (opt_ndevs < devs_min)
+		opt_ndevs = devs_min;
+	if (ndevs > opt_ndevs)
+		ndevs = opt_ndevs;
+
 	/* round down to number of usable stripes */
 	ndevs -= ndevs % devs_increment;
 

to

see

e, not

s

Resent because it did not appear on the ML for about 4h. KMail's acting up.

Sorry to only get back to you now, I must have missed your mail somehow= =2E

The problem is the shrinking stripe width with unmatched devices. Once = it hits devs_min-1 it's over. My solution is to try to keep the stripe = width constant.
The sorting then takes care of selecting the right devices.

It's simply: space / min-hight =3D max-width
a) is dictated by math
Since circumstances change (add, rm devs, rounding, ...) it is calculat= ed again at every allocation. The result is then rounded to the nearest=
multiple of devs_increment. This takes care of b).

The code may look wiered but should be identical to the mathematical floor(Space / min-hight + increment/2) if considered together with the = round down already present in the line after my patch.

The two ifs should safeguard against weird stuff by limiting the result=
to sane values.

I include an updated patch below. It's again written for and tested wit= h 3.0.0 but diff3 worked nicely for applying it to 3.3-rc1.

@@ -2329,6 +2329,8 @@
        u64 stripe_size;
        u64 num_bytes;
        int ndevs;
+       u64 fs_total_avail;
+       int opt_ndevs;
        int i;
        int j;

=20
@@ -2448,6 +2450,7 @@

                devices_info[ndevs].total_avail =3D total_avail;
                devices_info[ndevs].dev =3D device;
                ++ndevs;
+               fs_total_avail +=3D total_avail;
        }
=20
        /*

@@ -2456,6 +2459,16 @@
sort(devices_info, ndevs, sizeof(struct btrfs_device_info),
btrfs_cmp_device_info, NULL);
=20

+       /*
+       * do not allocate space on all devices
+       * instead balance free space to maximise space utilization
+       */
+       opt_ndevs =3D (fs_total_avail*2 + devs_increment*devices_info[0=

].total_avail) / (devices_info[0].total_avail*2);
+ if (opt_ndevs < devs_min)
+ opt_ndevs =3D devs_min;
+ if (ndevs > opt_ndevs)
+ ndevs =3D opt_ndevs;
+

        /* round down to number of usable stripes */
        ndevs -=3D ndevs % devs_increment;

--=20
Ihr GMX Postfach immer dabei: die kostenlose GMX Mail App f=C3=BCr Andr= oid.
Komfortabel, sicher und schnell: www.gmx.de/android
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" = in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html