[NEW EXAMPLE] ZooKeeper - Trie

[ainzzorl]

General

• Project name: ZooKeeper
• Example name: Trie implementation
• Project home page: https://github.com/apache/zookeeper
• Programming language(s): Java
• Frameworks, libraries used: N/A

Description

ZooKeeper is a centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services.

ZooKeeper operates with znodes - data objects organized hierarchically as in file systems. In some cases it needs to find the longest stored prefix for a given path. For this, it uses the Trie data structure.

Links

https://github.com/apache/zookeeper/blob/e642a325b91ab829aefa47708c7b4b45811d2d23/zookeeper-server/src/main/java/org/apache/zookeeper/common/PathTrie.java

https://github.com/apache/zookeeper/blob/e642a325b91ab829aefa47708c7b4b45811d2d23/zookeeper-server/src/test/java/org/apache/zookeeper/common/PathTrieTest.java

What makes it interesting

• Trie is a popular data structure, very frequently used in job interview problems :-)

Related work

N/A

Other

N/A

[ainzzorl]

Draft: https://github.com/ainzzorl/goodcode/blob/4f5b4e11c240077fcfbe8a6223e199178eedf292/articles/zookeeper-trie.md

[ainzzorl]

Before publishing:

• Link to znode https://zookeeper.apache.org/doc/r3.1.2/zookeeperProgrammers.html#sc_zkDataModel_znodes
• Find links to other Trie implementations.
• Observation about locking.
• Observation about Deque.

[ainzzorl]

Updated and marked as PUBLISHED. I haven't found another Trie implementation in big open source projects.