| 摘要 |
The present invention provides a method, system, and computer program product for reliably and efficiently serializing access to data structures (i.e. updates and retrievals) without requiring searchers to use locks. The disclosed technique ensures that the contents of the data structure remain valid during access operations, yet does not require searchers to perform compute-intensive comparison operations to determine validity. Two trees are used at all times. Searches proceed against a first tree, while the second tree is used for performing updates. The steps required to carry out a particular update operation are stored as a queued transaction. When the update to the second tree completes, the trees are switched. The queued transaction is applied to the now-out-of-date tree, such that the nodes of this tree do not need to be searched or otherwise evaluated in order to perform the update, thereby optimizing the process of bringing this tree into synchronization with the tree that is now being used by the searchers. The two trees are repeatedly switched as additional update operations are performed. Atomic operations are used to ensure proper synchronization between the search and update processing on the trees.
|
