multithreading: input file discovery / reading parallelism

[ThomasWaldmann]

talked with @fd0 at 34c3 about MT and he mentioned that the sweet spot for input file discovery / reading parallelism seems to be 2 (for hard disks, hdd based RAID) when doing a backup.

1 is too little to use all the available resources / capability of the hw.
more than 2 is too much and overloads the hw (random HDD seeks in this case).

[fschulze]

For an SSD this can be quite different, it would be great if one can adjust the number of threads for that case. Currently it takes an hour to scan my whole disk with a transfer size of less the 500MB. So for now I'll use borgbackup as a less frequent addition to TimeMachine (which I don't fully trust, I've seen files missing on spot checks).

It would also be great to know what parts take time, whether the scanning, matching, crypto, transfer or whatever.

[fd0]

I made several tests on very different hardware (with the help of a bunch of people), and it mostly did not help reading more than 2 files in parallel on SSD an/or RAID. But in order to do this in a more scientific way (I did not save the program and the data) I'd like to re-run these tests and graph the results.

Would you like to help with that and/or participate?

[fschulze]

@fd0 I can certainly provide measurements from my end if I don't have to setup too much. I'm totally fine installing a development borg version on my laptop, but would like to avoid doing anything on the storage side.

[fd0]

Yeah, I plan to do that in Go (concurrency is very easy), so the test binary is just a statically linked binary that you can build locally and then copy to the test machine and run it there (even cross-compilation is very easy).

[fd0]

I've build a small program we can use for measurements here: https://github.com/fd0/prb

It traverses the given directory in one thread, and reads all files in a specified number of worker threads. For example, my benchmarks for a directory on the internal SSD of my laptop gives me:

workers	files	dirs	bytes	time (seconds)	bandwidth (per second)
1	326863	78365	25034388499	152.982354574	163642327
2	326863	78365	25034389119	108.725610135	230252919
3	326863	78365	25034389494	93.519914623	267690465
4	326863	78365	25034389948	89.576514578	279474927
5	326863	78365	25034390236	89.055505093	281109968
6	326863	78365	25034390629	88.652750661	282387071
7	326863	78365	25034390913	88.978444428	281353434
8	326863	78365	25034391508	88.363886038	283310214
9	326863	78365	25034396005	89.240226907	280528152
10	326863	78365	25034396341	88.483356924	282927741

(Still running for the internal hard drive...)

[jkahrs]

On the internal NVMe: (MacOS 10.12)

Helper script:

TARGET=$HOME
for i in 1 2 3 4 5 6 7 8 9 10; do  
	sync && sudo purge
	bin/prb --workers $i --output /tmp/benchmarks.csv "$TARGET"
done

Results:

workers	files	dirs	bytes	time (seconds)	bandwidth (per second). 
1	134597	22829	33534469011	43.31894966	774129319. 
2	134597	22829	33534390461	26.958458113	1243928355   
3	134597	22829	33534441292	22.807006458	1470356986  
4	134597	22829	33534441365	20.826685577	1610166977  
5	134597	22829	33534295113	20.906010019	1604050465  
6	134597	22829	33534344292	21.007518011	1596302060  
7	134597	22829	33534391668	20.661027471	1623074734  
8	134597	22829	33534399908	20.66181482	1623013283  
9	134597	22829	33534453044	21.010812681	1596056923  
10	134597	22829	33534521348	20.446736352	1640091639  

[fd0]

Next data point: My internal hard disc:

workers	files	dirs	bytes	time (seconds)	bandwidth (per second)
1	11559	268	55096088012	852.778747346	64607717
2	11559	268	55096088012	974.067868801	56562884
3	11559	268	55096088012	1010.936685754	54500038
4	11559	268	55096088012	1057.294799461	52110431
5	11559	268	55096088012	1075.07961856	51248379
6	11559	268	55096088012	1110.684131519	49605541
7	11559	268	55096088012	1159.329260498	47524107
8	11559	268	55096088012	1180.693423095	46664177
9	11559	268	55096088012	1215.789427597	45317130
10	11559	268	55096088012	1252.950178241	43973087

[fd0]

Another machine, reading data from an SSD via SATA:

workers	files	dirs	bytes	time (seconds)	bandwidth (per second)
1	88389	25083	14306522715	52.196173041	274091410
2	88389	25083	14306522715	35.386510019	404293124
3	88389	25083	14306522715	31.67159325	451714651
4	88389	25083	14306522715	31.08763338	460199801
5	88389	25083	14306522715	31.059477186	460616984
6	88389	25083	14306522715	31.167345965	459022809
7	88389	25083	14306522715	31.012411926	461316028
8	88389	25083	14306522715	30.927243427	462586416
9	88389	25083	14306522715	30.926412386	462598847
10	88389	25083	14306522715	31.153801543	459222374

[jkahrs]

Same system, connected via USB3:

5400 rpm HDD

workers	files	dirs	bytes	time (seconds)	bandwidth (per second)
1	44370	12234	2557745423	64.929517906	39392644
2	44370	12234	2557745423	45.042011148	56785773
3	44370	12234	2557745423	47.941166942	53351755
4	44370	12234	2557745423	51.798936151	49378338
5	44370	12234	2557745423	54.807403461	46667881
6	44370	12234	2557745423	57.106539	44789011
7	44370	12234	2557745423	58.573511115	43667271
8	44370	12234	2557745423	60.245337734	42455491
9	44370	12234	2557745423	62.257068435	41083614
10	44370	12234	2557745423	64.328836775	39760479

SSD

workers	files	dirs	bytes	time (seconds)	bandwidth (per second)
1	12448	7383	44389369458	111.594261105	397774661
2	12448	7383	44389369458	104.685872615	424024449
3	12448	7383	44389369458	104.894013065	423183060
4	12448	7383	44389369458	104.908220452	423125749
5	12448	7383	44389369458	104.540388212	424614545
6	12448	7383	44389369458	104.80080464	423559433
7	12448	7383	44389369458	105.194333052	421974912
8	12448	7383	44389369458	104.782470494	423633545
9	12448	7383	44389369458	105.063509001	422500351
10	12448	7383	44389369458	105.366123482	421286918

[ThomasWaldmann]

Guess the only things missing still are some RAID systems with many HDDs or SSDs.

[fschulze]

NVMe in a late 2016 15" MacBook Pro (4 cores with Hyperthreading):

workers	files	dirs	bytes	time (seconds)	bandwidth (per second)
1	4243314	756425	301394839765	1018.361214516	295960642
2	4243380	756425	301396556781	684.329069022	440426353
3	4243440	756426	301397998843	558.604872262	539554905
4	4243475	756426	301399037339	523.684396133	575535646
5	4243519	756426	301400593097	509.297344263	591796907
6	4243566	756427	301401846249	522.760056444	576558676
7	4244200	756429	301429018785	530.952168634	567714074
8	4244429	756429	301437311356	529.609069741	569169465
9	4244469	756429	301438821859	509.666049886	591443793
10	4244508	756429	301440390469	510.457233737	590530157

@jkahrs what machine do you have? Your NVMe speed is impressive

Now this all got me thinking. Is borg actually reading all the files for every backup? I thought it's more like rsync which only reads the files if the stats changed.

If it actually is only reading files when the stats change, then the directory traversal is the bottleneck. As you can see just my home directory has more than 4 million files.

If traversal is the bottleneck, does borg already use https://pypi.python.org/pypi/scandir? Making traversal multithreaded is most likely harder, but could speed things up a lot. What about xattr and resource forks, I guess because scandir doesn't include them, that could be multithreaded more easily.

If borg actually reads files for all backups, then an option to work like rsync would be very useful for me. I have backups for servers where I know that files don't change without stat changes and they have hdds where not reading stuff would help a lot.

[ThomasWaldmann]

NVME SSD in my workstation (with few big VM files)

workers files   dirs    bytes   time (seconds)  bandwidth (per second)
1       29      14      60873793654     22.810396927    2668686294    # 2.67GB/s
2       29      14      60873793654     28.385084934    2144569720
3       29      14      60873793654     34.139300982    1783100177
4       29      14      60873793654     33.857192252    1797957527
5       29      14      60873793654     33.319131428    1826992212
6       29      14      60873793654     33.566628508    1813521237
7       29      14      60873793654     33.624335908    1810408800
8       29      14      60873793654     33.641778505    1809470139
9       29      14      60873793654     33.238669888    1831414850
10      29      14      60873793654     33.186091691    1834316442

Looks like reading big files gets worse with more workers.

[ThomasWaldmann]

Same, but with more and smaller/medium files.

workers files   dirs    bytes   time (seconds)  bandwidth (per second)
1       268881  35541   59742969794     40.711983296    1467454173  # 1.47 GB/s
2       268881  35541   59742969794     40.119823345    1489113480
3       268881  35541   59742969794     41.636482683    1434870717
4       268881  35541   59742969794     40.749647873    1466097817
5       268881  35541   59742969794     39.5652761      1509984908
6       268881  35541   59742969794     39.127989676    1526860191
7       268881  35541   59742969794     38.880705822    1536571122
8       268881  35541   59742969794     38.749396771    1541778060
9       268881  35541   59742969794     38.660238397    1545333714
10      268881  35541   59742969794     38.665501079    1545123382

[ThomasWaldmann]

@fschulze borg does not open unchanged files. but it fetches stats, xattrs, acls, bsdflags.

[jkahrs]

@fschulze this is the late 2016 13" model. I had the feeling that after downgrading back to Sierra with encrypted HFS+ the I/O went way up.

Software RAID5 HDD (8 Disks) (ext4):

workers	files	dirs	bytes	time (seconds)	bandwidth (per second)
1	225393	44283	16670948275	207.924925535	80177728
2	225393	44283	16670948275	152.340443245	109432189
3	225393	44283	16670948275	133.244525906	125115445
4	225393	44283	16670948275	122.852574096	135698811
5	225393	44283	16670948275	117.991702629	141289157
6	225393	44283	16670948275	131.906811125	126384287
7	225393	44283	16670948275	111.734195296	149201846
8	225393	44283	16670948275	112.290326643	148462906
9	225393	44283	16670948275	108.54295232	153588491
10	225393	44283	16670948275	106.306041287	156820328