1LIBSOLV-HISTORY(3) LIBSOLV LIBSOLV-HISTORY(3)
2
6 libsolv-history - how the libsolv library came into existence
7
9 This project was started in May 2007 when the zypp folks decided to
10 switch to a database to speed up installation. As I am not a big fan of
11 databases, I (mls) wondered if there would be really some merit of
12 using one for solving, as package dependencies of all packages have to
13 be read in anyway.
14 Back in 2002, I researched that using a dictionary approach for storing
16 dependencies can reduce the packages file to 1/3 of its size. Extending
17 this idea a bit more, I decided to store all strings and relations as
18 unique 32-bit numbers. This has three big advantages:
19 • because of the unification, testing whether two strings are equal
21 is the same as testing the equality of two numbers, thus very fast
22 • much space is saved, as numbers do not take up as much space as
24 strings the internal memory representation does not take more space
25 on a 64-bit system where a pointer is twice the size of a 32-bit
26 number
27 Thus, the solv format was created, which stores a repository as a
29 string dictionary, a relation dictionary and then all packages
30 dependencies. Tests showed that reading and merging multiple solv
31 repositories takes just some milliseconds.
32 Early solver experiments
34 Having a new repository format was one big step, but the other area
35 where libzypp needed improvement was the solver. Libzypp’s solver was a
36 port from the Red Carpet solver, which was written to update packages
37 in an already installed system. Using it for the complete installation
38 progress brought it to its limits. Also, the added extensions like
39 support for weak dependencies and patches made it fragile and
40 unpredictable.
41 As I was not very pleased with the way the solver worked, I looked at
43 other solver algorithms. I checked smart, yum and apt, but could not
44 find a convincing algorithm. My own experiments also were not very
45 convincing, they worked fine for some problems but failed miserably for
46 other corner cases.
47 Using SAT for solving
49 SUSE’s hack week at the end of June 2007 turned out to be a turning
50 point for the solver. Googling for solver algorithms, I stumbled over
51 some note saying that some people are trying to use SAT algorithms to
52 improve solving on Debian. Looking at the SAT entry in Wikipedia, it
53 was easy to see that this indeed was the missing piece: SAT algorithms
54 are well researched and there are quite some open source
55 implementations. I decided to look at the minisat code, as it is one of
56 the fastest solvers while consisting of not too many lines of code.
57 Of course, directly using minisat would not work, as a package solver
59 does not need to find just one correct solution, but it also has to
60 optimize some metrics, i.e. keep as many packages installed as
61 possible. Thus, I needed to write my own solver, incorporating the
62 ideas and algorithms used in minisat. This wasn’t very hard, and at the
63 end of the hack week the solver calculated the first right solutions.
64 Selling it to libzypp
66 With those encouraging results, I went to Klaus Kaempf, the system
67 management architect at SUSE. We spoke about how to convince the team
68 to make libzypp switch to the new solver. Fortunately, libzypp comes
69 with a plethora of solver test cases, so we decided to make the solver
70 pass most of the test cases first. Klaus wrote a "deptestomatic"
71 implementation to check the test cases. Together with Stephan Kulow,
72 who is responsible for the openSUSE distribution, we tweaked and
73 extended the solver until most of the test cases looked good.
74 Duncan Mac-Vicar Prett, the team lead of the YaST team, also joined
76 development by creating Ruby bindings for the solver. Later, Klaus
77 improved the bindings and ported them to some other languages.
78 The attribute store
80 The progress with the repository format and the solver attracted
81 another hacker to the project: Michael Matz from the compiler team. He
82 started with improving the repository parsers so that patches and
83 content files also generate solvables. After that, he concentrated on
84 storing all of the other metadata of the repositories that are not used
85 for solving, like the package summaries and descriptions. At the end of
86 October, a first version of this "attribute store" was checked in. Its
87 design goals were:
88 • space efficient storage of attributes
90 • paging/on demand loading of data
92 • page compression
94 The first version of the attribute store used a different format for
96 storing information, we later merged this format with the solv file
97 format.
98 libzypp integration
100 Integration of the sat-solver into libzypp also started in October 2007
101 by Stefan Schubert and Michael Andres from the YaST team. The first
102 versions supported both the old solver and the new one by using the old
103 repository read functions and converting the old package data in-memory
104 into a sat solver pool. Solvers could be switched with the environment
105 variable ZYPP_SAT_SOLVER. The final decision to move to the new solver
106 was made in January of 2008, first just by making the new solver the
107 default one, later by completely throwing out the old solver code. This
108 had the advantage that the internal solvable storage could also be done
109 by using the solver pool, something Michael Matz already played with in
110 a proof of concept implementation showing some drastic speed gains. The
111 last traces of the old database code were removed in February.
112
114 Michael Schroeder <mls@suse.de>
115libsolv 03/02/2022 LIBSOLV-HISTORY(3)