Method and system of implementing a database index in shared memory
In one exemplary embodiment, a method includes allocating an arena block of a shared memory of a database node server. The arena block is divided into one or more slots. The one or more slots include a discreet and constant area of memory within the arena block. Each slot is assigned a constant-memory address relative to an arena-block's shared memory address. The index is implemented as a red-black tree data structure. Each red-black tree node is mapped to a slot. Each red-black-tree node is provided a pointer to one or more neighbor nodes. The index stored in shared memory can be used during a ‘warm’ rebooting process.
1. A method comprising
allocating an arena block of a shared memory of a database node server;
dividing the arena block into one or more slots, wherein the one or more slots comprise a discreet and constant area of memory within the arena block;
assigning each slot a constant-memory address relative to an arena-block's shared memory address;
implementing an index as a red-black tree data structure;
mapping each red-black tree node to a slot; and
providing each red-black tree node a pointer to one or more neighbor nodes.
2. The method of claim 1 further comprising:
reattaching, with a server process, to a persisted memory of the database node during a restart operation, wherein the persisted memory comprises the index.
3. The method of claim 1 , wherein the arena block comprises a one gigabyte contiguous-arena block, and wherein the arena block is divided into slots of sixty-four bytes each.
4. The method of claim 2 , wherein a contiguous-arena block comprises a contiguous region of memory that is allocated for storing the index.
5. The method of claim 4 , wherein the address comprises a relative address.
6. The method of claim 4 , wherein a plurality of arena-blocks are allocated in the shared memory based on a size of the index.
7. The method of claim 3 , wherein the contiguous-arena block is provided an address by a database node server's operating system.
8. The method of claim 1 , wherein a data storage metadata is stored in a random access memory and wherein the data storage metadata is separately rebuilt during a restart operation.
9. The method of claim 8 , wherein the arena-block's identifier comprises the arena-block's shared memory address.
10. The method of claim 1 , wherein the constant-memory address of the slot is determined using an offset from an arena-block's identifier.
11. The method of claim 10 , wherein the pointer to the one or more neighbor nodes comprises the one or more neighbor nodes offset slot from an arena-block's identifier.
12. The method of claim 1 , wherein a list comprising a root-node metadata and a sentinel-node metadata for the red-black tree data structure is stored in the shared memory.
13. A computer system comprising:
a processor configured to execute instructions;
a memory containing instructions when executed on the processor, causes the processor to perform operations that:
allocate an arena block of a shared memory of a database node server;
divide the arena block into one or more slots, wherein the one or more slots comprise a discreet and constant area of memory within the arena block;
assign each slot a constant address relative to an arena-block's shared memory address;
implement an index as a red-black tree data structure;
map each red-black tree node to a slot; and
provide each red-black-tree node a pointer to one or more neighbor nodes.
14. The computer system of claim 13 , wherein the arena block comprises a one gigabyte contiguous-arena block, and wherein the arena block is divided into slots of sixty-four bytes each.
15. The computer system of claim 13 , wherein a contiguous-arena block comprises a contiguous region of memory that is allocated for storing the index.
16. The computer system of claim 15 , wherein the contiguous-arena block is provided an address by a database node server's operating system.
17. The computer system of claim 13 , wherein the address comprises a relative address.
18. The computer system of claim 13 , wherein a plurality of arena-blocks are allocated in the shared memory based on a size of the index, and wherein the shared memory comprises a LINUX® system shared memory.
19. The computer system of claim 13 , wherein an arena-block's identifier comprises the arena-block's shared memory address.
20. The computer system of claim 13 , wherein a list comprising a root-node metadata and a sentinel-node metadata for the red-black tree data structure is stored in the shared memory.