[pacman-dev] Tar backend for local db
I was thinking about the local database backend in pacman and how we could improve it. The tar-based backed for sync dbs have been quite a success. Ever since we did that, I have been wanting to do the same with the local database. But there were two issues: 1) tar is not designed for removing and updating files in place 2) with a directory/files per package structure, we are quite robust to corruption as a single file effects only a single package. Well... I have a cunning plan... How about we do both! Have the local database in a tarball but also extracted. All reading is done from the tarball, so -Q operations would be fast due to not require reading from lots of small files. With an operation that adds/removes/updates a package, the local database is still read from the tarball, but the modifications are done on the files backend and then the tarball is recreated at the end. We could even be efficient during the recreation and read all the old files from the old tarball and only read the new files from the filesystem (which will be in the kernel cache...). This would also give another use for "pacman -D" - an option could be added to recreate the local db tarball - in case it became corrupt or the files were manually edited. What do people think?
On Thu, Nov 1, 2012 at 6:12 AM, Allan McRae <allan@archlinux.org> wrote:
Well... I have a cunning plan... How about we do both!
Have the local database in a tarball but also extracted. All reading is done from the tarball, so -Q operations would be fast due to not require reading from lots of small files.
If you use a separate database for faster access anyway, why not use a real fast format like sqlite or such alike? It could be a fragile format since the db would be regenerated after each access. I personally see not much gain in this, it'd be a few milliseconds you save on the cost of making a simple task unnecessary complex (I am follower of the KISS principle :-).
On 01/11/12 15:25, Klaus-J. Wolf wrote:
On Thu, Nov 1, 2012 at 6:12 AM, Allan McRae <allan@archlinux.org> wrote:
Well... I have a cunning plan... How about we do both!
Have the local database in a tarball but also extracted. All reading is done from the tarball, so -Q operations would be fast due to not require reading from lots of small files.
If you use a separate database for faster access anyway, why not use a real fast format like sqlite or such alike? It could be a fragile format since the db would be regenerated after each access.
Because we already have all the code to read from tarballs - that is how the sync dbs are handled.
I personally see not much gain in this, it'd be a few milliseconds you save on the cost of making a simple task unnecessary complex (I am follower of the KISS principle :-).
# echo 3 > /proc/sys/vm/drop_caches # time pacman -Qi pacman-git ... real 0m13.242s
From experience with the tar backend for sync databases, this would decrease by at least 10 seconds.
Allan
Hi, I would recommend sqlite. It is really fast (faster than mysql and postgresql, when we're not talking about huge datasets), and just a small dependency to add. It's also used by several other projects, so it's likely that it would be installed as a dependency on a system sooner or later. My previous workplace used tar as a sort of database format for geological files, and tar files only worked okay, not great. When making a program read tar files directly from within a program, instead of extracting it first with the tar utility, it's cumbersome, and not KISS. Sqlite is well tested, and used for several projects (for instance firefox, not that firefox is a good example of speedy execution times). Also, one could argue that sqlite is a better fit for pacman, since it's like it was made to do this job, rather than tar, a tool that was originally made for making backups to tapes. I agree with Klaus-J. Wolf here, and am convinced that you would decrease the time it takes more by sqlite than with tar. Just my 4 nibbles. -- Best regards, Alexander Rødseth xyproto / trontonic / TU
Am 01.11.2012 10:41, schrieb Alexander Rødseth:
I would recommend sqlite. It is really fast (faster than mysql and postgresql, when we're not talking about huge datasets), and just a small dependency to add. It's also used by several other projects, so it's likely that it would be installed as a dependency on a system sooner or later.
While this sounds nice, there is one problem: There would be two distinct backends: One for local DBs, once for sync DBs. It's a situation that we may not want - and switching sync databases to sqlite is unlikely to happen.
On 01/11/12 19:41, Alexander Rødseth wrote:
Hi,
I would recommend sqlite. It is really fast (faster than mysql and postgresql, when we're not talking about huge datasets), and just a small dependency to add. It's also used by several other projects, so it's likely that it would be installed as a dependency on a system sooner or later. My previous workplace used tar as a sort of database format for geological files, and tar files only worked okay, not great. When making a program read tar files directly from within a program, instead of extracting it first with the tar utility, it's cumbersome, and not KISS. Sqlite is well tested, and used for several projects (for instance firefox, not that firefox is a good example of speedy execution times). Also, one could argue that sqlite is a better fit for pacman, since it's like it was made to do this job, rather than tar, a tool that was originally made for making backups to tapes.
The thing you are missing is EVERYTHING in pacman apart from the local db is in tar format. The packages are tarballs, the sync dbs are tarballs. We use a very good library for reading from tarballs without extracting them.
I agree with Klaus-J. Wolf here, and am convinced that you would decrease the time it takes more by sqlite than with tar.
From memory, when we implemented reading the sync db from the tarball, the actually time required to read it was measured as a fraction of a second. It is all the other stuff that takes the time. I have never been convinced that adding the extra dependency is worth the minor savings.
Allan
Allan McRae wrote:
This would also give another use for "pacman -D" - an option could be added to recreate the local db tarball - in case it became corrupt or the files were manually edited.
That would be an essential function as manual edits are quite common.
The thing you are missing is EVERYTHING in pacman apart from the local db is in tar format. The packages are tarballs, the sync dbs are tarballs. We use a very good library for reading from tarballs without extracting them.
"We have a really shiny hammer and and a lot of nails, so we may as well just use our shiny hammer on everything." It makes sense that packages are tar archives. A package is a fixed set of files arranged in a hierarchy. That's what tar was meant to store. Databases on the other hand are different. You can argue it any which way you want, but it's obvious that the multiple files/tarred archive approach was a lazy shortcut to avoid a proper solution that would have required time to implement, test and debug. At first Judd or whoever presumably just wanted to get it working, and subsequent improvements were made on what was already there. Now it's grandfathered in with all the emotional attachment and a proud member of the "good enough" club, but that does not mean that it's optimal. SQLite makes sense for both sync and local databases. I expect it would be faster and more versatile. The data would be stored in a common data format and not require custom files and parsers. It would facilitate the creation of third-party tools. Is this a big deal? No. As stated, the current solution is already "good enough". Further improvements will be welcomed, but there must come a point where you ask yourself if complicating an existing suboptimal solution to shave off a few seconds is really better than implementing a proper solution to the problem. Eventually you will want a proper solution, and then the current effort will be at least partially wasted. All that aside, +1 for tarring the local db to improve speed, as long as the local files remain easily accessible for manual editing. Regards, Xyne
On 01.11.2012 20:11, Xyne wrote:
SQLite makes sense for both sync and local databases. I expect it would be faster and more versatile. The data would be stored in a common data format and not require custom files and parsers. It would facilitate the creation of third-party tools.
Third-party tools *should* use libalpm.
All that aside, +1 for tarring the local db to improve speed, as long as the local files remain easily accessible for manual editing.
vim let's you open tar archives, change a file in there and then save the archive. -- Florian Pritz
On 11/1/12, Allan McRae <allan@archlinux.org> wrote:
# echo 3 > /proc/sys/vm/drop_caches # time pacman -Qi pacman-git ... real 0m13.242s
From experience with the tar backend for sync databases, this would decrease by at least 10 seconds.
From my experience writing non-libalpm pacman clients, you could reduce that by 13 seconds if you lazily loaded the local DB. There is no reason to walk and parse the data of hundreds of packages when the user is explicitly asking for one.
One minor quibble (we discussed this elsewhere but I just want to note it here), GNU tar can delete files from tarballs and add files to tarballs. This has three major problems. First, it only works on uncompressed tarballs. Second, the deleted space remains in use (pacman -D --vacuum will be needed). Third, it only works with magic in GNU tar and is seemingly not exposed by libarchive [1]. But I think there is serious potential here. Allan, I do like the general thrust of everything you are proposing. It does take an abysmally long time to load the local DB. But it seems silly to add what is essentially a union file system to pacman when there are simpler alternatives. -Kyle http://kmkeen.com [1] Delete/Append in GNU tar Sources at http://ftp.gnu.org/gnu/tar/tar-1.26.tar.gz Two files of interest: coverage tests (tests/testsuite line 10460) and src/delete.c. I do not understand how it works, but it does work and there you can find it. Some things to note. Deleting a file does not free up space and does not change the size of the tar file. But the file will no longer appear in --list or when extracted. Appending a file may or may not take up additional space. It appears from casual experimentation that GNU tar will reuse space if the appended file is small enough to fit inside a hole left by deletion.
On Thu, Nov 1, 2012 at 8:27 AM, keenerd <keenerd@gmail.com> wrote:
From my experience writing non-libalpm pacman clients, you could reduce that by 13 seconds if you lazily loaded the local DB. There is no reason to walk and parse the data of hundreds of packages when the user is explicitly asking for one.
Your non-libalpm clients must never need to compute reverse dependencies (e.g. requiredbys) then. There is quite a good reason we *have* to parse the rest when we show either info or need to compute dep chains during sync or upgrade operations. A simple `pacman -Q glibc` operation (to see if the package is installed locally) doesn't open more than a handful of files, and we don't even have to open the actual files in the local database- we only scan the directory. -Dan $ strace -e open,openat,getdents pacman -Q glibc open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libalpm.so.7", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libc.so.6", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libgpgme.so.11", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libarchive.so.12", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libcurl.so.4", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libcrypto.so.1.0.0", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libassuan.so.0", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libgpg-error.so.0", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libacl.so.1", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libattr.so.1", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libexpat.so.1", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/liblzma.so.5", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libbz2.so.1.0", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libz.so.1", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libssh2.so.1", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/librt.so.1", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libssl.so.1.0.0", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libpthread.so.0", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/libdl.so.2", O_RDONLY|O_CLOEXEC) = 3 open("/usr/lib/locale/locale-archive", O_RDONLY|O_CLOEXEC) = 3 open("/etc/pacman.conf", O_RDONLY) = 3 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 openat(AT_FDCWD, "/var/lib/pacman/local/", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC) = 3 getdents(3, /* 802 entries */, 32768) = 32752 getdents(3, /* 436 entries */, 32768) = 18464 getdents(3, /* 0 entries */, 32768) = 0 open("/etc/pacman.conf", O_RDONLY) = 3 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/usr/share/locale/locale.alias", O_RDONLY|O_CLOEXEC) = 4 open("/usr/share/locale/en_US.UTF-8/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory) open("/usr/share/locale/en_US.utf8/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory) open("/usr/share/locale/en_US/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory) open("/usr/share/locale/en.UTF-8/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory) open("/usr/share/locale/en.utf8/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory) open("/usr/share/locale/en/LC_MESSAGES/libc.mo", O_RDONLY) = -1 ENOENT (No such file or directory) open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 open("/etc/pacman.d/mirrorlist", O_RDONLY) = 4 openat(AT_FDCWD, "/var/lib/pacman/local/", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC) = 3 getdents(3, /* 802 entries */, 32768) = 32752 getdents(3, /* 436 entries */, 32768) = 18464 getdents(3, /* 0 entries */, 32768) = 0 glibc 2.16.0-5 +++ exited with 0 +++
On 01/11/12 23:27, keenerd wrote:
On 11/1/12, Allan McRae <allan@archlinux.org> wrote:
# echo 3 > /proc/sys/vm/drop_caches # time pacman -Qi pacman-git ... real 0m13.242s
From experience with the tar backend for sync databases, this would decrease by at least 10 seconds.
From my experience writing non-libalpm pacman clients, you could reduce that by 13 seconds if you lazily loaded the local DB. There is no reason to walk and parse the data of hundreds of packages when the user is explicitly asking for one.
Sure... if it was a -Ql operation it would be much faster. -Qi needs to read the desc file for all installed packages (for "Required by" calculation). Allan
On 01/11/12 15:12, Allan McRae wrote:
I was thinking about the local database backend in pacman and how we could improve it.
The tar-based backed for sync dbs have been quite a success. Ever since we did that, I have been wanting to do the same with the local database. But there were two issues:
1) tar is not designed for removing and updating files in place
2) with a directory/files per package structure, we are quite robust to corruption as a single file effects only a single package.
Well... I have a cunning plan... How about we do both!
Have the local database in a tarball but also extracted. All reading is done from the tarball, so -Q operations would be fast due to not require reading from lots of small files. With an operation that adds/removes/updates a package, the local database is still read from the tarball, but the modifications are done on the files backend and then the tarball is recreated at the end. We could even be efficient during the recreation and read all the old files from the old tarball and only read the new files from the filesystem (which will be in the kernel cache...).
This would also give another use for "pacman -D" - an option could be added to recreate the local db tarball - in case it became corrupt or the files were manually edited.
What do people think?
Just to be clear, I wanted comments on the dual local database (one "binary", one filesystem based) would be a good solution to increase read speed (due to not having many small files), but also keeping the robustness of the non-binary format to corruption. I.e would the extra 10-20MB be an acceptable trade-off. Given I have absolutely no interest in using sqlite, bdb, etc... and I can almost guarantee that I will be the one to provide a patchset that changes the local backend, comments about choosing a relational database are not needed. Allan
@Thomas, I see, thanks. @Allan, Very well, choose what you want, just wanted to comment on the use of tar vs sqlite on a general basis. - Alexander 2012/11/1 Allan McRae <allan@archlinux.org>:
On 01/11/12 15:12, Allan McRae wrote:
I was thinking about the local database backend in pacman and how we could improve it.
The tar-based backed for sync dbs have been quite a success. Ever since we did that, I have been wanting to do the same with the local database. But there were two issues:
1) tar is not designed for removing and updating files in place
2) with a directory/files per package structure, we are quite robust to corruption as a single file effects only a single package.
Well... I have a cunning plan... How about we do both!
Have the local database in a tarball but also extracted. All reading is done from the tarball, so -Q operations would be fast due to not require reading from lots of small files. With an operation that adds/removes/updates a package, the local database is still read from the tarball, but the modifications are done on the files backend and then the tarball is recreated at the end. We could even be efficient during the recreation and read all the old files from the old tarball and only read the new files from the filesystem (which will be in the kernel cache...).
This would also give another use for "pacman -D" - an option could be added to recreate the local db tarball - in case it became corrupt or the files were manually edited.
What do people think?
Just to be clear, I wanted comments on the dual local database (one "binary", one filesystem based) would be a good solution to increase read speed (due to not having many small files), but also keeping the robustness of the non-binary format to corruption. I.e would the extra 10-20MB be an acceptable trade-off.
Given I have absolutely no interest in using sqlite, bdb, etc... and I can almost guarantee that I will be the one to provide a patchset that changes the local backend, comments about choosing a relational database are not needed.
Allan
-- Best regards, Alexander Rødseth xyproto / trontonic / TU
participants (8)
-
Alexander Rødseth
-
Allan McRae
-
Dan McGee
-
Florian Pritz
-
keenerd
-
Klaus-J. Wolf
-
Thomas Bächler
-
Xyne