cmd/dss/dss.mm

.xx noindex
.xx meta.description="data stream scan"
.xx meta.keywords="compression data scan query"
.MT 4
.TL
DSS: Data Stream Scan
.AF "AT&T Labs Research - Florham Park NJ"
.AU "Glenn Fowler <gsf@research.att.com>"
.AU "Balachander Krishnamurthy <bala@research.att.com>"

.H 1 Abstract
.I dss
(data stream scan) is a framework for describing, transforming,
reading, querying, and writing streams of record oriented data.
It is implemented as a command and library API.
The API is extended by DLLs (shared libraries) that define data domain
specific I/O, type and query functions.
The goal is to provide a best in class repository for data scanning,
along with up to date documentation as a side effect of
coding to the API.
Numerous large scale network applications have used
.IR dss ,
significantly reducing the amount of time spent in coding.
Typical applications run terabytes of data through
.I dss
and have constructed custom queries very quickly.
The key reasons for the success of
.I dss
are its unique architecture,
generic template, and speed.
In speed,
.I dss
compares extremely favorably against
.BR perl (1),
the typical recourse in the networking community, and against customized
C/C++ code written to deal with a single domain dataset as well.
The range of applications for which
.I dss
has been
successfully applied over the last two years is wide and has involved
large volumes of
.I netflow
data,
.I BGP
data, HTTP proxy and server
logs, and OSPF LSA (Link State Advertisements.)
Often the use of
.I dss
has led to fearless exploration of ideas
across very large volumes of data.

.H 1 Introduction
Parsing is a critical part of record oriented data analysis.
It involves describing the record structure and splitting the
record fields into a form suitable for the analysis tools.
Each tool may have its own idiosyncratic record description and field
identifier syntax and format,
and some tools may be better at hiding the details than others.
For example, tools like
.BR grep (1) ,
.BR awk (1)
and
.BR perl (1)
intermix low and high level definition details within the same program.
Although relational databases provide high level abstractions and GUI
interfaces to the end user, a database expert is usually involved with
loading the data in the first place.
.P
It is not uncommon to have many analysis tools, each with an independent
parser,
applied to the same data within a single group of analysts.
This in itself is not a bad situation.
A relational database may be overkill for an application that needs
to visit each record only once;
hand coded programs may be inappropriate for data that is too large to fit
in memory, or that may benefit from indexed access, or that may undergo many
record format changes.
However, subtle parsing differences between independent analyses can make
comparisons difficult.
The absense of read or load errors does not necessarily mean that the data
was read correctly.
Certainly data access bugs can be fixed as they are discovered, but in the
worst case this could mean translating the fix to every analysis tool.
In some cases it may even be impossible to recover from bugs that affected
intermediate legacy data.
.P
.I dss
provides a data abstraction that can be used to mitigate parsing differences
between different analysis tools.
The key is that the abstraction provides efficient (in space and time) IO
support
.I and
a uniform interface for all data.
The approach has multiple benefits:
.BL
.LI
allows data analysts to focus on analyzing data
.LI
provides a target API for data IO coders
.LI
third parties familiar with the data abstraction model are
automatically proficient in new data domains
.LE
.P
.I dss
did not originate in a vacuum -- it arose out of experience with
.B BGP
data analysis in our lab.
A few in-house
.B BGP
tools gained popularity with the analysts.
Each analyst stepped up with new
.B BGP
feeds and file formats:
Ciso router table dumps,
.B MRT
format data, and ad-hoc flat files.
Each new format prompted a recoding effort, which by this time meant
changing a handful of related but slightly different implementations
that had evolved over a four year period.
Merging the
.B BGP
IO and parsing into a unified API was a big time saver, and also uncovered
several embarassing bugs that had remained hidden for years.
In addition, by employing best of class coding practices
(i.e., releasing the inner hackers)
the merged interface produced an efficient
.B MRT
parser that was 10 times faster than the one published by the originators
of the format.
By the time the analysts requested help on
.B NETFLOW
data the lesson had been learned, and
.I dss
was designed and implemented.

.H 1 "Data Abstraction Model"
.I dss
partitions data stream access into components that
form a uniform model for all data.
The model guides both the implementation and user interfaces.
It supports independent data methods, each with one or more physical
formats.
For example, Cisco router dump and
.B MRT
formats for the
.B BGP
method,
and all versions of the Cisco dump format for the
.B NETFLOW
method.
.P
Each user visible item, whether in the base API or in DLL extensions,
is placed in a dictionary.
A dictionary entry has a name and descriptive text suitable
for inclusion in a
.BR man (1)
page.
This information can be listed by the runtime interfaces, so up to date
documentation is always available.
.P
Figure 1 illustrates the component relationships in the
.I dss
model.
Some components are part of the default
.I dss
library, but most are implemented as independent DLLs that
are selected and loaded at runtime.
The
.I dss
components are described below.

.H 2 "TRANSFORM Components"
Transforms are generic data independent filters that are applied
to the raw data.
They are automatically detected and applied on input, and are selectively
applied on output, as determined by user and/or data specific options.
.I dss
currently supplies compression transforms for
.IR gzip ,
.IR pzip ,
.I bzip
and
.IR compress ;
delta (\fIfdelta\fP) and encryption support is planned.
A transform may be implemented within the main
.I dss
process
(e.g., the
.BR sfio (3)
.BR gzip (1)
discipline)
or as a separate process (e.g.,
.I gzip
or
.I gunzip
connected by a pipe.)
The current vs. separate process choice may even be delayed until runtime.
For example, on a multi-cpu architecture with idle processors, running
.I gunzip
as a separate process may take less real time than a single process
implementation.
.P
Transforms allow data to be stored in the most efficient (or secure) manner.
The data need only be converted when accessed.
Given the volumes of available network data, compression or deltas,
along with sampling, is essential for archiving.

.H 2 "METHOD Components"
Methods describe the data records for a specific data domain.
A method must be specified before
.I dss
accesses any data.
The method data description includes:
.BL
.LI
A dictionary of file storage formats with:
.BL
.LI
An identification function that automatically determines input formats.
A format may be a different version (\fInetflow\fP versions 1, 5 and 7) or
a completely different structure (\fIBGP\fP \fIMRT\fP files vs. \fICisco\fP
router dumps.)
.LI
A record read function.
This function also handles format specific headers and trailers.
.LI
A record write function.
This function also handles format specific headers and trailers.
.LE
.LI
A dictionary of record field types and names that includes the union of
fields available in all supported formats.
Fields absent in a particular format will have empty values.
For example, the
.I dss
.B netflow
method supports all popular netflow formats.
The same queries can be used on any of the
.I netflow
formats.
The
.B "source mask"
field, not available in the version 1 format, is still available for
version 1 queries, but will have a default value of 0.
If a new
.B foo
field were to be introduced in the version 101 format then it would simply
be added to the
.B netflow
method dictionary but would have an empty value for all but version 101
(and newer) data.
.LI
An optional canonical record that provides access to a C structure
representation of each record.
A method that provides a canonical record can simplify ad-hoc C queries.
The ad-hoc query can be implemented as a
.I dss
.B QUERY
component function.
This function is called for each record in the input data.
.LE

.H 2 "TYPE Components"
A
.I dss
type provides functions that convert data between internal and external data
representations.
Some types may also have a base type that provides alternate access to the
same data.
Non-numeric constants are represented as \f5'...'\fP or \f5"..."\fP quoted
strings.
.P
For example, the
.B ipaddr_t
type in the
.I dss
.B ip_t
type library implements an IP address as a 32 bit unsigned integer
(the base type), and converts between the integer representation and
quoted dotted-quad and DNS names.
.P
A type may optionally provide a match function that overrides the default
regular expression string match.
For example, the
.B ipaddr_t
type match function does IP prefix matching and the
.B aspath_t
type match function does AS path regular expression matching that treats
AS numbers as individual tokens (as opposed to the inefficient alternative
of converting the AS path to a string and applying a string regular
expression match.)

.H 2 "QUERY Components"
Queries are the user visible part of
.IR dss .
They are used to select, filter, and summarize data streams.
There are two forms of queries.
Interpreted queries provide named access to the data fields using
C style operators.
Dynamic queries provide
.I UNIX
style command access to the record stream.
Queries may be composed in a manner similar to a
.I UNIX
pipeline.
The main difference is that a pointer to the current record, as opposed to
the actual record data, is passed between query components.
Interpreted queries are generic and may be used with any method.
Dynamic queries may be generic or method specific; method specific queries
produce a diagnostic when used with the wrong input method.

.H 1 "dss Library Interface"
The library provides two main interfaces for handling data:
.BL
.LI
C style expression interpreter:
.BL
.LI
basic
.BR number ,
.B string
and
.B reference
types
.LI
compile time callout functions for expression optimization and overloads
.LI
execution time callout functions for all operators
.LE
.LI
domain specific methods:
.BL
.LI
data IO functions
.LI
data types and conversion functions
.LI
specific data field types and names
.LI
method types for handling domain data in different formats
.LE
.LE
The library applies
.BR gzip (1)
and
.BR pzip (1)
decompression as needed for all methods.
.P
Applications based on the library can:
.BL
.LI
perform IO on the data stream
.LI
report information about the data stream
.LI
evaluate expressions to filter records from the stream
.LI
format output for reports or further processing
.LE

.H 1 "dss Command Interface"
The
.BR dss (1)
command provides a command level interface to the
.BR dss (3)
library.
.EX
dss --man
.EE
lists the
.BR man (1)
page on the standard error.
.EX
dss --?method
.EE
lists the available methods; methods are implemented in DLLs
found on sibling directories of
.BR $PATH .
.EX
dss -x foo --man
.EE
provides details on the
.I foo
method.

.H 1 "Performance"
Real time for typical
.I netflow
data queries.
.TS
center allbox;
b b b b b
l l n n n.
Command	Window	Records	Size	Time
interpreted	10 min	1,715,850	-	0m8.27s
library	10 min	1,715,850	-	0m4.27s
interpreted	1 day	229,448,460	27Gb	17m34s
library	1 day	229,448,460	27Gb	9m23s
ascii pipe	1 day	229,448,460	27Gb	56m43s
.TE

.H 1 REFERENCES
.VL 1i
.LI
.xx link="../publications/dss-2004.pdf	DSS: Data Stream Scan",
with Balachander Kirshnamurthy.
.LE