Stonebraker
Are we just whistling dixie? Sounds like this can be done by WebLogix and
DB2 (according to Gray and DeWitt.) Or is there anything that can't be
done by a standard app server and a DBMS? Purpose of this session is
to enumerate the real challenges. This should be a reality check on
functionality that is needed in a stream DBMS.
Going to present apps. What do venture capitalists view as app for
streaming stuff? Must sell into the "real time enterprise" -- not a
sensor world, though it is a stream world. But, there are some sensor
applications now, and there probably will be more in the future.
Real-time enterprise (RTE):
Traditional view: decision support and OLTP don't mix. Bulk data
mover scrapes data from operational system into a warehouse, which has
the history of everything. An analyst runs queries against the
warehouse, and uses that knowledge to change the operations to
something different. Approx. 1 month feedback loop. Fortune 500 would like
to do this much more quickly. Oriented towards identifying "pearls of
wisdom".
Not oriented towards tactical (real time) business analysis and
tuning.
Dewitt: Doesn't Walmart do this every day?
Stonebraker: Yeah, but Amazon wants to be able to compare today to
yesterday, and they can't. People also want to detect
money-laundering in real-time. That's the RTE.
Example: Charles Schwab. Has a system to compute the commission on
each trade in real time. ~300K of rule-based code (home brew) -- pick
up a message, compute a number on it. No aggregates, but they're
having a hard time because they have lots of legacy (slow) DBMS
lookups. They want to do this in real time, not after the fact. This
is an operational system, totally stream based.
Sailesh: What is the real time application?
Stonebraker: I don't know. When you make a trade with Schwab, they
need to compute the commission when you make the transaction.
Jennifer: That's not real time.
Franklin: "Real time" just means fast.
Stonebraker: It's not clear why you can't do this with a conventional
system.
Next example: Fidelity.
In Fidelity, trades originate in lots of systems, and get executed in
several different places (e.g. Island, locally, etc.) They have a
system that does content routing in trades in real time. Complain
that it is too slow, and want prioritization of trade queue (for
important customers, etc.) Not totally clear why it's not fast enough
(e.g. is it a database problem) -- why wouldn't MQSeries work?
Mehul: What kinds of transactional semantics are required?
SB: Not much -- just have to guarantee message delivery.
But doesn't seem like RTE is very compelling -- not clear we really
need streaming DBMS here.
Real compelling app: US Army (MITRE) battalion monitoring. Placing
sensors on every vehicle, human, etc. Want to know where vehicles and
troops are. Want to triage people. A few thousand sensors reporting
state in real time.
20 queries -- on Jennifer's web site. Queries are a mix of historical
queries -- e.g. "give me a track of where tank 17 has been in the last
3 hrs", or continual queries, e.g. "tell me when one of my buddies is
pointing a gun at me."
Some are very hard, e.g. "tell me when 3 of my 4 tanks have crossed
the front line."
QOS is critical, according to these guys. Really want triage -- e.g.
react to who's important. Main bottleneck is the network --
computation is not the issue. Big problem is really allocating
bandwidth in a distributed system. But are very interested in QOS in
the context of distributed systems.
Stan: Disagree a little. Sensors on soldiers may be pretty darn tiny.
SB: Problem -- military apps are not politically correct. Hard to
sell a research program on military apps.
Hari: NW is the bottleneck, but processing can be important to reduce
the amount of communication.
SB: Point is that the real problem is a distributed one, not a
centralized one.
Johannes: Communication dominates power cost. Battery technology is
not scaling. Therefore reducing communication is important.
SB: But problem isn't sensor bandwidth. It's big app bandwidth.
They'd like to see a big federated system. Right now they stage the
data statically, but they'd like to do it dynamically.
Mehul: Do the stations move?
SB: Of course. And that makes the problem hard because there's less
bandwidth.
Stan: What about homeland security? They seem isomorphic.
SB: We could try to make these apps more politically correct. Homeland sec.
might be more correct.
Another sensor application:
Environmental monitoring. E.g. "fish pills" -- to monitor mercury
level in the water. "Whistling dixie".
Once a minute is fine, or once every ten minutes if fine. SB thinks
low bandwidth apps are easy, which means that in the DBMS there's not
a lot of hard processing.
Stan: Want to do signal processing. The amount of processing per
sample could be high.
Franklin: Can existing systems support these signal processing ops?
There may be interesting new operators.
SB: That's an argument for doing this in DB2, not an argument for
building a totally new system.
Another app: electronic property sticker. MIT library is serious
about putting a passive sensor on every book. Interesting in losing
books that get put in the wrong location, detect books that are being
stolen. "Whistling dixie". Low data rate.
Sam: What if you have millions of these?
Jennifer: What's the data rate in the military app?
SB: A few thousand sensors, a few samples per second. Not high data
rates, but the processing is hard.
SB: Best killer app. Gillette. Bought 10 million "dimes" (passive
electronic property stickers) to put on retail bundles. For theft?
For supply chain management. Why? Presumably razor blades are a item
that walks out of the supermarket.
Dewitt: For auto checkout?
SB: Yeah, fairly quickly, there will be a basestation on every
shopping cart. It'll track the items in the cart, tell you when you
pass items you like to buy, etc. Will allow perfect supply chain
management.
"Dime based" systems its hard to come up with things that look really
hard. Seems like military apps are the best bet.
On to Dennis Shasha (NYU).
Working on finance. Online pattern discovery is data streams.
Sensor-less. Pars trading in stock trading (find highly correlated
pairs in nlogn time). Sensor less (RTE).
Sensor full app: Gamma ray detection in astrophysics. Burst detection
over a large number of window sizes in almost linear time. About 1TB
of data per day, trying to find supernovas -- gamma ray bursts. Want
to do it in real time so they can tell people to point their
satellites at the burst.
App 1: Pairs trading Stock price streams on the NYSE. Looking for
pairs of stocks that have been highly correlated over the past three
hours. Here they are only interested in stocks that have been
tracking each other. If two stocks are tracking each other and one
goes out of sync with the other, and there's not reason for that to
happen, they want to short one stock and buy the other. A form of
arbitrage.
Have to know which stocks are correlated. And these correlations can
change.
Need sliding windows, and these correlations can change. Given tens
of thousands of high speed time series, data streams to detect high
value correlation, including synchronized and time-lagged over sliding
windows in real time.
High update frequencies. Time is of the essence, since by the time a
stock hits the news wire, the stock has already moved. Need to be the
first guy on the scene.
Related issue: talking about volumes. Similar to gamma ray apps.
Stat stream: stream synoptic data "Basic window" the computation must
finish by the time the next window comes around. Window sizes are
about 5 minutes. Doing this for 10k streams on a single PC.
Application 2: elastic burst detection.
Discover time intervals with an unusually large number of gamma ray
bursts. Looking for "showers" -- they sky may be above noise threshold
for a few ms, a few hours, or even a few days. The kind of window
we're looking for can vary a whole lot. This'd be easy for fixed
windows, but hard for variable (any) sized windows. Need to do this
in one pass (which makes it a streaming app.)
Burst detection uses a wavelet thing. Doesn't matter too much, but
this isn't a standard SPJA problem.
Near linear time algorithm for doing this. If there are lots of
events, may have to backtrack a little, which can make the complexity
a little worse. Rarely lots of events.
SB: Trouble with these apps is that they're over recent history only.
Not trying to correlate stocks that were correlated four days ago with
stocks for today. Problem is to find stocks correlated today. Could
do this with a main-memory resident algorithm. Doesn't seem like
there isn't much a historical component in stock market analysis.
Shasha: Right about this app. But there are examples where you need
history -- e.g. don't want to be fooled by correlations that didn't
pan out in the past.
Hari: Does that mean that the only hard apps are those that have a
historical component.
SB: Yeah, historical makes it hard.
Maier: If you can bound the data, it's easy.
Hari: But can conventional database systems do these queries, even if
they're not historical?
SB: But these apps just look like reading in some data and running a
one-pass mining algorithm over them.
Shasha: But there are other components, e.g. comparing correlations
with news articles.
Alex: Have sensors in cars. Every few seconds you have a million
vehicles reporting where they are. Need to incorporate that data
together to route traffic, set speeds, etc.
Maier: Got sensors going into a model. Only a few sensors but
gigabytes of data flowing out of these.
Ted Johnson:
Network monitoring. What is the challenge? Very high data rates.
Optical linkes -- gigabytes /sec and higher in OC192. Millions of
packets/sec.
Complex queries. Extract dynamic substreams (flows, TCP session, etc.)
Many sequence numbers, types of sequencing. Want to do flow level
analysis. Looks like simulations of network protocols (e.g. IP
defragmentation. etc.)
Multiple data sources: SNMP, netflow, BGP, packet sniffers, router
tables, etc. Many layer protocols: multimedia, NPN etc. Dozens to
hundreds of heterogeneous deployments -- would like to do correlations
across sites.
Every bad thing happens (always errors, malformed packets. etc).
Often times these bad things are what you're looking for.
Must overcome a prejudice that database technology is too slow and
rigid for network monitoring.
Many examples of attempts to load data into a DBMS and process it.
Too much data, and queries are too complicated.
Years long lead time for core deployment.
SB: Is this real time, or post mortem?
Ted: Both, need real time to get to the point where you can do post
mortem.
Gigascope: Gigascope is a lightweight and flexible stream database
specialized for network monitoring.
Current deployments: link to Internet (100Mbit/sec). Large on-line
gaming site (Gigabit ethernet.)
Developed in close cooperation with network analysis. (So the
terminology will seem weird.)
Queries:
Problem -- protocol problem. Trying to determine where the problem
is. Want to collect information about packets, and then run it
through a state machine to model packet delay, loss,etc.
Input: Gigabit ethernet. Output: select clause.
select timestamp, sourceIP, destIP, source_port,
dest_port,len,total_length, gp_header from GAMEPROTOCOL where
sample_hash[50,sourceip,destip] and protocol=17 and offset = 0
select tb,lowIP, highIP, protocol, SUM(len), COUNT(*)
from IPV3 where
sample_rand[75]
group by protocol_time_60 as tb UMIN(sourceIP,destIP)
as lowIP UMAX(sourceIP,destIP) as highIP
This is running in gigascope. Tapped into the router.
Two kinds of sampling going on here. In the first query, want to
sample packets from a specific set of users (first 5% of hashes in
this case). Second one is just a random sample of 7.5% of the data.
Speed isn't important. Packet loss is. Need to look at all of the
packets.
Approx 1M packets per second during peak usage. Drops are bad, since
if we drop some of the packets we'll bias results.
More queries:
select tb*60, MIN(timestamp), MAX(timestamp), destIP, dest_port from
TCP where ipversion=4 and offset=0 and protcol=6 and ... group by ...
seelct tb, localip, peerid, asid, count(*), sum(len) from IDataProtcol
where ipversion=4 and (dest_port=25 or source_port=25) group by time
60 as tb destIP as localip getlpmid(sourceIP,'peeridtbl') as peerid
getlpmid(sourceIP,'asnidtbl') as asid;
getlpmid -- prefix matching external function. Needed this early,
since fast prefix matching is essential.
Second application: intrusion detection.
Current technology (e.g. snort). Low speed only Cumbersome
specification language. Can't trigger alarms by recording from
aggregates (e.g. recent ping attack on root DNS).
Needed FAST trigger processing fast alarm to network manager (not
challenging) Run query Q on the next 500 packets (challenging) Run
query Q in the previous 500 to next 500 (very hard)
Distributed network monitoring:
Like to have a monitor at every backbone router. Need wide ranging
information to determine network health. Today -- 500gbytes of
netflow data (already highly aggregated) Monitor at every customer
router? Complex distributed queries -- e.g. to diagnose distributed
network attacks Quality of service becomes important because highly
aggregated records are more important than others.
What's interesting?
High data rates. Complex queries -- language constructs to capture
substreams. Extensive support for user defined functions. Support
user defined operators.
Have multiple data sources. Need collaborations across disciplines.
Accept that you can't do everything -- some things are expressible in
SQL.
SB:
Take away -- good apps:
Military
Traffic monitoring
Financial apps -- interesting if its non historical
Networking monitoring
Jennifer:
Requirements of a good app:
high data rates
complex (e.g. historical) queries
long running queries
need for real time responses
desire to not just hard code things
Carlo:
Are these really the only interesting things?
Jennifer:
Of course not. But to justify our existence, these are the apps were
after.
Ted: Can do a lot of this with custom programs. But there's a huge
advantage to having a reusable framework.
Franklin:
A large number of queries probably makes a good app.
Stan:
You really mean a large number of dynamic queries (coming and going)!
Nesime: Might be interesting where there is variability in rates.
You'd like to not have to block for a long period of time.
Dewitt: Network apps seem like a big one. But the network people are
awfully skeptical. Unless you're ATT, do you really have access to
the kinds of data that you need? Traffic apps is good, but there
doesn't seem to be that many queries. It's silly to try to be
politically correct w.r.t. military stuff -- we should be going after
that.
Would the networking community want help from the database community?
Ted: Only if you can build a system that is easy and actually works.
SB: The military guys are willing to spend an arbitrary amount of time
helping us. Is ATT willing to give us data and queries?
Ted: We'll never give you data.
Hari: It's clear that Sprint and ATT have this data. But you don't
have to be one of these guys to get this data. A problem that MIT has
been going after for a few years -- tracking of outages. It's clear
that outages happen, but the providers won't tell you what happens.
Goal of project is to deploy 1000 nodes throughout the internet and
use that to track losses. Would like to correlate n^2 paths between
these nodes and routing messages. Would like to correlate outages
with types of routing messages. Can predict that an outage is about
to happen by looking for certain patterns of data that occur before a
failure.
Why don't we use databases? We want to run queries, but we can't get
databases to do want we want. JMH couldn't fix our queries for us.
There's a lot of computation we want to apply. Need these apps to be
distributed, because we don't have the bandwidth. But what we should
do is get students at ATT and Sprint doing this.
SB: Can we get a schema and 20 network monitoring queries?
Jennifer: We already have them on the web site.
Hari: Just a summary -- yes NW people do care about DB people.
Dewitt: But can we do anything useful?
Hari: Yes, but it has to be distributed.
SB: We're done.