Accurate counting algorithmforhigh-speed parallel applications

摘要

Statistical counter offers the appeal of an efficient and scalable counting mechanism on multi-core architectures where parallelism has been increasing sharply. Statistical counter has been widely used in practice (eg, in high-end network devices to count the number of packets received) despite the truth that it can only provide weak consistency guarantee on the counting results it returns, that is, statistical counter could miscount and the returned results may be inaccurate. As hardware and its parallelism advances, the miscount issue has raised concerns in both industry and academy. This paper is motivated by this real-world miscount issue that we were facing when building a high-speed intrusion detection system on a commercial multi-core server with 40Gbps NICs. To tackle the problem, we first systematically analyze the miscount issue and quantify themiscounts in counting results. Then, we present a novel counting algorithm that (1) is competitive to statistical counter in performance on multi-core architectures and (2) provides strong consistency guarantee on counting results returned. Experiments show that it takes the new counting algorithm 10ns and 1,500ns to perform an update and a read operation, respectively. Moreover, the counting results returned are accurate.