This is a relational database backend library written explicitly for
use with the NIS+ rpc.nisd server. It implements a relational database
with a small series of access functions allowing NIS+ structures (mainly
entries) to be stored and retrieved in a (hopefully) speedy manner in
response to NIS+ queries.

The Sun implementation of the NIS+ database uses something refered to
in the nis_db(3n) manual page as the 'Structured Storage Manager' (SMM).
This implementation is actually built on top of Berkeley DB. You need
to have the Berkeley DB library available in order to build this
library and to link programs that use it. (With FreeBSD, NetBSD, BSD/OS
and OpenBSD, the Berkeley DB library is part of libc, so no special
steps need to be taken for these operating systems. Linux users will
have to do a little more work.)

The following is a description of how this library implementation
works. The author does not claim to be a database expert; there
are probably better ways to go about doing this. This was just the
simplest solution my arguably feeble mind was able to conjure up.

Note: In the Sun libnisdb.{a,so} in Solaris 2.5, db_free_result() 
appears to be a C++ function. This is to say that it appears as a
C++ mangled name in the library symbol table. Calling it from C as
db_free_result(foo) doesn't work when you try to call it from a C
program (such as the dbtest.c program included with this library's
source distribution). This is because the C compiler generates a reference
to the non-mangled function name, and the linker fails to make the
connection.

The NIS+ service allows clients to make queries using a series of
attributes. This is to say that a client may ask the NIS+ server for
all entries in a particular table where (in the case of a passwd
table, for instance) all the UIDs are '0' and all the shells are
'/bin/csh.' (It happens that when a passwd table is created,
generally only the name and UID attributes are defined to be
searchable, however for this example we need to illustrate what
happens for queries that return more than one matching entry.)
By contrast, NIS v2 only allowed simple 'key/value' queries: a
client could only ask for the data associated with a given key.
With NIS v2, a single query would always yeild only a single datum.
This is not true of NIS+.

The NIS+ database backend is used to store tables. A is table made up
entries, each of which conists of several discrete fields. If you
stack a bunch of entries on top of each other, these fields align
to form columns. For a passwd type entry, the first column would contain
all usernames, the second would contain all passwords, the third
all UIDs, and so on. At least one column is defined to be searchable,
which means that a client may ask for data based on the contents
of a field in a particular column. A client may, for example, ask
for all entries where the 'name' column contains the value 'foouser.'
The client would then get back the entry for 'foouser' in the
table, thus obtaining foouser's passwd entry.

This sort of retrieval can become complicated when more than one
column is defined to be searchable. The database has to search for
several records, and it must do so quickly. While the Berkeley DB
library allows for relatively fast key/data queries with large
databases, it is not designed to handle relational queries. The
NIS+ database library attempts to provide a method for performing
relational queries using Berkeley DB as a backend.

To do this, we actually store several pieces of data for any given
entry. Entries themselves need to be specially encoded. The NIS+
protocol definition defines a structure called entry_obj, which
contains a list of attributes and values. It also contains an
array of entry_col structures. (These are called objects in most
NIS+ references. I happen to loathe the whole concept of object
oriented programming and will therefore not stoop to using such
ridiculous terminology. You have been warned.) In order to store
this structure in a transparent fashion, the library uses the
xdrmem_create() interface to the XDR library to encode it into
a single contiguous buffer of a known size. The buffer itself
is then run through a hash function to generate a (hopefully)
unique numerical 'key' that can be used to refer to the entry
later. This numerical key and the encoded buffer are stored as
a single key/data pair:

           KEY                            DATA
      _______________           ____________________________________
     [ hash value #1 ]  ---->  [ XDR-encoded entry_obj structure #1 ]
      ---------------           ------------------------------------
      _______________           ____________________________________
     [ hash value #2 ]  ---->  [ XDR-encoded entry_obj structure #2 ]
      ---------------           ------------------------------------
      _______________           ____________________________________
     [ hash value #3 ]  ---->  [ XDR-encoded entry_obj structure #3 ]
      ---------------           ------------------------------------

Next, a series of key/value pairs are stored using the fields
supplied in the entry. For example, each entry in a passwd
table contains seven fields called 'name,' 'password,' 'uid,'
'gid,' 'gcos,' 'home,' and 'shell.' Of these, the 'name' and
'uid' fields are usually marked as searchable, which means we can
use them for search criteria. Therefore, in addition to
the entry structure itself, we have two field/value keys that can
be used to describe a particular entry. A given field/value key may
map to more than one entry (i.e. there may be several entries where
uid = 0, therefore the uid=0 field/value key is actually associated
with more than one entry). This allows us to form relations between
different entries. For example, say we have the following passwd
entries:

    foo:*:1:1:Dumb User:/dev/null:/bin/csh    ( entry 1 )
    bar:*:2:0:Dumber User:/dev/null:/bin/csh  ( entry 2 )
    baz:*:3:0:Dumbest User:/dev/null:/bin/sh  ( entry 3 )

Let us further say that we wish to store these entries in a table
where the GID and shell fields are searchable. (I realize that
normallu only the 'name' and 'UID' fields are searchable -- humor me.)
We would encode each of these entries and store then as shown above:
each entry would be stored as data with a 32-bit hash value as a key.
We would then store the following relations:

         KEY                     DATA

    [ GID = 1 ]  ---->          [ hash value #1 ]

    [ GID = 0 ]  ---->          [ hash value #2 ] [ hash value #3 ]

    [ shell = /bin/sh  ] ---->  [ hash value #3 ]

    [ shell = /bin/csh ] ---->  [ hash value #1 ] [ hash value #2 ]


Let's say now that a user queries the database for all entries where
GID = 1 and shell = /bin/csh. The database retrieves the data associated
with the 'GID = 1' and 'shell = /bin/csh' keys, which yeilds a total
of three hash values. However, the GID = 1 case yeilds only one
value. This means there can be only one possible matching entry,
and that only one of the entries in the 'shell = /bin/csh' case
will satisfy the query.

To find the correct entry, the library compares the values in
the larger hash value set starting with the first one and working its way
down (since the values are all 32 bit unsigned ints, this can easily be
accomplished using an incrementing pointer and integer comparisons).
In this example, it happens that only hash value #1 appears in the 
hash value list of both the GID = 1 and shell = /bin/csh relations.
This means that only hash value #1 satisfies the conditions of the query.
Now that the database has determined this, it can retrieve the data
associated with hash value #1 and return it to the caller.

----------------------------------------------------------------------------

Addendum:
--------


Further experimentation with the Sun libnisdb has led to a design
change. A performance comparison between the Sun library and the
finished original version of this library showed that the Sun library
was nearly twice as fast under the following circumstances:

- A sample program is used to create and populate a table called
  'passwd.org_dir.test1234.' using the following criteria:

	o The 'name' and 'uid' fields were marked as
	  TA_CASE | TA_SEARCHABLE.

	o All other fields were marhed TA_CASE (which doesn't
	  really mean much).

	o ta_maxcols was 64

	o ta_col_len was 7

- A sample passwd file containing approximately 38,000 entries was
  used to populate the table. Of these, there were a small handful
  that were related (37 had a uid of 0).

- The test was made on a SPARCstation 10 with 64 MB of RAM running
  Solaris 2.5.1. The programs were compiled with gcc 2.7.2 using
  -O optimization.

- The resulting table was written to a tmpfs on /tmp so as to avoid
  wasting disk space. (This means the actual completion times were
  artificially reduced compared to what they would have been for
  a real filesystem, but since this is only a comparison test it
  doesn't really matter.)

- All 38,000 entries were added in one continous loop before the
  program exited.

Results showed that the program linked with the Sun library took
approximately 52 seconds to add all 38,000 to the table. By contrast,
this library took on the average of 1 minute 40 seconds to perform
the exact same operation. The following additional observations were
made:

- The Sun library created a file called passwd.org_dir.test1234..log
  which grew to approximately 8MB in size before the population of
  the table was completed.

- A third file called was then created which was called
  passwd.org_dir.test1234..tmp which later grew to about 9MB
  in size. While this file was being created, the .log file
  remained at a constant size.

- The final table file was also 9MB in size.

- Running a later program to do a db_list_entries() on the resulting
  table took a considerable amount of startup time before any
  results were generated.

From this, the author has drawn the conclusion that the Sun library
maintains two seperate sets of data for each table: the actual collection
of entries and a fairly large structure or collection of structures
used to describe the relations between the entries. The relation data
is kept in memory; when entries are added, the entries are written to
the '.log' file while the relation data in memory is updated. When
the database is closed, the relation data is written to the table
file as one large chunk. When the table is reopened, the library
reads all of the relation data back into memory -- this is where
the startup delay comes from.

The original design for this library called for saving relation data
immediately, as it became known. This results in extra file I/O
operations and syscall overhead which the Sun library is able to
avoid until the last minute.

The advantage to the Sun approach is an overall improvement in
performance while the rpc.nisd server is running in exchange for
a startup delay penalty and increased use of memory. The original
design for this library traded off the extra performance in exchange
for a more uniform performance curve and a smaller and less volatile
memory footprint. It is not clear which option is preferable in
actual operation. Sun would prefer that you purchase heavy duty
hardware from them, hence it makes sense that they would favor
the more memory intensive approach, which requires more hardware
resources to run efficiently.
