TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn

                              by
               Steven Dorner   [email protected]
          Computer and Communications Services Office
               University of Illinois at Urbana

                         July 26, 1989


                          updated by
               Paul Pomes   [email protected]
          Computer and Communications Services Office
               University of Illinois at Urbana

                        August 2, 1992





_I_n_t_r_o_d_u_c_t_i_o_n

This document provides an overview of the CCSO Nameserver.  It
should give the reader a good idea of the capabilities, implemen-
tation and performance of the Nameserver.

_O_v_e_r_v_i_e_w

The CCSO Nameserver is a computer resident "phone book".  It can
keep a relatively small amount of information about a relatively
large number of people or things, and provide fast access to that
information over the Internet.[1] Here at the University of Illi-
nois, we keep the contents of the "white pages" of our
_S_t_u_d_e_n_t/_S_t_a_f_f _D_i_r_e_c_t_o_r_y as well as other selected information, in
the Nameserver.

Unlike a printed directory, the information in the CCSO
Nameserver is dynamic.  It can be updated at any time, from any
computer on the Internet capable of running the "client" program,
_p_h.[2] The Nameserver can also be taught to keep new _t_y_p_e_s of
information, such as electronic mail addresses or office hours,
without recompilation or change to the existing database.

____________________
  Converted to portable n/troff format using the -me macros from
funky Next WriteNow format (icch).
  [1]  The  collection of local, regional, and national networks
using the TCP/IP protocols.
  [2]  At  present this means 4.[23] BSD UNIX, VMS, VM/CMS, DOS,
or Macintosh.












22                             TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn


The remainder of this document will examine in somewhat further
depth three aspects of the Nameserver; what it does (CCaappaabbiillii--
ttiieess), how it does them (IImmpplleemmeennttaattiioonn), and how well it does
them (PPeerrffoorrmmaannccee).  There are in-depth documents describing some
of these aspects of the Nameserver; the interested reader may
refer to the _R_e_f_e_r_e_n_c_e_s section for the titles of these other
documents.

_C_a_p_a_b_i_l_i_t_i_e_s - _T_h_e _D_a_t_a_b_a_s_e

The CCSO Nameserver manages a database that consists of many
individual _e_n_t_r_i_e_s.  Each entry contains one or more _f_i_e_l_d_s, each
field consisting of a one or more printable ASCII characters
(including tab and newline).  Each field is associated with a
particular _f_i_e_l_d _d_e_s_c_r_i_p_t_i_o_n that is used to specify the behavior
of the field.  A field description includes a name, a maximum
length for the fields it describes, and certain _p_r_o_p_e_r_t_i_e_s that
determine how the field is used.

There are essentially no intrinsic limits on the size of the
database, in number of entries, numbers of field descriptions,
numbers of fields per entry, or sizes of fields.[3]

Certain fields[4] in the database are indexed.  Words from these
fields can be used as keys to select entries in the database.
Words from any field may be used to refine the selection made by
the key fields.  The indexing scheme used is "double-hashing",
and results in very fast lookups for key fields.  The hash table
is also indexed to facilitate pattern matching on the hash table
(and hence the database).

_C_a_p_a_b_i_l_i_t_i_e_s - _T_h_e _S_e_r_v_e_r

The database resides entirely on one computer and is managed by a
server program, _q_i (query interpreter).  Multiple instances of _q_i
may be executing at any one time; access to the database is con-
trolled by advisory locks.  Any number of processes may read the
database, unless a process is writing the database, in which case
all processes must wait for that process to complete its work
before beginning their own.

_Q_i uses a command-reply scheme like that used by FTP.[5] It
____________________
  [3] Actually there are limits imposed by the  32-bit  pointers
used  throughout  the  system.   Before  those  limits  could  be
reached, however, the database  would  likely  be  too  large  to
manage.
  [4] Those whose field descriptions in the  ._c_n_f  file  contain
the property "Indexed".
  [5] See RFC-959, _F_i_l_e _T_r_a_n_s_f_e_r _P_r_o_t_o_c_o_l (_F_T_P), J.  Postel  and
J. Reynolds.












TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn                             33


accepts commands from its standard input, and writes replies on
its standard output.  Both commands and replies are couched in
"netascii"; lines consisting of printable ASCII characters ter-
minated with a newline (ASCII 10) or carriage-return newline
(ASCII 13 ASCII 10) pair.  Additionally, the backslash "\" is
used to "escape" certain characters, as in the C programming
language.[6]

Commands consist of a keyword optionally followed by one or more
arguments or keywords.  Commands include: _q_u_e_r_y for querying the
database; _c_h_a_n_g_e for changing fields in entries; _a_d_d for adding
new entries.  Replies consist of a numerical code ranging from
-599 to 599, and additional text.  The numerical codes may indi-
cate an operation in progress (100-199), success (200-299), a
request for further information (300-399), temporary failure
(400-499), or permanent failure (500-599).  Replies in the range
from -599 to -100 indicate that further replies are to be
expected for the current command; they otherwise have the same
meanings as their positive counterparts.

The behavior of _q_i may be modified by use of certain _o_p_t_i_o_n_s,
accessed by the _s_e_t command.  The number of available options is
small; the most important options are _e_c_h_o, which causes _q_i to
print commands on its output before executing them, and _l_i_m_i_t,
which allows the user to specify a maximum number of entries to
which a command may be applied.

_Q_i operates in three different modes; anonymous, login, and hero.
Each mode is more liberal than the previous in the operations it
allows, and consequently more difficult to access.  Anonymous
mode is used to make queries of public information[7] and for a
few other innocuous purposes.  In anonymous mode, there is a max-
imum number of entries that can be viewed with one command; the
purpose of this limitation is to discourage the use of the
Nameserver for the preparation of mailing lists.  Anonymous mode
is used for most queries of the Nameserver.

To enter login mode, a user must identify himself as the owner of
a particular Nameserver entry by giving an _a_l_i_a_s (login name) and
a password.[8] In addition to the capabilities of anonymous mode,
____________________
  [6] The set of such escapes is much more limited  than  in  C;
only  "\n"  for newline, "\t" for tab, "\"" for double-quote, and
"\\" for backslash are allowed.
  [7]  I.e.,  to view fields whose field description contain the
property "Public".
  [8] Actually the user is asked to encrypt a string  using  his
password,  and _q_i compares the result returned with the result it
obtained by encrypting the same string  with  the  user's  stored
password.  This is to provide additional security when running _q_i
over networks; the user's password is never sent "in  the  clear"
over a potentially insecure network.











44                             TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn


login mode allows the logged in user to change fields from his or
her own entry in the Nameserver.[9]

Hero mode is entered either by entering login mode as a
Nameserver "hero" (superuser) or by running _q_i directly from a
terminal, rather than over a network.  In this mode, all artifi-
cial limits are removed; the hero may change any field in any
entry in the database, as well as view as many entries as he
wishes.  Hero mode is used mostly for administrative purposes.

_C_a_p_a_b_i_l_i_t_i_e_s - _Q_u_e_r_i_e_s

Since most of what the Nameserver does is answer queries, it is
fitting to describe queries more fully here.  A nameserver query
consists of five elements; the "query" keyword, values for one or
more indexed fields, values for zero or more non-indexed fields,
optionally the "return" keyword, and optionally a list of fields
to print from the selected entries.  A couple of examples will
clarify.  First, a plain query; the arguments are interpreted as
requests for words from the name or nickname fields, both of them
indexed fields:

   qi> query steven dorner
   -200:1:         alias: s-dorner
   -200:1:          name: dorner steven c.
   -200:1:         email: [email protected]
   -200:1:         phone: (w) 244-1765
   -200:1:       address: 181 DCL, MC 256
   -200:1:              : 1201 W. Washington, C, 61821
   -200:1:         title: res programmer
   -200:1:      nickname: Steve
   -200:1:         hours: 8-4 weekdays
   200:Ok.


Here is an example that uses all five elements.  The "department"
field is not indexed.

   qi> query dorner department=computing return name email department
   -200:1:          name: dorner steven c.
   -200:1:         email: [email protected]
   -200:1:    department: computing services office
   200:Ok.





____________________
  [9] Actually a user may change only those fields  whose  field
description contain the property "Change".












TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn                             55


_C_a_p_a_b_i_l_i_t_i_e_s - _T_h_e _C_l_i_e_n_t

Usually, the Nameserver is accessed via the "client" program _p_h.
This program makes a connection to a copy of _q_i on the machine
that keeps the Nameserver database.  It then provides assistance
to the user of the Nameserver; it formulates queries, formats
Nameserver responses, and provides other conveniences.

_P_h operates in two modes; command-line and interactive.  In
command-line mode, _p_h forms a Nameserver query from the arguments
given it, sends it to _q_i, prints the result, and exits.  In
interactive mode, _p_h reads commands from the user, relays them to
_q_i, and prints _q_i's responses.  The responses are automatically
sent through a paging program.  Some commands given to ph are
expanded into more than one qi command.  For example, the _p_h
"edit" command first asks _q_i for the value of the desired field,
puts that value in an editor where the user edits it as s/he
pleases, and then issues a "change" command to change the field
to its desired new value.

_I_m_p_l_e_m_e_n_t_a_t_i_o_n - _T_h_e _S_o_u_r_c_e

The Nameserver is written in C (a small parser is written in
lex[10]), and runs on UNIX systems.  The client, _p_h, may be run
on 4.[23]BSD derived systems.  A version of _p_h exists for VMS,
DOS, Mac, and a limited version exists for VM/CMS systems.

There were at last count 320,000 bytes of C and lex source code;
some 6,000 statements in 63 files.  This source is divided into
several distinct categories; _q_i (230,000 bytes, 28 files, 3500
statements), _p_h (46,000 bytes, 3 files, 700 statements), utili-
ties (89,000 bytes, 21 files, 1700 statements), and libraries
(19,500 bytes, 11 files, 300 statements).

The database and _q_i reside on a Digital Equipment Corporation
VAXServer 3500 running Ultrix.

_I_m_p_l_e_m_e_n_t_a_t_i_o_n - _T_h_e _D_a_t_a_b_a_s_e

The database is kept in six files with the extensions ._d_i_r, ._d_o_v,
_i_d_x, ._i_o_v, ._s_e_q, and ._b_d_x.  The ._d_i_r and ._d_o_v files contain the
actual data.  The ._i_d_x and ._i_o_v files contain the hash table,
with pointers into the data files.  The ._s_e_q file contains all
the words from the hash table, sorted alphabetically, along with
pointers into the hash table; it is used for pattern-matching on
the hash table.  The ._b_d_x file contains a tree of four-letter
nodes, each node pointing to where entries with those four
letters begin in the ._s_e_q file; the ._b_d_x file speeds search of
____________________
  [10] See _L_e_x-_A _L_e_x_i_c_a_l _A_n_a_l_y_z_e_r _G_e_n_e_r_a_t_o_r, M.E.  Lesk  and  E.
Schmidt.












66                             TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn


the ._s_e_q file.

The ._d_i_r file consists of a header and one fixed-length record
for each entry in the database.  If there is too much data for
one record, the remainder is placed in the ._d_o_v file.  The ._d_o_v
file also consists of fixed-length records, and if one is not
enough, the remainder can be placed in more ._d_o_v records.  Thus,
an entry is really a linked list of fixed-length records, and is
not limited in size.  It is relatively easy to play with the
sizes of the ._d_i_r and ._d_o_v records (before compilation and
installation of the database) for optimum performance.  We use a
fairly small record size in the ._d_i_r file, to minimize space was-
tage,[11] and a fairly large record size in the ._d_o_v file, to
minimize linking.  Most entries are wholly contained in the ._d_i_r
file; most of the rest require only one ._d_o_v record.

Each entry begins with some fixed-length information, followed by
the fields that make up its data.  Each field is a null-
terminated ASCII string.  A field begins with an ASCII string
that is the id of the field description for that field, and a
colon.  The field's data follows, and then the null terminator
(ASCII 0).  Tagging each field with its description number means
that the database is not sensitive to the presence, absence or
order of the fields.  This in turn means that field descriptions
can be added to the Nameserver at will, and the newly-defined
fields used, without recompilation or rebuilding of the database
(see _I_m_p_l_e_m_e_n_t_a_t_i_o_n - _F_i_e_l_d _D_e_s_c_r_i_p_t_i_o_n_s below).

The ._i_d_x file is made up of a fixed number of fixed-length
records.  Each record that is in use contains a word from an
indexed field, and a set of pointers to the ._d_i_r records that
contain the word in an indexed field.  Overflow in the ._i_d_x file
is handled like overflow in the ._d_i_r file; the excess pointers
are put in one or more fixed-length records in the ._i_o_v file.
Words are indexed by computing a hash function.  If the selected
location is not empty but does not contain the desired word, the
hash function is iterated, until a limit is reached (implying the
failure of the index) or the word or an empty spot is found.  If
the spot is empty, the word and a pointer to the entry in which
it occurs is placed in the record.  If the spot is not empty, a
pointer to the entry is appended to the list of pointers for that
word.

           Nroff version of Figure 1 not available.

               _F_i_g_u_r_e _1.  _D_a_t_a_b_a_s_e _O_r_g_a_n_i_z_a_t_i_o_n

____________________
  [11] Not entirely successfully - see  _P_e_r_f_o_r_m_a_n_c_e  -  _D_a_t_a_b_a_s_e
_S_i_z_e below.













TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn                             77


The ._s_e_q file uses fixed-length records (called _l_e_a_v_e_s) to keep a
sorted list of all the words in the hash table (._i_d_x and ._i_o_v
files).  Each leaf contains up to four words, and a pointer to
the next leaf in alphabetical order.  With each word is stored a
pointer into the hash table where that word is found.

The ._b_d_x file has records (called _n_o_d_e_s) that contain one four-
byte key, and two pointers; one to the previous node in alphabet-
ical order, and one to the following node in alphabetical order.
If a particular four-byte key happens to begin a leaf, that key's
node will contain a pointer to that leaf instead of a pointer to
another node.

_I_m_p_l_e_m_e_n_t_a_t_i_o_n - _Q_u_e_r_i_e_s

An incoming query is first broken down into its component parts.
Then, the selection arguments of the query are checked for
indexed arguments.  The longest indexed arguments[12] are looked
up one by one in the hash table (or, if they contain pattern-
matching characters, a search is made through the ._b_d_x and ._s_e_q
files for each pattern).  The index entries are "anded" together
to select only those entries that contain all of the indexed
words.

Next, the selected entries are fetched one by one, and matched
against the argument list.  This is done for two reasons.  First,
the fact that an entry appears in the index for a word says noth-
ing about which _f_i_e_l_d the word is to be found in; it merely notes
that the word does appear.  Therefore, it is necessary to recheck
indexed fields, and make sure the words in question appear in the
proper fields.  Second, the non-indexed words must be checked, to
see that they appear in the proper fields in the entry.

If the entry passes the checks, the selected fields (or a set of
default fields) are printed.

_I_m_p_l_e_m_e_n_t_a_t_i_o_n - _F_i_e_l_d _D_e_s_c_r_i_p_t_i_o_n_s

Field descriptions are kept in a file that _q_i reads each time it
is run.  This file consists of lines describing each field, in
ASCII, with colons separating the elements in a line.  First
comes the id number of the field, then the name of the field and
its maximum length.  Finally, there is a colon-separated list of
properties for the field.

____________________
  [12] Actually, the longest indexed arguments free of  pattern-
matching  metacharacters.   Pattern matches take much longer than
normal index lookups since  the  ._b_d_x  and  ._s_e_q  files  must  be
searched,  and  since  such searches frequently result in a large
number of matches being selected.












88                             TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn


Since this file is read each time _q_i starts up, lines can be
added to define new fields at will.  All subsequent invocations
of _q_i will be able to recognize and use the fields.

The major properties fields may have are Indexed, Public,
Default, Lookup, and Change.  Fields marked Indexed are kept
track of in the database's index.  At least one such field _m_u_s_t
be included in every query.  Fields marked Public may be viewed
by anyone using _q_i in anonymous or login mode.  Fields not marked
Public may only be viewed by the entry's owner in login mode, or
by someone using _q_i in hero mode.  Default fields are printed if
no "return" clause is given in a query.  Lookup fields may be
used in the selection part of a query; a field not marked Lookup
cannot be used to select entries.[13] Finally, a user in login
mode in _q_i may change any of his or her fields that are marked
Change.

_P_e_r_f_o_r_m_a_n_c_e - _D_a_t_a_b_a_s_e _S_i_z_e

Our database contains 80,140 entries, totalling 16 megabytes of
information.  The ._d_i_r and ._d_o_v files together are 33 megabytes;
nearly half the space is wasted.  This percentage could be
reduced by reducing the record size of the ._d_i_r file.

The hash table, which has room for 450,001 words, actually con-
tains 157,324 words and 270,784 pointers, for a total of 1.3
megabytes of hash table.  The ._i_d_x and ._i_o_v files are 19.5 mega-
bytes in size; even allowing for a large number of empty hash
table slots (necessary for performance), most of the space is
wasted.  As with the ._d_i_r file, reducing the record size in the
_i_d_x file would help the situation.

Rounding out the database is 7.2 megabytes in the ._b_d_x and ._s_e_q
files.

_P_e_r_f_o_r_m_a_n_c_e - _S_p_e_e_d

To test speed, we took 300 words from different parts of the
index, and looked each one up using _q_i.  _Q_i found 396 entries in
78 seconds; that is about 1/4 second per lookup.  Using four
letter keys and wildcarding the rest, _q_i found 9213 entries in
460 seconds, for about 11/2 seconds per lookup.

In actual use over a network, response is slower, since the
client program must establish a connection with the host that has
the database.  Looking up 100 indexed words in separate
____________________
  [13] You might decide, for example, that no one should be  al-
lowed to be found by his or her phone number.  You could mark the
phone number field as Public (so it  could  be  viewed)  but  not
Lookup (so no one could use it in searches).












TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn                             99


invocations of _p_h took 109 seconds, or 1 second per lookup; 118
entries were found.

_P_e_r_f_o_r_m_a_n_c_e - _U_s_a_g_e

In a recent week, typical of most weeks, we had 3100 uses from
over 70 campus machines.[14] By far most of the commands given
were queries (3643).  There were also 175 logins, 264 changes,
and a few hundred other commands issued.  Of the commands: 58%
were successful; 26% were queries that found no entries; 8% were
queries that found too many entries; 4% were other errors; 3%
were rejected because they required login mode, but were being
given in anonymous mode; and 1% failed due to command syntax
errors.

_F_u_r_t_h_e_r _D_i_r_e_c_t_i_o_n_s

Overall, we are fairly satisfied with what has been done to date.
Ongoing efforts will be centered around making the Nameserver
convenient to use in a distributed environment.  This will pri-
marily involve allowing users to specify a server, although some
peripheral issues are also in need of resolution.

Additionally, we will make some attempts to remove wasted space
from the database and its associated index; this is not a high
priority since the database, for all its wasted space, is still
not unmanageably large.

_D_i_s_t_r_i_b_u_t_i_o_n

The CCSO Nameserver is Copyright (C) 1988 by the University of
Illinois Board of Trustees.  Portions of the software are Copy-
right (C) 1985 by CSNet.  It is distributed free of charge, and
is available for anonymous ftp from uxc.cso.uiuc.edu, in the
net/qi subdirectory as well as the pub/qi.tar.Z file.  The client
software for UNIX and VMS is available on the same computer, in
the net/ph subdirectory and in the file pub/ph.tar.Z.  No support
will be provided by the University, and the University is not
liable for anything bad that happens as a result of its use.  The
software may not be redistributed without permission from CSNet.

_R_e_f_e_r_e_n_c_e_s

_U_N_I_X _M_a_n_u_a_l _P_a_g_e_s.  Manual pages are available on _p_h(1) and
_q_i(8).


____________________
  [14] It is impossible to get an exact count of the  number  of
machines, since there are some machines that use another computer
as a relay; these machines do not show up in the count.












1100                            TThhee CCCCSSOO NNaammeesseerrvveerr -- AA DDeessccrriippttiioonn


_T_h_e _C_C_S_O _N_a_m_e_s_e_r_v_e_r, _A_n _I_n_t_r_o_d_u_c_t_i_o_n by Steven Dorner.  A brief
introduction geared at a new user of _p_h.

_T_h_e _C_C_S_O _N_a_m_e_s_e_r_v_e_r, _W_h_y by Steven Dorner.  A recap of the design
decisions that made our Nameserver what it is, including evalua-
tions of some similar systems available when our Nameserver was
designed.

_T_h_e _C_C_S_O _N_a_m_e_s_e_r_v_e_r, _S_e_r_v_e_r-_C_l_i_e_n_t _P_r_o_t_o_c_o_l by Steven Dorner.
Full documentation of the language used between the Nameserver
server program, _q_i, and the outside world.

_T_h_e _C_C_S_O _N_a_m_e_s_e_r_v_e_r, _G_u_i_d_e _t_o _I_n_s_t_a_l_l_a_t_i_o_n by Steven Dorner.  How
to install the programs that make up the CCSO Nameserver.

_T_h_e _C_C_S_O _N_a_m_e_s_e_r_v_e_r, _A _P_r_o_g_r_a_m_m_e_r'_s _G_u_i_d_e by Steven Dorner.  In
depth documentation for anyone maintaining or wishing to com-
pletely understand the CCSO Nameserver.

_R_e_b_u_i_l_d_i_n_g _a _N_a_m_e_s_e_r_v_e_r _D_a_t_a_b_a_s_e _I_n _2_4 _E_a_s_y _S_t_e_p_s by Steven
Dorner.  Describes how we build a database, beginning with raw
data we receive from our Administrative branch.

_A_c_k_n_o_w_l_e_d_g_e_m_e_n_t

Our Nameserver is very similar in function and philosophy the
CSNet nameserver.  In fact, the database management code from
that nameserver, with some modification, is used in our
Nameserver.  We are grateful to CSNet that their program was made
available to us.

You are viewing proxied material from bitreich.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.