Partition lookup and state synchronization

Disclosed herein are system, method, and computer program product embodiments for multilevel synchronization of database table partition states. An embodiment operates by retrieving a partition from a partition lookup structure and determining whether the partition is in an active state. Based on a determination that the partition is in the active state an embodiment increments a counter associated with the partition using a compare-and-swap instruction accesses the partition.

BACKGROUND

Many database systems rely on partitioning to improve performance. Generally, databases consist of one or more tables of data. Partitioning a table into distinct parts can improve the performance and availability of the data. Accessing data in a partitioned database table involves finding the partition by, for example, looking up an identifier in a list of partitions. Changing the state of a partition may require synchronization among multiple processes that access the partition. Current methods of synchronizing partition states may require using a synchronization variable, such as a mutex. However, a synchronization variable may cause performance degradation in processes waiting to obtain access to the variable.

DETAILED DESCRIPTION

Provided herein are system, method and/or computer program product embodiments, and/or combinations and sub-combinations thereof, for multilevel synchronization of database table partition states.

FIG. 1is a block diagram of a database100where multilevel synchronization of partition states can be performed, according to an example embodiment.

Database100includes one or more tables110containing one or more indices120. Database100may be implemented in any computer system, as described below with reference toFIG. 5by way of example. A table110comprises an organized set of data elements stored in database100. A table110can be modeled as a set of vertical columns, identified by name, and horizontal rows. For example, a table110may be created to store data regarding employees of a company. The table110may include columns for each type of information to be stored about each employee, for example, employee name, social security number, phone number, office location, etc. Each row of the table could then represent the value of the information for one employee.

An index120is a data structure for improving the speed of data retrieval in a table110. An index120can be created and maintained to quickly locate data without having to traverse an entire table110. For example, an index120can include an organized listing of employees sorted by social security number and pointing to the corresponding row in table110. In this way, the database can quickly locate an employee record using the social security number.

An index110can be divided into one or more partitions130. A partition130can create a division of a table110into independent parts. The partitioning can be done based on identified criteria. Common criteria for partitioning a table include range partitioning and list partitioning. Range partitioning can create a partition by selecting values within a particular range. For example, a partition could be for all table rows where the column for zip code has a value between 20000 and 29999. List partitioning can be a list of values that a column satisfies. For example, all rows where the column for office location is either Boston, New York, Philadelphia, or Washington, D.C., could make a partition for East Coast offices.

When a table110is partitioned, satisfying a database query may require locating the partition where the queried data is located. Traditionally, a database table may maintain a list of partitions. Conventionally, a partition may be identified using an index identifier and a partition identifier together. With traditional solutions, a database task trying to satisfy a query can access the list of partitions to locate a desired partition.

Partitions130can have an associated state. For example, when a partition130is first created it can be set to a CREATE state until the creation process completes. When the partition130is ready for use, it can be set to an ACTIVE state. Furthermore, when a partition130is ready to be dropped (i.e., removed) the partition130can be set to a DROP state until the dropping process completes.

The table110can include a data structure, which is described in greater detail below in conjunction withFIGS. 2 and 3, for efficient partition lookup. The data structure can be associated to partitions that could change in state independently, and can handle counters for the partitions to efficiently synchronize multiple access to the partitions.

FIG. 2is a block diagram showing further details of a database table110with partitions130configured to perform multilevel synchronization of partition states, according to an example embodiment.

Table110can contain a mutex210and partitions130. Mutex210is a variable used for concurrency control. In general, a mutex is used to prevent two concurrent processes from accessing a shared resource simultaneously. In an embodiment, mutex210is used to control access to indices in table110. For example, a process wanting change the state of a partition can set mutex210, perform the modification, and then clear mutex210. In this manner, the mutex210serves to prevent access to one or more partitions, whose state is being changed by an initial process, by other processes while the partitions are being placed in a transitory state by the initial process.

Partitions130can also contain a variable (e.g., keepcnt variable220) that maintains a count of how many processes are currently accessing the corresponding partition. When a process accesses a partition it increments the partition's keepcnt220. If a process wanted to drop (i.e., remove) a partition, the process would wait for the keepcnt variable220value for the partition to be 0.

An index120can also contain a partition lookup structure230. Partition lookup structure230can be a sorted array of partition identifiers along with a pointer to the partition. In an embodiment, only partitions in the ACTIVE state are included in partition lookup structure230.

In an embodiment, various mechanisms are provided for controlling access to partitions depending to the partition's state. In an embodiment, partitions in ACTIVE state can be accessed by using a compare-and-swap instruction to increment keepcnt variable220.

A process incrementing the variable (e.g., keepcnt220) can use a compare-and-swap instruction, such as, for example, a CMPXCHG instruction provided in x86 processor architectures. A compare-and-swap instruction can serve to ensure that the process correctly updates the value of the keepcnt variable in a multi-threaded database environment. For example, suppose two processes want to access a partition130. Both processes may read the current keepcnt value for the partition to be 2. If the processes were to update the value of keepcnt without using a compare-and-swap operation, the first process would set the keepcnt value to 3, but the second process would also set it to 3 if it read the value before the first process updated it. Instead, a compare-and-swap instruction can be used. A compare-and-swap instruction attempts to change the value of a variable as an atomic instruction. In the above example, the compare-and-swap instruction would compare the keepcnt value previously read by the second process and compare it with the current keepcnt value for the partition. If the values are different, the process will return the new keepcnt value and the second process can try to change it again. If the values are the same, the process changes the keepcnt value.

If a partition is in a non-active state, such as a DROP state, a process accessing it may obtain exclusive access to the process by using mutex210.

FIG. 3is a flowchart for a method300for accessing a partition while achieving multilevel synchronization of partition states, according to an example embodiment. Method300can be performed by processing logic that can comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (e.g., instructions run on a processing device), or a combination thereof.

At step302, a process looking to access a partition accesses the partition lookup structure and searches for the partition identifier (ID). In an embodiment, the process searches for the partition ID using a binary search algorithm, as will be understood by those skilled in the relevant arts.

At step304, the process obtains the partition and determines whether the partition is still valid, i.e., is in the ACTIVE state. This step ensures that another process has not changed the state of the partition in a multi-threaded processing environment. If at step304the partition is not in the ACTIVE state, the process moves to a fallback procedure for changing the state of the partition by trying to access the mutex, as shown in step314. If the partition is in the ACTIVE state, the process moves forward to step306to update the variable (e.g., keepcnt variable220) that keeps track of the processes accessing the corresponding partition.

At step306, the process increments the keepcnt variable220associated with the partition using a compare-and-swap atomic instruction. Again, this ensures effective synchronization of the partition state.

At step308, the process again verifies that the partition is in the ACTIVE state. If the state is in the ACTIVE partition, the process can proceed with the partition access, as shown in step310. If the partition state has changed, the process would decrement the keepcnt variable220, as shown in step312, and move to the fallback procedure of accessing the mutex, as shown in step314.

At step314, the process attempts to obtain the mutex. When the process succeeds at obtaining the mutex, the processor verifies that the partition is in the ACTIVE state, as shown at step316. If the partition is in the ACTIVE state, the process accesses the partition, as shown in step310. Otherwise, the process returns an error indicating that the partition is not ready for use.

FIG. 4is a flowchart describing a method400of changing the state of a partition while achieving multilevel synchronization of partition states, according to an example embodiment. Method400can be performed by processing logic that can comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (e.g., instructions run on a processing device), or a combination thereof.

At step402, a process looking to change the state of a partition accesses the partition lookup structure and searches for the partition identifier (ID). In an embodiment, the process searches for the partition id using a binary search algorithm, as will be understood by those skilled in the relevant arts.

At step404, the process attempts to obtain mutex210for the partition.

Once the process can set mutex210, the process sets the variable (e.g., keepcnt220) for the partition to a blocked value, as shown in step406. A blocked value can be any value that specifies that the partition is currently blocked from access. For example, the process can set the keepcnt220to a value of −100. Any other process trying to access the partition would read the blocked value and would wait to obtain mutex210that the process is holding.

At step408, the process can then proceed to change the state of the partition.

Various embodiments can be implemented, for example, using one or more well-known computer systems, such as computer system500shown inFIG. 5. Computer system500can be any well-known computer capable of performing the functions described herein.

Computer system500includes one or more processors (also called central processing units, or CPUs), such as a processor504. Processor504is connected to a communication infrastructure or bus506.

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

Computer system500may also include one or more secondary storage devices or memory510. Secondary memory510may include, for example, a hard disk drive512and/or a removable storage device or drive514. Removable storage drive514may 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 drive514may interact with a removable storage unit518. Removable storage unit518includes a computer usable or readable storage device having stored thereon computer software (control logic) and/or data. Removable storage unit518may be a floppy disk, magnetic tape, compact disk, DVD, optical storage disk, and/any other computer data storage device. Removable storage drive514reads from and/or writes to removable storage unit518in a well-known manner.

Computer system500may further include a communication or network interface524. Communication interface524enables computer system500to communicate and interact with any combination of remote devices, remote networks, remote entities, etc. (individually and collectively referenced by reference number528). For example, communication interface524may allow computer system500to communicate with remote devices528over communications path526, 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 system500via communication path526.

In an embodiment, a tangible apparatus or article of manufacture comprising a tangible computer useable or readable medium having control logic (software) stored thereon is also referred to herein as a computer program product or program storage device. This includes, but is not limited to, computer system500, main memory508, secondary memory510, and removable storage units518and522, as well as tangible articles of manufacture embodying any combination of the foregoing. Such control logic, when executed by one or more data processing devices (such as computer system500), causes such data processing devices to operate as described herein.