Description of problem: lvm2 code has now O(n)^2 complexity when dealing with lvm2 metadata. This has been introduced with commit: 687029cbbd5b97d545363b4f7448b5a1fe71f3c5 With this patch operations with dm_config_tree are significantly slowed down since each operation now searched for duplicate entries through the whole list of dm_config_nodes. This patch was introduced in version 2.02.113 Version-Release number of selected component (if applicable): 2.02.165 How reproducible: Steps to Reproduce: 1. create large metadata 2. run i.e. lvs command 3. double metadata size 4. compare time of lvs command - in correct version this should scale linearly Actual results: O(n)^2 complexity Expected results: O(n) complexity Additional info:
These patches avoid checking for duplicate config nodes in metadata config trees (which causes the complexity as mentioned in comment #0). When constructing metadata config trees, duplicate nodes are already avoided by direct metadata validation before such metadata are written to disk. The patches: https://git.fedorahosted.org/cgit/lvm2.git/commit/?id=7563e69cf13126af5889de147c092b9d2e490648 https://git.fedorahosted.org/cgit/lvm2.git/commit/?id=e40fbd08c8e3da43d07aabe58bd5549105056908 https://git.fedorahosted.org/cgit/lvm2.git/commit/?id=045772aa30ba1c5ab9dff730ce25ca6346c7150a https://git.fedorahosted.org/cgit/lvm2.git/commit/?id=f1cad4c7103ac0edc0b724217b50d062326deb43
Scheduled for lvm2 v2.02.166 upstream release.
Some performance numbers take on T61 2.2GHz CPU 4G RAM: with kernel: 4.7.2-201.fc24.x86_64 (These are for 'stable set of metadata LV' I keep for performance testing - and were used whenever I'm doing some regression testings: PV sits on loop device on tmpfs backend file (so no disk I/O latencies) Plan 'time lvs' on VG with: ----- 1700LV ----- non-lvmetad: 0.6s lvmetad: 0.3s (0.8s with initial scan) fixed_non-lvmetad: 0.4s fixed_lvmetad: 0.2s (0.5s with initial scan) ----- 7200LV ----- non-lvmetad: 5.0s lvmetad: 2.7s (7.6s with inital scan) (CPU time consumed by lvmetad by 2 'lvs' queries: 1.3s) fixed_non-lvmetad: 1.0s fixed_lvmetad: 0.7s (1.5s with initial scan) (CPU time consumed by lvmetad by 2 'lvs' queries: 0.4s) As one can immediately observe - patches from comment 1 do have major impact and already improve things a lot. Other note to take - we still do have some other 'minor' regressions even with 'fixed' version as timings for 'lvmetad' case are 'too good' compared with non-lvmetad case. However these needs more clever structures to be used - so outside of 7.3 range.