KDADK-MMPM

KDADK is a high-performance data analysis development kit developed by Huawei. Million-rule Multi-Pattern Matcher (MMPM) is integrated into KDADK and can effectively process matching based on tens of millions of rules.

Rule matching is a fundamental requirement in intelligent data analysis scenarios. However, massive-scale rule matching is a big challenge. Rule matching libraries, such as Hyperscan, experience performance degradation when processing over 100,000 rules. In such cases, KDADK-MMPM expresses itself as a dedicated algorithm library essential for massive-scale rule matching.

MMPM provides different algorithms for two different scenarios. For rule sets containing hundreds of thousands of variable-length rules, it employs an Aho-Corasick (AC) Trie-based unanchored multi-pattern matching algorithm. For rule sets with tens of millions of fixed-length rules, it utilizes a Hash-based anchored multi-pattern matching algorithm.

MMPM operates in two phases: rule preprocessing and rule matching.

MMPM uses a two-level hash structure to maintain rules in an ultra-large rule set, improving the search speed without deteriorating the efficiency of adding, deleting, and modifying rules.

MMPM uses the following key technologies: AC Trie array-based table lookup optimization, AC automaton, multi-level hashing, parallelized hashing, and vectorized collision check.

MMPM is suitable for scenarios such as network security data distribution, fine-grained data distribution for carriers, data distribution for public security and technical investigation, IDP, WAF, and foundation model application firewalls.