For search Ads retrieval in e-Commerce, when a customer inputs a query, from tens of millions of Ads products, the system needs to quickly retrieve a limited number of candidates that can not only meet the customer's search intension but also have high conversion probability. This constructs challenges for both retrieval efficiency and retrieval quality on the perspective of relevance and engagement. To alleviate these challenges, traditional solutions usually adopt a cascading architecture including the recall, pre-ranking, ranking and re-ranking stages. These methods are helpful, however, due to the hard limit of online customer request processing latency, only a small ratio of relevant candidates can be retrieved and the quality of pre-ranking is limited. Different from the online cascading architecture, we propose an effective offline-based solution: for each query, we first use multi-path recall, such as BERT-based embedding to retrieve a much larger number of candidates. Then, a carefully designed LLM-based relevance model is used to filter out the irrelevant candidates. Finally, we use powerful DNN models to rank the left candidates, and only a small number of best candidates are passed to the online system for real-time usage. In the online system, we keep a single ranking stage and use the most powerful models only. Compared to the online cascading architecture, our proposed method can not only largely reduce the online system's overhead and latency, but also significantly improve the overall quality. Real world A/B test experiments on Coupang search Ads show that this solution can improve the revenue, GMV, and advertiser ROAS by 5.79%, 11.37%, and 6.69%, respectively. The relevance defect ratio can be reduced by 68%. Meanwhile, the customer request processing P99 latency can reduced by 21%, when the online serving cluster's hardware cost is reduced by 52%.

Boolean expression matching plays an important role in many applications. However, existing solutions still show efficiency and scalability limitations. For example, existing solutions often exhibit degraded performance when applied to high-dimensional and diverse workloads, and existing algorithms rarely consider supporting concurrent matching and index updating under multicore environments. To overcome these limitations, in this article, we first design the PS-Tree data structure to efficiently index Boolean expressions in one dimension. By dividing predicates into disjoint predicate spaces, PS-Tree achieves high matching performance and good expressiveness. Based on the PS-Tree , we propose a Boolean expression matching algorithm called PSTDynamic . By dynamically adjusting the index and efficiently filtering out a large proportion of unmatching expressions, PSTDynamic achieves high matching performance under high-dimensional and diverse workloads. For multicore environment, we further extend the PSTDynamic algorithm to PSTParallel to achieve scalability with lower matching latency and higher matching throughput. We run experiments on both synthetic and real-world datasets. The experiments verify that our proposed algorithms show high efficiency and parallelism. Moreover, they also achieve fast index construction and a small memory footprint. Comprehensive experiments show that our solutions drastically outperform state-of-the-art methods.

Streaming graph computation has been widely applied in many fields, e.g., social network analysis and online product recommendation. However, existing streaming graph computation approaches still present limitations on accuracy and efficiency. To improve the accuracy, some distributed systems use the sequential graph update method based on an incremental computation model. However, these systems cannot handle the dynamic graph update concurrently. The speculation-based parallel updating model can parallelize the graph computation, however, it is restricted due to ignoring the original messages when updating a graph. Streaming graph computation usually requires high accuracy and low latency. As such, it is challenging to utilize incremental computation while simultaneously supplying concurrent processing guarantees.To overcome these challenges, in this paper, we first analyze a number of classical graph algorithms and summarize three principles that graph algorithms should satisfy in streaming scenarios. Based on these principles, we propose GraphFlow, a streaming graph computation model. GraphFlow achieves fast and accurate computation by utilizing incremental state update and propagation. To reduce the impact of concurrent update conflicts, GraphFlow provides a fine-grained lock based parallel update strategy. We implement GraphFlow framework and evaluate its performance and concurrent update conflict probability on real-world datasets. Meanwhile, we compare GraphFlow with two existing representative graph processing systems. Experimental results show GraphFlow achieves low latency and outperforms other graph processing systems given large datasets.

Microservice architectures backed by container technology have been widely used in many real-world cloud-native applications. By enabling customers to manage their services and configurations in the cloud in a centralized, externalized, and dynamic manner, efficient service and configuration management plays a fundamental role in building cloud-native service-centric applications. The number of containers in cloud data centers continues to increase. For example, in the Alibaba Cloud, the number of containers reached hundreds of thousands by 2023 and is expected to reach several million soon. At this scale, existing service and configuration management solutions have limited efficiency, scalability and robustness. Other related approaches, such as message bus systems and publish/subscribe (pub/sub for short) systems, also do not work well for large-scale service and configuration management in the cloud, as their designs are more general purpose directed. To overcome these limitations, we design a system, called Ripple, that uniquely combines several existing and some novel features such as consistent hashing-based workload distribution, dynamic destination list-based and client-assisted message delivery, incremental update, and adaptive load balancing. Approaches exhibiting these features have not been well investigated in the domain of service and configuration management. We compare our proposed solution with existing academic and industrial approaches. The experiments show that our solution greatly outperforms its counterparts. For example, for the same workload, when Ripple is used, the average message delivery latency and network bandwidth consumption can be reduced by up to 77% and 93%, respectively.

Efficiently evaluating a large number of arbitrary Boolean expressions is needed in many applications such as advertising exchanges, complex event processing, and publish/subscribe systems. However, most solutions can support only conjunctive Boolean expression matching. The limited number of solutions that can directly work on arbitrary Boolean expressions present performance and flexibility limitations. Moreover, normalizing arbitrary Boolean expressions into conjunctive forms and then using existing methods for evaluating such expressions is not effective because of the potential exponential increase in the size of the expressions. Therefore, we propose the A-Tree data structure to efficiently index arbitrary Boolean expressions. A-Tree is a multirooted tree, in which predicates and subexpressions from different arbitrary Boolean expressions are aggregated and shared. A-Tree employs dynamic self-adjustment policies to adapt itself as the workload changes. Moreover, A-Tree adopts different event matching optimizations. Our comprehensive experiments show that A-Tree-based matching outperforms existing arbitrary Boolean expression matching algorithms in terms of memory use, matching time, and index construction time by up to 71%, 99% and 75%, respectively. Even on conjunctive expression workloads, A-Tree achieves a lower matching time than state-of-the-art conjunctive expression matching algorithms.

Boolean expression matching is an important function for many applications. However, existing solutions still suffer from limitations when applied to high-dimensional and dense workloads. To overcome these limitations, in this paper, we design a data structure called PS-Tree that can efficiently index subscriptions in one dimension. By dividing predicates into disjoint predicate spaces, PS-Tree achieves high matching performance and good expressiveness. Based on PS-Tree, we first propose a Boolean expression matching algorithm PSTBloom. By efficiently filtering out a large proportion of unmatching subscriptions, PSTBloom achieves high matching performance, especially for high-dimensional workloads. PSTBloom also achieves fast index construction and a small memory footprint. Compared with state-of-the-art methods, comprehensive experiments show that PSTBloom reduces matching time, index construction time and memory usage by up to 84%, 78% and 94%, respectively. Although PSTBloom is effective for many workload distributions, dense workloads represent new challenges to PSTBloom and other algorithms. To effectively handle dense workloads, we further propose the PSTHash algorithm, which divides subscriptions into disjoint multidimensional predicate spaces. This organization prunes partially matching subscriptions efficiently. Comprehensive experiments on both synthetic and real-world datasets show that PSTHash improves the matching performance by up to 92% for dense workloads.

Despite suffering from inefficiency and flexibility limitations, the filter-based routing (FBR) algorithm is widely used in content-based publish/subscribe (pub/sub) systems. To address its limitations, we propose a dynamic destination-based routing algorithm called D-DBR, which decomposes pub/sub into two independent parts: Content-based matching and destination based multicasting. D-DBR exhibits low event matching cost and high efficiency, flexibility, and robustness for event routing in small-scale overlays. To improve its scalability to large-scale overlays, we further extend D-DBR to a new routing algorithm called MERC. MERC divides the overlay into interconnected clusters and applies content-based and destination-based mechanisms to route events inter- and intra-cluster, respectively. We implemented all algorithms in the PADRES pub/sub system. Experimental results show that our algorithms outperform the FBR algorithm.

Despite suffering from inefficiency and flexibility limitations, the filter-based routing (FBR) algorithm is widely used in content-based publish/subscribe (pub/sub) systems. To address its limitations, we propose a dynamic destination-based routing algorithm called D-DBR, which decomposes pub/sub into two independent parts: Content-based matching and destination-based multicasting. D-DBR exhibits low event matching cost and high efficiency, flexibility, and robustness for event routing in small scale overlays. To boost scalability, we further complement D-DBR with a new routing algorithm called MERC. MERC divides the overlay into interconnected clusters and applies content-based and destination-based mechanisms to route events inter- and intra-cluster, respectively. We implemented all algorithms in the PADRES pub/sub system. Experimental results show that our algorithms outperform FBR in terms of improving event dissemination throughput by up to 700% and reducing the end-to-end latency by up to 55%.

In-memory data grid (IMDG) is a novel data processing middleware for Internetware. It provides higher scalability and performance compared with traditional rational database. However, because the data stored in IMDG must follow the key/value data model, new challenges have been proposed. One important aspect is that IMDG does not support standard data accessing languages such as JPA and SQL, and application developers must design their programs according to the peculiarities of an IMDG product. This results in complex and error-prone code, especially for the programmers who have no deep understanding of IMDG. In this paper, we propose a data accessing reference architecture for IMDG and a methodology to design and implement its data accessing layer. In this methodology, data accessing engine construction, data model designation and join operation supporting are presented. Moreover, following this methodology, we develop and implement a JPA compatible data accessing engine for Hazelcast as a case study, which proves the feasibility of our approach.