add libsolv.3 man page

1 files changed, 119 insertions, 0 deletions

diff --git a/doc/libsolv.3 b/doc/libsolv.3
new file mode 100644
index 0000000..29f5f5e
--- /dev/null
+++ b/doc/libsolv.3
@@ -0,0 +1,119 @@
+.\" See LICENSE.BSD for license
+.TH LIBSOLV 7 "May 2011"
+.SH NAME
+libsolv \- package dependency solver library using a satisfiability algorithm
+
+.SH HISTORY
+This project was started in May 2007 when the zypp folks decided to switch
+to a database to speed up installation. As I'm not a big fan of databases,
+I wondered if there would be really some merit of using one for solving,
+as package dependencies of all packages have to be read in anyway.
+.PP
+Back in 2002 I researched that using a dictionary approach for storing
+dependencies can reduce the packages file to 1/3 of its size. Extending
+this idea a bit more, I decided to store all strings and relations
+as unique 32bit numbers. This has three big advantages:
+.IP - 2
+because of the unification, testing if two strings are equal is the same as
+testing the equality of two numbers, thus very fast
+.IP - 2
+much space is saved, as numbers don't take so much space as strings
+.IP - 2
+the internal memory representation doesn't take more space on a
+64bit system where a pointer is twice the size of a 32bit number
+.PP
+Thus the solv format was created, which stores a repository as a string
+dictionary, a relation dictionary and then all packages dependencies.
+Tests showed that reading and merging multiple solv repositories takes
+just some milliseconds.
+
+.SS
+Early solver experiments
+
+Having a new repository format was one big step, but the other area
+where libzypp needed improvement was the solver. Libzypp's solver was
+a port from the red carpet solver, which was written to update packages
+in an already installed system. Using it for the complete installation
+progress brought it to its limits. Also, the added extensions like
+support for weak dependencies and patches made it fragile and
+unpredictable.
+.PP
+As I wasn't very pleased with the way the solver worked, I looked at
+other solver algorithms. I checked smart, yum and apt, but could not
+find a convincing algorithm. My own experiments also were not very
+convincing, they worked fine for some problems but failed miserably
+for other corner cases.
+
+.SS
+Using SAT for solving
+
+SUSE's hack week at the end of June 2007 turned out to be a turning point
+for the solver. Googling for solver algorithms I stumbled over some note
+saying that some people are trying to use SAT algorithms to improve
+solving on debian. Looking at the SAT entry in wikipedia, it was easy
+to see that this indeed was the missing piece: sat algorithms are well
+researched and there are quite some open source implementations.
+I decided to look at the minisat code, as it is one of the fastest
+solvers while consisting of too many lines of code.
+Of course, directly using minisat would not work, as a package solver
+doesn't need to find just one correct solution, but it also has to
+optimize some metrics, i.e. keep as many packages installed as possible.
+Thus, I needed to write my own solver incorporation the ideas and
+algorithms used in minisat. This wasn't very hard, and at the end of
+the hack week the solver calculated the first right solutions.
+
+.SS
+Selling it to libzypp
+
+With those encouraging results I went to Klaus Kaempf, the system
+management architect here at SUSE. We spoke about how to convince the
+team to make libzypp switch to the new solver. Fortunately libzypp comes
+with a plethora of solver test cases, so we decided to make the solver pass
+most of the test cases first. Klaus wrote a "deptestomatic" implementation
+to check the test cases. Together with Stephan Kulow, responsible for the
+openSUSE distribution, we tweaked and extended the solver until most of
+the test cases looked good.
+Duncan Mac-Vicar Prett, the team lead of the YaST team, also joined
+development by creating ruby bindings for the solver. Later, Klaus
+improved the bindings and ported them to some other languages.
+
+.SS
+The attribute store
+
+The progress with the repository format and the solver attracted another
+hacker to the project: Michael Matz from the compiler team. He started
+with improving the repository parsers so that patches and content files
+also generate solvables. After that, he concentrated on storing all
+of the other metadata of the repositories that are not used for solving,
+like the package summaries and descriptions. In the end of October, a first
+version of this "attribute store" was checked in. Its design goals were:
+.IP - 2
+space efficient storage of attributes
+.IP - 2
+paging/on demand loading of data
+.IP - 2
+page compression
+.PP
+The first version of the attribute store used a different format for
+storing information, we later merged this format with the solv file
+format.
+
+.SS
+libzypp integration
+
+Integrating the sat-solver into libzypp also started in October 2007 by
+Stefan Schubert and Michael Andres from the YaST team. The first
+versions supported both the old solver and the new one by using the
+old repository read functions and converting the old package data
+in-memory into a sat solver pool. Solvers could be switched with
+the environment variable ZYPP_SAT_SOLVER. The final decision to 
+move to the new solver was made in January of 2008, first just by
+making the new solver the default one, later by completely throwing out
+the old solver code. This had the advantage that the internal solvable
+storage could also be done by using the solver pool, something Michael
+Matz already played with in a proof of concept implementation showing
+some drastic speed gains. The last traces of the old database code
+were removed in February.
+
+.SH AUTHOR
+Michael Schroeder <mls@suse.de>