System and method for supporting zero-copy binary radix tree in a distributed computing environment
A system and method supports key management in a distributed computing environment such as a distributed data grid. A binary radix tree is used to intern a plurality of binary keys. The binary radix tree is serialized to a byte buffer and a view of the binary is created. A byte sequence interface to the nodes of the serialized binary radix tree allows use of references which refer to positions in the serialized binary radix tree instead of requiring byte array copes of the interned keys. Use of references into the byte array in place of a byte array copies of interned keys reduces the memory overhead associated with referrers such as reverse indices which make reference to values associated with the plurality of binary keys. The reduction in memory overhead enhances performance and capabilities of a distributed computing environment such as a distributed data grid.
1. A method for supporting key management in a distributed computing environment, the method comprising:
providing a binary radix tree comprising a plurality of nodes which intern a plurality of binary keys;
serializing the binary radix tree to a buffer;
providing an interface to the buffer, wherein the interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a node of the binary radix tree and with a binary key of the plurality of binary keys; and
providing said plurality of references to a plurality of referrers whereby the plurality of referrers are enabled to realize the plurality of binary keys from the plurality of references without maintaining copies of the plurality of binary keys.
2. The method of claim 1 , further comprising:
providing a plurality of satellite nodes in the binary radix tree wherein the plurality of satellite nodes are augmented with information indicative of their position in the binary radix tree.
3. The method of claim 1 , further comprising:
providing a plurality of satellite nodes in the binary radix tree wherein the plurality of satellite nodes are augmented with position information indicative of their position in the binary radix tree; and
using the position information encoded in satellite nodes to improve efficiency of traversal of the binary radix tree.
4. The method of claim 1 , wherein providing an interface to the buffer, wherein the interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a node of the binary radix tree and with a binary key of the plurality of binary keys comprises:
providing a byte sequence interface to the buffer, wherein the byte sequence interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a location of node of the binary radix tree in said byte sequence interface and with a binary key of the plurality of binary keys.
5. The method of claim 1 , wherein providing an interface to the buffer, wherein the interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a node of the binary radix tree and with a binary key of the plurality of binary keys comprises:
providing a byte sequence interface to the buffer, wherein the byte sequence interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a location of node of the binary radix tree in said byte sequence interface and with a binary key of the plurality of binary keys; and
supporting a byteAt(n) method with the byte sequence interface where the byteAt(n) method returns a byte at the an nth position in the byte sequence.
6. The method of claim 1 , wherein providing an interface to the buffer, wherein the interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a node of the binary radix tree and with a binary key of the plurality of binary keys comprises:
providing a byte sequence interface to the buffer, wherein the byte sequence interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a location of node of the binary radix tree in said byte sequence interface and with a binary key of the plurality of binary keys; and
supporting a length method with the byte sequence interface wherein the length method can determine the number of bytes of data represented in a node of the byte sequence.
7. The method of claim 1 , wherein:
the plurality of referrers comprise plurality of reverse indices and wherein each reverse index comprises a set of references.
8. The method of claim 1 , wherein:
the plurality of referrers comprise plurality of reverse indices and wherein each reverse index comprises a set of references; and
whereby each reverse index has reduced memory overhead compared to maintain a set of binary keys.
9. The method of claim 1 , further comprising:
associating each node in the binary radix tree with an address for a value associated with a key associated with the node.
10. The method of claim 1 , further comprising:
providing a long storage array holding a plurality of addresses for values associated with the plurality of keys; and
associating each node in the binary radix tree with a slot in the long storage array and thereby associating each node with an address for a value associated with a key associated with the node.
11. A system for supporting key management in a distributed computing environment, the system comprising:
a computer system comprising a microprocessor and a memory;
a server node of said distributed computing environment operating on said computer system; and
wherein the server node is configured to,
provide a binary radix tree comprising a plurality of nodes which intern a plurality of binary keys;
serialize the binary radix tree to a buffer in memory of said computer system allocated to said node;
provide an interface to the buffer, wherein the interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a node of the binary radix tree and with a binary key of the plurality of binary keys, and
provide said plurality of references to a plurality of referrers whereby the plurality of referrers are enabled to realize the plurality of binary keys from the plurality of references without maintaining copies of the plurality of binary keys.
12. The system of claim 11 , wherein the server node is further configured to provide a plurality of satellite nodes in the binary radix tree, wherein the plurality of satellite nodes are augmented with information indicative of their position in the binary radix tree.
13. The system of claim 11 , wherein the server node is further configured to:
provide a plurality of satellite nodes in the binary radix tree wherein the plurality of satellite nodes are augmented with position information indicative of their position in the binary radix tree; and
use the position information encoded in satellite nodes to improve efficiency of traversal of the binary radix tree.
14. The system of claim 11 , wherein the interface to the buffer comprises:
a byte sequence interface to the buffer, wherein the byte sequence interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a location of node of the binary radix tree in said byte sequence interface and with a binary key of the plurality of binary keys.
15. The system of claim 11 , wherein the interface to the buffer comprises:
a byte sequence interface to the buffer, wherein the byte sequence interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a location of node of the binary radix tree in said byte sequence interface and with a binary key of the plurality of binary keys; and
wherein the byte sequence interface is configured to support a byteAt(n) method with the byte sequence interface where the byteAt(n) method returns a byte at the an nth position in the byte sequence.
16. The system of claim 11 , wherein the interface to the buffer comprises:
a byte sequence interface to the buffer, wherein the byte sequence interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a location of node of the binary radix tree in said byte sequence interface and with a binary key of the plurality of binary keys; and
wherein the byte sequence interface is configured to support a length method with the byte sequence interface wherein the length method can determine the number of bytes of data represented in a node of the byte sequence.
17. The system of claim 11 , wherein:
the plurality of referrers comprise plurality of reverse indices and wherein each reverse index comprises a set of references; and
whereby each reverse index has reduced memory overhead compared to maintain a set of binary keys.
18. The system of claim 11 , wherein each node in the binary radix tree is associated with an address for a value associated with a key associated with the node.
19. The system of claim 11 , further comprising:
a long storage array holding a plurality of addresses for values associated with the plurality of keys; and
wherein each node in the binary radix tree is associated with a slot in the long storage array and thereby associated with an address for a value associated with a key associated with the node.
20. A non-transitory computer readable medium including instructions stored thereon for supporting key management in a distributed computing environment, which instructions, when executed, cause a node in the distributed computing environment to perform steps comprising:
providing a binary radix tree comprising a plurality of nodes which intern a plurality of binary keys;
serializing the binary radix tree to a buffer;
providing an interface to the buffer, wherein the interface is configured to provide a plurality of references, wherein each reference of the plurality of references is associated with a node of the binary radix tree and with a binary key of the plurality of binary keys; and
providing said plurality of references to a plurality of referrers whereby the plurality of referrers are enabled to realize the plurality of binary keys from the plurality of references without maintaining copies of the plurality of binary keys.