Self tuning adaptive bucket memory manager

Disclosed herein are system, method, and computer program product embodiments for adaptively self-tuning a bucket memory manager. An embodiment operates by receiving requests for memory blocks of varying memory sizes from a client. Determining a workload for the client based on the requests. Analyzing buckets in the bucket memory manager based on the workload. Adjusting parameters associated with the bucket memory manager based on the analyzing to accommodate the requests.

BACKGROUND

Generally, in a typical computing environment, a memory manager allocates memory for various applications. The applications may request memory of varying sizes, from small chunks of memory to large chunks of memory. In return, the memory manager allocates the requested size from a block of memory and distributes the allocated memory to the application. However, there may be issues with performance in efficiently distributing memory of varying sizes. Specifically, memory managers tend to degrade the longer they run because as they allocate from the block of memory, the block of memory becomes fragmented. As a result, the memory manager may take a longer time to scan the fragmented block of memory to find a requested memory size.

DETAILED DESCRIPTION

Provided herein are system, apparatus, device, method and/or computer program product embodiments, and/or combinations and sub-combinations thereof, for adaptively self-tuning a bucket memory manager.

FIG. 1is a block diagram100of a client102interfacing with a database management system (DBMS)104, according to an embodiment. The DBMS104may include a database106having a plurality of nodes108. The nodes108of database106may be distributed within one or more machines or computers, over local or diverse geographic areas.

Nodes108may each include one or more processors, bucket memory manager110, local memory112, and a connection to one or more other nodes108of database106. Local memory112may be directly accessible via a high-speed bus or other connection120. Additionally, the nodes108may access the memory112of one or more other nodes108through one or more interconnects120.

An interconnect may be a connection or communication pathway between two or more nodes108, enabling the nodes to communicate with one another including accessing the memories112of other nodes108. For example, Node108-0may have access to both local memory112-0, as well as remote memory112-1. Memory112-1may be considered local memory to Node108-1, and remote memory to any other nodes108accessing memory112-1, including Node108-0. For example, remote memory112-0may be any memory that is accessible via a connection through one or more additional nodes108-1,108-2, and108-3other than the local node108-0.

In an embodiment, the bucket memory manager110, in any given node108, may interact with other bucket memory managers110in other node108through the interconnect120. In addition, as noted above, each bucket memory manager110has access to the respective local memory112of its own node108and any of the other remote memories112of other nodes108. For example, bucket memory manager110-0may have access to bucket memory manager110-3and remote memory112-3.

In an embodiment, DBMS104may receive a request from a client102for data114. DBMS104may determine that data114does not exist within the database106(e.g., in the memory112of any of the nodes108). DBMS104may then need to load data114from a disk116into one or more memories112. Alternatively, for example, client102may request that data114be loaded into database106from disk116.

Disk116may be a tape drive, hard drive disk, or other storage (generally referred to as secondary storage) that requires greater resources (including, but not limited to time) by which to perform data access. For example, generally, data stored in memory112may be accessed more quickly than data114when stored in disk116.

FIG. 2is a block diagram of a bucket memory manager110, according to an embodiment. As mentioned above, each of the nodes108include bucket memory manager110. The bucket memory manager110interacts with the memory112and processes requests from clients102for memory blocks of particular sizes.

In an embodiment, the bucket memory manager110may include one or more fixed size buckets202, one or more global buckets204, one or more instances206, and one or more associated engines208. A bucket202,204is a container for storing pointers to memory blocks in each of the memories112. The fixed size buckets202each store pointers to memory blocks of a particular size. For example, fixed size bucket202-1may store pointers to one or more 1-megabyte (MB) allocations from memory112-0in node108-0. In another example, bucket202-2may store addresses for one or more 3 MB allocation from memory112. Each of the fixed size buckets202-1through202-N are associated with memory blocks of a particular size.

In an embodiment, the global bucket204stores pointers to memory blocks of sizes not stored by fixed size buckets202. For example, fixed size bucket202-1may store a plurality of 1 MB memory sizes, fixed size bucket202-2may store a plurality of 3 MB memory sizes, fixed size bucket202-3may store a plurality of 5 MB memory sizes, whereas global bucket204-1may store memory blocks of other memory sizes from memory112. Thus, global bucket204-1is used to process memory requests of memory blocks not associated with the fixed size buckets202.

Each instance206comprises an engine208, one or more fixed size buckets202, and a global bucket204, according to an embodiment. For example, instance206-1comprises engine208-1, fixed size buckets202-1through202-N, and global bucket204-1.

In an embodiment, the bucket sizes associated with the fixed size buckets202for the instances206are the same. The number of buckets202,204in each of the instances206is the same. For example, each instance206has one global bucket204, one engine208and N number of fixed sizes buckets202. The fixed size buckets202across each of the instances206store pointers to memory blocks of the same size. For example, fixed size bucket202-1in each of the instances206may store pointers to memory blocks of 1 MB; fixed size bucket202-2in each of the instances206may store pointers to memory blocks of 3 MB; and, fixed size bucket202-3in each instance206may store pointers to memory blocks of 5 MB. In an alternative embodiment, the fixed size buckets202across each of the instances206store pointers to memory blocks of different sizes.

In an embodiment, the pointers in each of the fixed size buckets202,204across each of the instances point to different memory blocks. For example, each of the buckets202,204stores data structures210containing the pointers to the memory blocks of a particular size. The data structures210will be explained further below.

In an embodiment, engine208is a transaction manager for each of the buckets202,204. The engine208manages communication between the client102, the fixed size buckets202, the global bucket204, and the memory112for its respective instance206. For example, engine208-1may access and retrieve the pointers to a memory block of a particular size from fixed size bucket202-1based on a request from client102. Then, the engine208-1may access and retrieve the block of memory in memory112pointed to by the retrieved pointer.

In an embodiment, the engine208may access and insert fragments into the data structures210of the buckets202,204. The engine208may lock access to the accessed bucket202,204so no other engines208have access to that bucket. For example, engine208-1may access global bucket204-1in instance206-1to retrieve a memory address not associated with a fixed size bucket202. The engine208-1may use a spinlock on global bucket204-1so the other engines208-2through208-N cannot access the contents of global bucket204-1in instance206-1while engine208-1accesses global bucket204-1. However, the spinlock may only apply to a particular bucket of a particular instance, such as global bucket204-1in instance206-1. Engine208-2may therefore access any other bucket in instance206-1other than the global bucket204-1during the time engine208-1accesses the global bucket204-1.

In an embodiment, as noted above, each engine208is associated with an instance206. For example, engine208-1is associated with instance206-1. Engine208-1initially accesses and retrieves buckets from fixed size buckets202or global buckets204in instance206-1. If engine208-1does not find a requested memory size in instance206-1, engine208-1may access the fixed size buckets202or global buckets204in the other instances206-2through206-N. For example, engine208-1may retrieve a pointer to a 1 MB memory allocation from fixed size bucket202-1from associated instance206-1. However, in the case that the fixed size bucket202-1is empty and does not have any pointers to a 1 MB memory allocations, engine208-1will search for a pointer to a 1 MB memory allocation in the next available instance206. Engine208-1will then check the fixed size bucket202-1in instance206-2. The engine208-1will continue to check each other instance206until a pointer to a 1 MB memory allocation is retrieved. As mentioned above, upon retrieval the engine208-1carves the memory block from memory112based on the pointer and passes the memory block to client102.

In an embodiment, a processor associated with each of the nodes108may randomly assign an engine208to one of the instances206associated with that node108based on a thread id number or a random seed id number. For example, processor of node108-0assigns id number4to engine208-1of node108-0. Id number4associates engine208-1to instance206-4of node108-0. By associating an id number to each engine208in a respective node108, each engine208is guaranteed to be associated with a different instance206upon boot up.

In an embodiment, engine208may access memory112after recognizing one or more of the buckets are empty across all the instances206. For example, engine208-1recognizes fixed size bucket202-1and global bucket204in each instance206is empty when accessing and trying to retrieve a pointer to a 1 MB memory allocation. In response, engine208-1in node108-0will initially search in memory112-0in node108-0and scan for a memory chunk size of 1 MB. If local memory112-0provides no size of a contiguous 1 MB memory address space, then engine208-1will search in memory112-1. The engine208-1scans each subsequent memory112for a 1 MB memory allocation until one is found. Upon finding a 1 MB allocation in a memory112, engine208-1allocates the 1 MB block of memory from the memory112and stores a pointer to the address in fixed size bucket202-1.

In an embodiment, engine208returns the memory block from client102to the memory112. For example, engine208deallocates the memory block back to memory112. In addition, the engine208returns the pointer to the memory block to the bucket where the pointer was originally retrieved. For example, engine208-1accesses fixed size bucket202-1for retrieving a pointer to a 1 MB memory allocation for client102. Engine208-1passes the 1 MB memory allocation to client102based on the pointer. After client102finishes using the 1 MB memory, client102releases and deallocates the 1 MB memory address back to node108. The engine208-1also returns the pointer to the deallocates 1 MB memory allocation to fixed size bucket202-1.

In an embodiment, engines208may simultaneously be able to handle multiple tasks. These task may be searching for and allocating memory from memory112; processing requests from client102; and, interacting with the different buckets. In an alternative embodiment, an engine208which is not active may be used to scan the buckets in each of the instances206and fill the buckets with pointers to memory addresses to a max fill threshold. For example, engine208-3is not active. Specifically, engine208-3has not received a request from client102. Accordingly, engine208-3may scan each bucket202,204in each of the instances206to examine the max fill level of each bucket202,204. If engine208-3recognizes fixed size bucket202-1has 5 pointers and the max fill threshold is 10 pointers, engine208-3may scan the associated memory112, such as memory112-0, and allocate 5 more pointers to memory blocks for fixed size bucket202-1to meet the max fill threshold.

In an embodiment, the max fill threshold may be predefined by a configuration file. The configuration file may be read by every engine208upon boot up of the DBMS104. For example, the configuration file may specify a max fill threshold of 10 memory addresses for each bucket. The max fill threshold may be chosen based on the size of the memory allocated for the bucket memory manager110. The memory allocated for the bucket memory manager110will be explained below.

FIG. 3is a block diagram of an engine208-1interacting with a fixed size bucket202-1in the bucket memory manager110, according to an embodiment. The engine208-1communicates with interface302of fixed size bucket202-1. The interface302allows the engine208-1to communicate with the data structures210. Specifically, engine208-1communicates with the interface302to retrieve particular memory addresses from the data structures210. Further, the engine208-1communicates with the interface302to insert new memory addresses into the data structure210. In addition, the engine208-1may communicate to the interface302to remove all the data structures210.

In an embodiment, each of the buckets202,204adheres to the architecture described inFIG. 3. For example, each of the buckets202,204includes data structures210containing one or more data elements304. Each data element304contains a memory address, a size associated with the memory address, and a pointer, such as pointers306through316, pointing to the address of the next data element304.

In an embodiment, the data structures210organize the data elements304in a manner that facilitates easy retrieval and insertion. For example, the data elements304shown inFIG. 3are organized in a linked list manner. The linked list manner includes a data element304and a pointer306pointing to the next data element304. The last data element304-6includes a pointer316pointing to NULL. The NULL denotes the end of the linked list. The data structures210may not be limited to linked lists but may also be organized as dynamic arrays, stacks, queues, hash tables, heaps, and binary trees, according to some embodiments.

FIG. 4is a block diagram of a memory block112, according to an embodiment. The memory block112shows the various memory locations402through412pointed to by pointers306through316respectively. As shown inFIG. 3, the pointers306through316are contained by the fixed size bucket202-N from the data elements304inFIG. 3. Also mentioned above, the data elements304contain only the addresses, the pointers to the addresses, and size of the memory location, not the memory itself from memory block112. In addition, bucket memory manager110is contained in memory112. A chunk of memory from memory112is set aside to store the contents of the bucket memory manager110. This chunk of memory for the bucket memory manager110is calculated upon the max fill threshold of each data structure, the number of instances206allocated, and the number of buckets within those instances206upon boot up, according to an embodiment. The max fill threshold, the number of instances206, and the number of buckets within those instances206may be preconfigured in the configuration file to be read upon boot up of the DBMS104.

FIG. 5is a flowchart for a method500for operations of the bucket memory manager110, according to an embodiment. Method500can be performed by processing logic that can comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (e.g., instructions executing on a processing device), or a combination thereof.

In502, an engine208retrieves configuration information from a configuration file for the bucket memory manager parameters. For example, upon boot up of the DBMS104, engines208in each of the nodes108read information from a configuration file. Specifically, the information may consist of the number of instances206for each bucket memory manager110, the number of buckets202,204for each instance206, the bucket sizes for the fixed size buckets202, and a max fill threshold for each of the buckets202,204. In addition, the configuration information may contain a bucket memory manager run mode. Specifically, the bucket memory manager run mode may operate in two different settings. The two settings are manual mode and self-tuning mode. The method500illustrates the manual mode where the bucket sizes for the fixed size buckets202are pre-configured based on the information read from the configuration file. The self-tuning mode will be further explained below. In an embodiment, the configuration file may be stored in disk116and configured by a client102.

In504, the bucket memory manager parameters are configured based on the configuration information retrieved from the configuration file. For example, as mentioned above, nodes108are initialized based on the configuration information to have 5 instances206; each instance206contains 4 fixed size buckets202; and, the bucket sizes of each bucket202,204are 1 MB, 3 MB, 5 MB, and 10 MB. In addition, the max fill threshold for each of the buckets202,204has a fill level of 20. However, these numbers are for illustrative purposes only, other numbers may be used.

In506, the database106receives a request from client102for a requested memory size. For example, client102launches a particular application, such as a word document, which requires a particular memory size to execute and run. The database106receives a request from client102for a particular memory size, such as 3 MB, in order to run the word document. In an embodiment, a node108is chosen to receive the request of client102, such as node112-0, based on a workload of the nodes. An engine208, such as engine208-1in node112-0, receives the request from client102.

In508, an engine208, such as engine208-1, scans the fixed size buckets202-1through202-N of an associated instance206for a particular memory size based on a requested memory size from a client102. For example, engine208-1receives a 3 MB request from client102. In response, engine208-1scans for a match of a bucket size in the fixed size buckets202and the global bucket204. In an embodiment, the engine208scans the fixed size buckets202first before scanning the global bucket204.

In510, engine208determines if a match was found in one of the fixed size buckets202. For example, engine208-1scans for 3 MB sizes in the fixed size buckets202. Engine208-1finds fixed size bucket202-3holds pointers to 3 MB memory blocks. In514, that memory pointer is retrieved from the data structure210in the associated fixed size bucket202, such as fixed size bucket202-3. In response, the engine208grabs the allocated memory block based on the memory pointer.

If a match was not found, then in512, the engine208scans the global bucket204for the requested memory size. In an embodiment, the global bucket204stores the pointers of various memory addresses and associated sizes in ascending order. In an embodiment, the global bucket204stores the various addresses and associated sizes in ascending order of the addresses. The ascending order architecture facilitates the engine208to efficiently find a memory address of the requested size.

In516, the engine208passes the requested memory block based on the retrieved pointer to the client102. For example, the engine208passes the memory block402from memory112based on the pointer306retrieved from the fixed size bucket202-1to the client102. In an embodiment, the engine208maintains a tracking system to determine which memory addresses or memory blocks402through412are currently in use by a client102. This ensures another engine208does not allocate a memory block overlapping with memory currently in use by the client102. Specifically, the tracking system may be a table stored in the disk116storing a copy of the pointers306through316of the requested memory blocks. In an alternative embodiment, each bucket memory manager110keeps track of the memory block addresses in the respective engines208.

In518, the engine208receives the returned memory block from client102upon completion or application closing. For example, client102frees the 3 MB memory address and the engine208returns the pointer306of the 3 MB memory address to the associated fixed size bucket202-1. Specifically, the engine208inserts the returned pointer306back into the data structure210in the same fixed size bucket202-1from where it was retrieved. In an embodiment, the engine208clears an entry in the tracking system associated with the returned pointer.

FIG. 6is a flowchart illustrating a self-tuning mechanism in a bucket memory manager, according to some embodiments. Method600can be performed by processing logic that can comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (e.g., instructions executing on a processing device), or a combination thereof.

In602, requests are received for memory blocks of various sizes from client102. In an embodiment, the DBMS104may receive requests for memory blocks from client102of various sizes such as 3 MB, 4 MB, and 5 MB. These various sizes are based on the applications of client102.

In604, a workload for client102is determined based on the memory requests. In an embodiment, the workload of client102is based on a plurality of factors of the memory requests. For example, the workload may be the types of memory requests, the sizes of memory requests, and the frequencies of memory requests from a client102. More detail will be explained below.

In606, the existing buckets202,204are analyzed based on a workload of client102. In an embodiment, the bucket memory manager110continuously monitors parameters associated with the buckets202,204. The parameters associated with the buckets202,204may be the number of data elements304or fragments in the buckets202,204; the allocations associated with an engine; total number of memory requests for each instance206; the total number of buckets202,204and the total number of instances206; locking conditions associated with the buckets202,204; the sizes of the fixed size buckets202, and, any configuration setting stored in the configuration file. More detail on each of these parameters will be explained below.

In608, parameters associated with the bucket memory manager110are adjusted based on the analyzing to accommodate the requests. In an embodiment, the bucket memory manager110adjusts the bucket memory manager parameters based on the set of rules extracted from the configuration information. More detail on the adjustment of these parameters will be explained below.

FIG. 7is a flowchart for a method700for operations of the self-tuning mechanism in the bucket memory manager110, according to an embodiment. Method700can be performed by processing logic that can comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (e.g., instructions executing on a processing device), or a combination thereof.

In702, the engine208retrieves configuration information from a configuration file for the bucket memory manager parameters. For example, upon boot up of the DBMS104, engines208in each of the nodes108read information from a configuration file. Specifically, the information may consist of the number of instances206for each bucket memory manager110, the number of buckets for each instance206, the bucket sizes for the fixed size buckets202, and a max fill threshold for each of the buckets. As mentioned above, the configuration file also includes a bucket memory manager run mode. As method500above illustrates the manual mode of the bucket run manager flag, methods600above and700below illustrates the self-tuning mode where the bucket memory manager run mode is set to self-tuning mode. Further, the configuration information includes a set of rules for the bucket memory manager110to follow while the bucket run manager flag is set to the self-tuning mode. These set of rules instruct the bucket memory manager110for running in self-tuning mode, as explained below.

In704, the bucket memory manager parameters are configured based on the self-tuning mode and the configuration information retrieved from the configuration file. For example, when in the self-tuning mode, the configuration information initially sets the number of instances206for each bucket memory manager110, the number of buckets for each instance206, and a max fill threshold for each of the buckets. The other configuration information, as mentioned in the above paragraph, adapts to the needs of client102, according to an embodiment. In an alternative embodiment, in the self-tuning mode, the bucket memory manager parameters adapt to a particular need of client102.

In706, the database106receives a request from client102for a requested memory size. The same function occurs here as mentioned above in506and602. In addition, a memory request counter is initialized for each new memory request made from client102. For example, a memory request counter for 1 MB is initialized to 1 when a request for 1 MB is received. The associated memory request counter is incremented by one for each subsequent memory request of the same size. In an embodiment, all of the engines208maintain and monitor each of the memory request counters. In an alternative embodiment, each request from a client102is stored in an array to track all requests, as explained below.

In708, the bucket memory manager110analyzes a workload of a client102. For example, the workload may be the types of memory requests, the sizes of memory requests, and the frequencies of memory requests from a client102. In addition, the bucket memory manager110analyzes the amount of time a memory block is utilized by the client102. In an embodiment, the amount of time a memory block is utilized by client102initializes when the engine208passes the memory block to the client102and ends when the engine208receives the memory block from the client102. The engine208, which passes and receives the memory block to and from client102, tracks the time utilized via a timer.

In710, the bucket memory manager110analyzes the supply of buckets. Specifically, the bucket memory manager110continuously monitors parameters associated with the buckets. In an embodiment, the bucket memory manager110monitors the number of times an engine208steals a memory address from another instance206. For example, the engine208-1accesses fixed size bucket202-1in an associated instance206-1for a 1 MB memory address. However, fixed size bucket202-1is empty and does not have any 1 MB memory addresses. In response, engine208-1may access fixed size bucket202-1in another instance206-2and steal a 1 MB memory allocation to give to client102. The number of times an engine208steals a memory address from another instance206is stored in a variable labeled instance_empty. The contents of the instance_empty are incremented by one each time this situation occurs.

In an embodiment, the bucket memory manager110monitors the number of data elements304or fragments in each data structure210. For example, data structures210may each contain a different number of data elements304ranging from0to max fill threshold. Each engine208continuously monitors the data elements304in each of the buckets202,204with the associated instance206. The number of data elements304in a snapshot is stored in variable numfrags. The snapshot may be taken periodically, such as every hour, and before the system shuts down.

In an embodiment, the bucket memory manager110monitors parameters associated with the number of fragments in each fixed size bucket202and global bucket204. For example, each engine208monitors the range of the number of fragments in each of the buckets. Specifically, the engine208monitors the highest and the lowest number of fragments obtained in each data structure210. The highest number of fragments is stored in a variable labeled highwatermark and the lowest number of fragments is stored in a variable labeled lowwatermark. The contents of these two variables are stored from a snapshot at an instance in time of the bucket memory manager110. The snapshot may be taken periodically, such as every hour, and before the system shuts down.

In an embodiment, the bucket memory manager110monitors the number of times a misallocation occurs. For example, engine208-1may receive a request from client102for a memory size of 1 MB. Before engine208-1accesses and has a chance to retrieve the memory request of 1 MB from fixed size bucket202-1in instance206-1, engine208-2accesses and retrieves the memory address in instance206-1that engine208-1planned to retrieve. The engine208-1recognizes this situation as a misallocation, according to an embodiment. In response, engine208-1initializes an allocs_missed variable to keep track of the number of times this situation occurs for a particular bucket and an associated instance206. Each subsequent time this occurs, engine208-1increments the contents of the allocs_missed variable by one.

In an embodiment, the bucket memory manager110monitors the number of times engine208allocates from global bucket204-1despite an available fixed size bucket202. For example, engine208-1receives a request from client102for a memory size of 3 MB. Engine208-1accesses fixed size bucket202-3of instance206-1, which stores pointers to 3 MB memory blocks. However, the fixed size bucket202-3is empty. Engine208-1proceeds to check each fixed size bucket202-3of instances206-2to206-N yet finds no pointers to 3 MB memory blocks. As a result, engine208-1goes to the global bucket204-1of instance206-1for a pointer to a 3 MB memory block. If engine208-1recognizes the global bucket204-1does not have a pointer to a 3 MB memory allocation, the engine208-1allocates a 3 MB memory allocation from memory112. At the same time, the other engines208are signaled by engine208-1to allocate 3 MB memories from memory block112to fill their buckets storing pointers to the 3 MB memory allocations. In response, engine208-1initializes a bucket_empty variable to keep track of the number of times this situation occurs for a particular bucket and associated instance206. Each subsequent time this situation occurs, engine208-1increments the contents of the bucket_empty variable by one.

In an embodiment, the bucket memory manager110monitors the total number of requests for memory addresses for each instance206. For example, engine208-1receives100requests from client102for memory addresses whereas engine208-2receives 50 memory requests. Each engine208keeps track of the number of requests received starting after boot up in an allocs variable. The engine208increments the contents of the allocs variable by one every time a request is received.

In an embodiment, the bucket memory manager110monitors the current number of buckets202,204and the current number of instances206. The number of buckets202,204is stored in a variable labeled numbuckets and the number of instances206is stored in a variable labeled numinstances. At a specific instance in time, engine208may acquire a snapshot of the number of buckets202,204and the number of instances206in bucket memory manager110. The snapshot may occur periodically, such as every hour and before the system shuts down.

In an embodiment, the bucket memory manager110monitors the number of times the bucket memory manager110tried allocating a memory address under a locked condition. For example, engine208-1accesses fixed size bucket202-1. However, fixed size bucket202-1is locked due to engine208-2accessing and retrieving a pointer to a memory address. The number of retries for accessing a locked bucket202is stored in a variable labeled retries. Each time the locked bucket is accessed, the contents of the retries variable is incremented by one. Each engine208creates a separate retries variable for each bucket202in the associated instance206.

In an embodiment, the bucket memory manager110monitors the number of times the bucket memory manager110failed to allocate a memory address request. Specifically, the bucket memory manager110counts the number of times an engine208returned NULL to a memory request. For example, engine208-1scans all of the fixed size buckets202and all of the global size buckets204for a pointer to a 6 MB memory allocation request. However, none of the buckets in the bucket memory manager110contain a pointer to a 6 MB memory allocation nor is there enough contiguous memory space in memory112to allocate a 6 MB memory space. As a result, engine208-1returns a NULL to client102. A variable labeled failures for each engine208stores the number of times a NULL is returned to the client. Each time a NULL is returned by one of the engines208, the contents of the variable labeled failures is incremented by one.

In an embodiment, the bucket memory manager110monitors every request for a memory address from client102. For example, engine208-1receives five 4 MB address requests, six 1 MB address requests, and three 6 KB address requests. Engine208-2receives four 8 KB address requests and three 4 MB address requests. An array labeled statarray[n] in each engine208keeps track of the received address request for each of the engines208in a respective bucket memory manager110. The statarray[n] stores each memory address request associated with a timestamp when an engine208receives the request.

In712, the bucket memory manager110adjusts the bucket memory manager parameters based on the analyzing from604and606.712expands upon the functionality of608from above. Further, the bucket memory manager110adjusts the bucket memory manager parameters based on the set of rules extracted from the configuration information. As mentioned above, these set of rules define the self-tuning mode for the bucket memory manager110.

In an embodiment, one rule defines the fixed size buckets202with the most popular address sizes. Specifically, each of the fixed size buckets202needs to be tuned to the workload of the client102. For example, the statarray[n] is sampled by engine208for a certain amount of time, such as 5 minutes, to monitor the memory address requests. If engine208notices a particular memory address request, such as 5 MB, is more frequently requested from client102where these requests consume more than twenty percent of the statarray[n] for a length of time, the engine208will automatically add a 5 MB bucket202to instance206. In general, for self-tuning, the bucket memory manager110monitors the statarray[n] for a predetermined period. If a requested memory address consumes greater than a percentage threshold of the total allocations in statarray[n] during the predetermined period and a fixed size bucket202for the requested memory allocation does not already exist, a fixed size bucket202is created for the size of the requested memory allocation. In an embodiment, when a fixed size bucket202-N is added to one instance206-1to match the current workload of client102, the other instances206-2through206-N also add a fixed size bucket202-N of the requested memory address size.

In an embodiment, another rule is to avoid having too many memory address sizes in an unused bucket202. Specifically, engine208may contain fixed size buckets202of sizes 1 MB, 3 MB, 4 MB, and 5 KB. However, if the engine208notices the 5 KB fixed size bucket202is rarely used, then the engine208removes the 5 KB fixed size bucket202in order to preserve memory. For example, the statarray[n] is sampled by engine208for a predetermined period, such as 5 minutes, to monitor the memory address requests. If engine208notices a memory address request, such as 5 KB, consumes less than one percent of the total allocations in statarray[n] during that predetermined period, then the engine208will remove the 5 KB fixed size bucket202. Removal of the memory addresses for the 5 KB fixed size bucket202consists of freeing the memory fragments, according to an embodiment. Therefore, if a requested memory address amount consumes less than a percentage threshold of the total allocations in the statarray[n] after sampling for a predetermined period, the engine208removes that fixed size bucket202from the instances206.

In an embodiment, another rule is to avoid and reduce any engine/bucket contention. Specifically, a goal of the self-tuning is to pass memory efficiently and avoid any contention between buckets. For example, engine208-1of instance206-1tries to steal memory addresses from fixed size bucket202-1of instance206-2. However, engine208-1of instance206-2is in the process of accessing and retrieving a memory address from the fixed size bucket202-1of instance206-2. Therefore, engine contention occurs and the bucket memory manager110degrades performance. In order to alleviate this issue, engine208adds more instances206. In this particular rule, the allocs_missed variable is sampled for a predetermined period, such as 5 minutes, to monitor the total memory allocation requests and the number of times another engine208-2stole from an engine208-1. If the engine208-1notices the contents of allocs_missed is greater than the predetermined period, such as ten percent of the total amount of memory allocation addresses over 5 minutes, then another instance206-N is added to the bucket memory manager110. The added instance206-N is populated with the same fixed size buckets202as the other instances206and a global bucket204. Upon adding an instance206, an engine208-N associated with the newly added instance206-N, allocates new memory addresses from memory112and fills the fixed size buckets202and the global bucket204with the new memory addresses.

In an embodiment, another rule is to avoid having too many memory addresses sizes in an unused instance206. Specifically, another goal of the self-tuning mode is to pass memory efficiently and avoid any memory that is not being used in an instance206. Further, another goal of this rule is to ensure maximum use of each instance206. If an instance206is not being used at all and not stealing memory address from other instances206, then that instance206should be removed. Specifically, the allocs_missed variable is sampled for a predetermined period, such as 5 minutes, to monitor the total memory allocation requests and the number of times another engine208-2steals from an engine208-1. If the engine208-1notices the allocs_missed contents is less than a predetermined threshold, such as 0.1 percent of the total amount of memory allocations, then that particular instance206, is removed from the bucket memory manager110.

Because of each of these rules, there are variations to actions that may be performed. Specifically, a fixed size bucket202may be created or removed and an instance206may be created or removed. Further, additional addresses may be added or removed from the fixed size bucket202or global bucket204if the bucket is greater than the max fill threshold or does not have any addresses in the bucket. In an embodiment, each engine208may perform these actions in parallel with actions from the other engines208.

In714, the engine208acts on the request from client102and passes the requested memory address to the client102.714expands upon the functionality of608from above. As mentioned in516, the engine208passes a pointer of the requested memory address from the fixed size bucket202-1or the global bucket204to the client102.

This process loops at706to monitor the bucket memory manager110upon receiving a request from client102for a requested memory address, according to an embodiment. In an alternative embodiment, the bucket memory manager110continuously monitors the self-tuning bucket memory manager parameters even when no requests are received for memory allocation from client102.

FIG. 8is a block diagram of a self-tuning environment800, according to an embodiment. In addition or alternatively to the description of the operations of the self-tuning mechanism within the bucket memory manager110with respect toFIGS. 6 and 7,FIG. 8illustrates a self-tuning mechanism802operating with one or more processing application(s)804. In some embodiments, self-tuning mechanism802begins operating with processing application804upon boot up of the DBMS104, or at some time thereafter. Specifically, the self-tuning mechanism802may be compiled or linked with the processing application804upon a client102invoking the processing application804. The processing application804may be any application associated with a processor or one or more engines or computing modules. For example, the processing application804may be the bucket memory manager110, a web browser, a media player, a computer game, to name a few examples, or any combination thereof. The self-tuning mechanism802may be included with and/or operate with the processing application804to improve efficiency and processing times associated with the processing application804.

In an embodiment, the self-tuning mechanism802in the environment800follows a similar rule structure as the self-tuning mechanism described in method700with regard to the bucket memory manager110. In an embodiment, however, the rule structure of the self-tuning mechanism802is defined following the compilation of the processing application804with the self-tuning mechanism802. In an embodiment, following compilation, the rule structure is set based on configuration information in a configuration file associated with the processing application804. For example, if the processing application804is a central processing unit (CPU) that is processing items off a queue, the parameters defined in the configuration file may set the number and depth of the queues; the amount of time items are allowed to remain on the queue before removal; and/or, a max threshold amount of items in any queue. In an embodiment, the self-tuning mechanism802utilizes the same or similar rule structure described in method700for the processing application804based on this configuration information. For example, similar to as described in712, the bucket memory manager parameters are adjusted based on the analyzing in604and606. Similarly, the self-tuning mechanism802may adjust the parameters for the CPU processing items off a queue example based on similarly defined rules. The same or similar functionality can be applied for any self-tuning mechanism802with any associated processing application(s)804.

Various embodiments can be implemented, for example, using one or more computer systems, such as computer system900shown inFIG. 9. Computer system900can be used, for example, to implement method500ofFIG. 5, method600ofFIG. 6, and method700ofFIG. 7. For example, computer system900can retrieve a memory allocation based on a request from client102using buckets in a bucket memory manager110. Computer system900can further self-tune a plurality of bucket memory manager parameters based on a current workload of memory allocation requests from client102, according to some embodiments. Computer system900can be any computer capable of performing the functions described herein.

Computer system900can be any well-known computer capable of performing the functions described herein.

Computer system900includes one or more processors (also called central processing units, or CPUs), such as a processor904. Processor904is connected to a communication infrastructure or bus906.

Computer system900also includes a main or primary memory908, such as random access memory (RAM). Main memory908may include one or more levels of cache. Main memory908has stored therein control logic (i.e., computer software) and/or data.

Computer system900may also include one or more secondary storage devices or memory910. Secondary memory910may include, for example, a hard disk drive912and/or a removable storage device or drive914. Removable storage drive914may be a floppy disk drive, a magnetic tape drive, a compact disk drive, an optical storage device, tape backup device, and/or any other storage device/drive.

Removable storage drive914may interact with a removable storage unit918. Removable storage unit918includes a computer usable or readable storage device having stored thereon computer software (control logic) and/or data. Removable storage unit918may be a floppy disk, magnetic tape, compact disk, DVD, optical storage disk, and/or any other computer data storage device. Removable storage drive914reads from and/or writes to removable storage unit918in a well-known manner.

According to an exemplary embodiment, secondary memory910may include other means, instrumentalities or other approaches for allowing computer programs and/or other instructions and/or data to be accessed by computer system900. Such means, instrumentalities or other approaches may include, for example, a removable storage unit922and an interface920. Examples of the removable storage unit922and the interface920may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM or PROM) and associated socket, a memory stick and USB port, a memory card and associated memory card slot, and/or any other removable storage unit and associated interface.

Computer system900may further include a communication or network interface924. Communication interface924enables computer system900to communicate and interact with any combination of remote devices, remote networks, remote entities, etc. (individually and collectively referenced by reference number928). For example, communication interface924may allow computer system900to communicate with remote devices928over communications path926, which may be wired and/or wireless, and which may include any combination of LANs, WANs, the Internet, etc. Control logic and/or data may be transmitted to and from computer system900via communication path926.