Automated operator placement in distributed Data Stream Management Systems subject to user constraints

摘要

Traditional distributed Data Stream Management Systems assign query operators to sites by optimizing for some criterion such as query throughput, or network delay. The work presented in this paper begins to augment this traditional operator placement technique by allowing the user issuing a continuous query to specify a variety of constraints — including collocation, upstream/downstream, and tag- or attribute-based constraints — controlling operator placement within the query network. Given a set of constraints, operators, and sites; four strategies are presented for optimizing the operator placement. An optimal brute force algorithm is presented first for smaller cases, followed by linear programming, constraint satisfaction, and local search strategies. The four methods are compared for speed, accuracy, and efficiency, with constraint satisfaction performing the best, and allowing assignments to be adapted on the fly by the DDSMS.