doc/libsolv.3

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