In modern data-driven ecosystems, Extract, Transform, Load (ETL) flows serve as the backbone of data integration pipelines. These flows facilitate the seamless movement of data across disparate systems and formats, streamlining processes that range from data acquisition to preparation for analysis. However, the pervasive use of ETL flows introduces a pressing challenge-how to bound the maintenance cost of an ever-expanding number of flows. In this paper, we describe an end-to-end prototype for ETL flow refactoring, aimed at reducing the maintenance cost, which keeps the human in the loop for refactoring decisions. Our prototype adopts and significantly extends the gSpan Frequent Subgraph Mining (FSM) algorithm to apply it to real-world ETL use cases in the context of the IBM DataStage™ data integration tool. We report on real customer workloads, share their statistics and evaluate the performance of our prototype. We found potential for up to 32% maintenance cost reduction on the use cases we analyzed after removing duplicate flows. We also share an anonymized version of the workloads with the research community.

Measurement capabilities are fundamental for a variety of network applications. Typically, recent data items are more relevant than old ones, a notion we can capture through a sliding window abstraction. These capabilities require a large number of counters in order to monitor the traffic of all network flows. However, SRAM memories are too small to contain these counters. Previous works suggested replacing counters with small estimators, trading accuracy for reduced space. But these estimators only focus on the counters’ size, whereas often flow ids consume more space than their respective counters. In this work, we present the CELL algorithm that combines estimators with efficient flow representation for superior memory reduction.We also extend CELL to the sliding window model, which prioritizes the recent data, by presenting two variants named RAND-CELL and SHIFT-CELL. We formally analyze the error and memory consumption of our algorithms and compare their performance against competing approaches using real-world Internet traces. These measurements exhibit the benefits of our work and show that CELL consumes at least 30% less space than the best-known alternative. The code is available in open source.

Sketches maintain compact approximate statistics about streams of data, thereby enabling quickly answering queries regarding the data stream without having to reprocess it. Often, recent data is considered more important than older one, which is captured by the sliding window model. In distributed settings, where parts of the stream are seen by different, potentially geographically distributed components of the system, it makes sense to collect global statistics about the stream, but in a decentralized manner. Further, in order to ensure availability, scalability, and good performance, it is appealing to treat sketches as a CRDT data-type. In this work we introduce the notion of sliding window CRDT sketches. We then present the CRDT All Timestamps (aka CRDT-AT) and CRDT Last Timestamp (aka CRDT-LT) algorithms for implementing such sketches and analyze them. We also study the performance of CRDT-AT and CRDT-LT using real workloads, to establish their viability.

Estimators reduce the memory footprint of maintaining network statistics, while keeping the estimation error of each flow proportional to its size. This is unlike sketches and other approximate algorithms that only guarantee an error proportional to the entire stream size. In this work we present the CELL algorithm that combines estimators with efficient flow representation to obtain superior memory reduction compared to the state of the art.

In applications such as sharded data processing systems, data flow programming and load sharing applications, multiple concurrent data producers are feeding requests into the same data consumer. This can be naturally realized through concurrent queues, where each consumer pulls its tasks from its dedicated queue. For scalability, wait-free queues are often preferred over lock based structures. The vast majority of wait-free queue implementations, and even lock-free ones, support the multi-producer multi-consumer model. Yet, this comes at a premium, since implementing wait-free multi-producer multi-consumer queues requires utilizing complex helper data structures. The latter increases the memory consumption of such queues and limits their performance and scalability. Additionally, many such designs employ (hardware) cache unfriendly memory access patterns. In this work we study the implementation of wait-free multi-producer single-consumer queues. Specifically, we propose Jiffy, an efficient memory frugal novel wait-free multi-producer single-consumer queue and formally prove its correctness. We then compare the performance and memory requirements of Jiffy with other state of the art lock-free and wait-free queues. We show that indeed Jiffy can maintain good performance with up to 128 threads, delivers better throughput than other constructions we compared against, and consumes less memory.

Effective management policies for datastore caches should provide good hit-ratios on a large number of workloads, operate in constant time, and maintain a small amount of metadata. In certain workloads, cache stability is an important metric, as limiting the number of cache updates can improve power consumption, increase the life expectancy of flash memories, and conserve network bandwidth in distributed settings. This paper introduces TinyCache, a compact table based management policy for datastore caches. TinyCache achieves similar hit ratio compared to the leading alternatives while operating in worst case constant time and only accessing a fixed sized memory word for each update. TinyCache encodes its metadata in a memory optimal manner and reduces the number of cache updates by up to X6 compared to state of the art.