Memory optimizations for distributed stream-based applications

Distributed stream-based applications manage large quantities of data and, therefore, have large memory requirements. On the other hand, this class of applications has specific properties and exhibits unique production and consumption patterns that set these applications apart from general-purpose applications. This dissertation examines possible ways to harness the unique characteristics of stream-based applications to assist in creating efficient memory management schemes. In particular, this dissertation looks at the memory reclamation problem. It takes advantage of special traits of streaming applications to extend the definition of the garbage collection problem for those applications and include not only data items that are not "reachable" but also data items that have no effect on the final outcome of the application. Streaming applications typically fully process only a portion of the data, and resources directed towards the remaining data items, that is data items that do not affect the final outcome, can be viewed as wasted resources that should be minimized. Two complementary approaches are suggested: (1) Garbage Identification. (2) Adaptive Resource Utilization. Garbage Identification is concerned with an analysis of dynamic data dependencies to infer those items that the application is no longer going to access. Several garbage identification algorithms are developed and examined. Each one of the algorithms uses a set of application properties (possibly distinct from one another) to reduce the memory consumption of the application: (1) The Dead timestamps based Garbage Collector algorithm (DGC) combines garbage identification and computation elimination. The DGC algorithm locally identifies dead items, that is, items that are of no interest to any of the application threads and thus, will not be requested in the future. This information is then propagated to neighboring nodes. (2) Additional GC algorithms for streaming applications (Keep Latest 'n Unseen, Propagation of Dead Sets, Out-of-Band Propagation of Guarantees, and Out-of-Band Propagation of Dead Sets) are also presented. These algorithms enable the runtime system to achieve a tighter control on memory used by streaming applications. They explore the potential benefits of providing more information to the runtime system either directly from the application writer or by disseminating information more efficiently within the runtime system. The Adaptive Resource Utilization (ARU) algorithm predicts the capacity of the system to process data items. It attempts to adjust the rate new data items are introduced to the application in order to match the processing capacity of system. In that sense, ARU extends the definition of wasted data items to include those items that would be identified as garbage had they been produced. The ARU algorithm infers the capacity of the system by analyzing the dynamic relationships between the production and consumption of data items. It then adjusts the data generation accordingly. Thus, the ARU algorithm makes local capacity decisions based on global information. This dissertation also presents a methodology to explore the design space of distributed software environments. The methodology involves expressing the attributes of the design space as "what-if" scenarios. The scenarios are then simulated and evaluated for their effect on the system's performance. The use of "what-if" scenarios makes it possible to define and express an ideal system. This ideal system serves as a reference point that helps in assessing how well implemented or simulated systems perform. The simulations are dependent on accurate measurements of events that are performed in a distributed environment. To support the simulations, a distributed and cycle-accurate event-logging measurement infrastructure is presented. In this dissertation, the methodology and the measurement infrastructure are used to assess the performance of garbage identification algorithms. An Ideal Garbage Collector is defined and used as a reference point to assess implemented (REF, TGC, and DGC) and proposed (OBPG, KLnU, PDS, and OBPDS) garbage identification algorithms. The proposed garbage identification algorithms are simulated and the best garbage collector is implemented. This work also serves as a case study that evaluates the validity of this methodology. The results indicate that the garbage identification algorithms that achieve a low memory footprint (close to that of an ideal garbage collector) perform their garbage identification decisions locally; however, they base these decisions on best-effort global information obtained from other components of the distributed application. The ARU algorithm is found to be as effective as the most successful garbage identification algorithm in reducing the memory footprint of stream-based applications, thus confirming the previous observation that using global information to perform local decisions is fundamental in reducing memory consumption of stream-based applications.