�ݺ�ߣ

Literature Review of Stream Data
Processing
Your name: Nabilahmed Patel
Email: nabilpatel11@gmail.com

References
 A. Gilani.Design And Implementation Of Stream Operators, Query Instantiator And
Stream BUFFER Manager. December 2003,
http://itlab.uta.edu/students/alumni/MS/Altaf_Gilani/AGil_MS2003.pdf.
 B. K. Kendai. Runtime Optimization And Load Shedding In Mavstream: Design
And Implementation. December 2006.
http://itlab.uta.edu/students/alumni/MS/Balakumar_Kendai/BKen_MS2006.pdf.
Sharma Chakravarthy 2

MavStream
 MavStream is Data Stream Management System (DSMS) for processing continuous
query over stream.
 It is modelled as a client-server architecture.
 The client accepts input (query) from the user and sends it to the server.
 The server processes the input and creates server speciﬁc data structures that will be
used while the continuous query is being processed.
 The output of query is given back to the client.

MavStream Architecture

MavStream Client
 Web-enabled GUI.
 Accepts queries and stream definition from users.
 Generates an ASCII file of the user input.
 CQs are defined in file by giving stream operator and information about instantiating them.
 To create query tree, it is required that user give association between operators.
 Server takes in the text input.
 Communication between client and server is command driven and protocol oriented.

MavStream Server
 TCP Server.
 Responsible for executing users requests and producing desired output.
 Integration and interaction of modules such as input processor, instantiator, operators, buffer manager
and scheduler.
 Some of the commands supported by the server are given below:
 Register a stream
 Receive a query plan object
 Start a query
 Send all stream information to the client
 Stop a query

Input Processor
 Generates Query Plan Object by processing text input.
 It is a sequence of operator nodes where every node describes an operator completely.
 Data structure called “Operator Data” is used to store operator definition.
 The “Operator Data” is wrapped in an “Operator Node” that has references to the parent
and child operators.
 The entire query plan object is accessed using a reference of the Operator Node for the root
operator.

Input Processor(Cont.)
 As data flows from leaves to root , query tree is traversed in bottom-up manner.
 On visiting each node input processor calls the instantiator module to instantiate the
operators.
 After instantiating the operators, the query tree is processed to create operator paths,
segments and simplified segments.
 Computes the processing capacity of paths and memory release capacity and sorts them.
 Processes the QoS parameters and stores them in the appropriate data structures to be used
by system monitor.

Instantiator
 Initialize and instantiate the stream operators and their associated buffers.
 It creates an instance of each needed operator and initializes it on reading Operator Node
data.
 It extracts the information from the operator node and converts it into the form required by
each operator.
 It then associated buffers with desired parameters to operators.
 It also associates a scheduler with the operator to facilitate communication for scheduling.
 Instantiator does not start the operator, it only does all the necessary initialization.

Scheduler
 In MavStream scheduling is done at operator level.
 Operators are scheduled on based of their state and priority.
 The scheduler maintains a ready queue, which decides the order in which operators are
scheduled.
 This queue is initially populated by the server.
 Operators must be in a ready state in order to get scheduled.
 Operator goes through a number of states while it is being scheduled.

Scheduler
 Scheduling Strategies Supported by MavStream:
 Round-Robin: all the operators are assigned the same priority(time quantum).
 Weighted Round-Robin: different time quanta are assigned to different operators based on their
requirements.
 Path capacity scheduling: schedules the operator path which has the maximum processing
capacity.
 Segment scheduling: Schedules the segment which has the maximum memory release capacity.
 Simplified segment scheduling: same as segment scheduling except the construction of segment is
different.

Scheduler
 Master Scheduler:
 The execution of all schedulers is controlled by the master scheduler.
 Master scheduler allocates time quantum to each scheduler to execute.
 At any instance of time only one scheduler is allowed to run by the master scheduler.
 It also provides an interface to add and remove queries from the ready queue of the
scheduler and to change the scheduling strategy of queries.

Feeder
 It has been developed to feed the tuples of streams to buffers of leaf operators.
 If many streams are combined and is fed as one stream then split condition should
be specified by user using “split” operator supported by MavStream.
 Each stream is fed using different thread.
 As there is no facility of direct stream from sensors, feeder reads the data from flat
files which contain synthetically generated data.
 The mean rate of feeder is changed over time and pauses to the feeding has also
been introduced to simulate bursty nature of streams.
 The characteristics of feeding can be specified by a configuration file.

Operators
 The operators are designed to handle long running queries producing results continuously
and incrementally.
 To deal with blocking operators (aggregates and join), operators are designed using window
concept.
 During the life span of an operator, it can either be in ready, running, suspended or stop
state .
 MavStream supports the following operators: split, select, project , join (hash and nested
versions), group by and various aggregate operators (sum, average, max, min, count).

Buffer Management
 To provide a mechanism to handle the mismatch between input rates and the processing
capacity by using available memory.
 As we have limited main memory, if incoming tuples exceed the upper limit, they have to
be either discarded or stored in secondary storage.
 An interface is provided to store tuples either in main memory buffers or on secondary
storage (using a configuration option) and retrieve the tuple stored in secondary storage.
 The management of main memory buffers and secondary storage for tuples is completely
handled by the buffer manager.

Runtime Optimizer
 The primary goal of the runtime optimizer is to monitor QoS measures to make sure that
user speciﬁed QoS values are met to the best extent possible.
 Based on the monitoring, system choose the best (or optimal) scheduling strategy for a
query.
 In MavStream Runtime Optimizer consists of a System Monitor, which monitors the values
of QoS measures for a query and a Decision Maker, which chooses the best scheduling
strategy for a query and controls the load shedders.
 If the scheduling strategy being used succeeds in meeting the QoS requirements of a query,
runtime optimizer does not take any actions for that query.

Runtime Optimizer (cont.)
 Alternative Design: Decision Making based on input rate of streams
 QoS measures of a query depends on the scheduling strategy chosen for that query and
arrival rate of input streams.
 The processing capacity of any system is ﬁxed.
 As the input rates of streams are bursty, any change in the arrival rates of stream can
potentially trigger a change in scheduling strategy of queries depending on that stream.
 Such an approach would also be ignorant of the actual QoS requirements of the query
and may end up taking decisions to change scheduling strategy when it may not be
necessary.
 Hence MavStream utilizes a technique for choosing strategies using the feedback
obtained by monitoring actual QoS measures and a static table called decision table.

�ݺ�ߣ

CSE-5393 _Mid_Nabilahmed_Patel

Recommended

More Related Content

What's hot (8)

Viewers also liked (20)

Similar to CSE-5393 _Mid_Nabilahmed_Patel (20)

CSE-5393 _Mid_Nabilahmed_Patel