Database redistribution utilizing virtual partitions

In some embodiments, a partitioned database is stored in a plurality of logical or physical partitions on at least a logical or physical first data storage node, and a subset of a first partition among the plurality of logical partitions is configured as a virtual partition. An input indicating an allocation of a second physical data storage node to store the partitioned database is received. A second partition is configured on the second data storage node. In response to the input, the partitioned database is redistributed over the first and second data storage nodes by moving data within the virtual partition on the first partition to the second partition.

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention relates in general to data processing, and in particular, to redistribution of a partitioned database.

2. Description of the Related Art

In computing environments in which a large volume of data is stored, the data are commonly managed by a relational database management system (RDBMS), which can be utilized to instantiate one or more databases for storing, accessing and manipulating the data. Each databases includes one or more table spaces, which in turn store table data in accordance with the relational data model. As implied by tabular organization, the table data is logically arranged in rows and columns, with each table row having an associated row key.

To provide enhanced manageability, performance and/or availability, a relational database is commonly partitioned into multiple logical or physical partitions (hereinafter, simply referred to as a “partition” unless a more definite meaning is required), each having its own data, indexes, configuration files, and transaction logs. Table data of any given table can be located in one or more of the partitions, with the partition on which the table data resides typically being determined by a hash function. Because data is distributed across database partitions, the power of multiple processors, possibly on multiple computers, can be harnessed in tandem to store, retrieve, process and manage the data in the database.

Enterprises that manage large data volumes, such as online transaction processing (OLTP) systems, data warehousing enterprises, insurance and financial companies, etc., are frequently required to expand their data storage and processing capacities as the volume of stored data grows. For example, an enterprise may add one or more additional servers and their associated storage nodes to the existing information technology (IT) infrastructure of the enterprise in order to handle an increased volume of data while avoiding a degradation in query response times.

To make use of the additional servers, the RDBMS must redistribute and reorganize one or more database instances so that the database instance(s) reside not only on the storage nodes of the existing servers, but also on the storage nodes of the newly installed servers. A conventional process by which a RDBMS redistributes and reorganizes a database in accordance with the prior art is depicted inFIG. 1.

The conventional process of redistributing and reorganizing a database begins at block100and thereafter proceeds to block102, which depicts the RDBMS making a backup of the entire database that is to be redistributed. Depending upon the size of the database, making a backup of the database can consume significant processing time (e.g., days or weeks). The process then enters an iterative loop including blocks104-118in which the database is redistributed row by row across the existing and new storage nodes. The redistribution begins at block104, which depicts the RDBMS reading a key value of the next database row to be processed. The RDBMS then rehashes the key value of the database row to determine a target partition number on which the database row will reside following the redistribution (block106). At block110, the RDBMS determines whether the target partition number is the same as the existing partition number, meaning that the database row will not be moved. If the target partition number matches the existing partition number, the process passes to block118, which is described below. If, however, the target partition number does not match the existing partition number, the process proceeds to blocks112-116.

At blocks112-116, the RDBMS reads the complete database row from the preexisting storage node, inserting the database row in a new partition on a newly added storage node, and then deleting the database row from the preexisting storage node. Thereafter, at block118, the RDBMS determines whether or not all rows of the database have been processed. If not, the process returns to block104, which has been described. If, however, RDBMS determines at block118that all rows of the database have been processed, the process proceeds to block120.

As will be appreciated, the movement of selected database rows from the preexisting storage nodes to the newly installed storage nodes via the redistribution depicted at block104-118leaves the preexisting storage nodes sparsely populated and thus inefficiently utilized. Consequently, at block120the RDBMS reorganizes the database rows in the preexisting storage nodes to return the database to a compact storage organization. If the reorganization completes successfully, the RDBMS then makes a second backup of the entire database at block122. In addition, as depicted at block124, the RDBMS executes a utility to gather statistics regarding the database, to recharacterize the table spaces, indexes, and partitions, and to record these statistics in a catalog. Finally, at block126, the RDBMS notifies any partition-aware applications (e.g., Microsoft® Internet Information Services (IIS)) of the reorganization of the database across the newly added storage nodes. Thereafter, the conventional process for redistributing and reorganizing the database ends at block130.

FIGS. 2A-2Cdepict the redistribution and reorganization of a database over newly added data storage nodes in accordance with the prior art. In particular,FIG. 2Adepicts a data storage system200including four database partitions202a-202dthat are populated with a database. Because the size of the database is nearing the capacity of the currently installed data storage nodes, a data warehousing enterprise may add one or more additional storage nodes to data storage system200in order to support additional database partitions.

In the example depicted inFIG. 2B, the data warehousing enterprise adds one or more additional storage nodes to data storage system200in order to support four additional database partitions202e-202h.FIG. 2Bfurther illustrates that, following the conventional row-by-row redistribution of the database depicted at blocks104-118ofFIG. 1, the portion of the database moved to new database partitions202e-202his tightly compacted, but the portion of the database remaining on original database partitions202a-202dis sparsely populated and therefore makes poor utilization of the storage capacity of data storage system200. Accordingly, as discussed above with reference to block120ofFIG. 1, the RDBMS must also reorganize the portion residing on database partitions202a-202dto achieve the compact, well distributed database illustrated inFIG. 2C.

SUMMARY OF THE INVENTION

In some embodiments, a partitioned database is stored in a plurality of logical or physical partitions on at least a logical or physical first data storage node, and a subset of a first partition among the plurality of logical partitions is configured as a virtual partition. An input indicating an allocation of a second physical data storage node to store the partitioned database is received. A second partition is configured on the second data storage node. In response to the input, the partitioned database is redistributed over the first and second data storage nodes by moving data within the virtual partition on the first partition to the second partition.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENT

With reference now to the figures and with particular reference toFIG. 3, there is illustrated a high level block diagram of an exemplary data processing environment300in accordance with one embodiment. As shown, exemplary data processing environment300includes an data processing enterprise310, which can be operated or on behalf of an organization, such as a business, governmental agency, non-profit association, educational institution or the like, that manages a large volume of data. Data processing enterprise310is coupled for communication to one or more circuit-switched or packet-switched communication networks304, such as wired or wireless local area or wide area network(s), cellular telephony network(s), and/or public switched telephone network(s) (PSTNs). Thus, data processing enterprise310may communicate with devices302a-302d(e.g., server computer systems, personal computer systems, portable computer systems, mobile telephones, smart phones, landline telephones) via communication network(s)304.

The communication between devices302a-302dand data processing system110can include voice communication, for example, via a PSTN or voice over Internet Protocol (VoIP) connection, and/or data communication, for example, via instant messaging, Simple Mail Transport Protocol (SMTP) or Hypertext Transfer Protocol (HTTP). For example, the communication between data processing enterprise310and devices302a-302dcan include the transmission of data requests from devices302a-302dto data processing enterprise310and the transmission of responsive data (e.g., formatted as program code, images, graphics, text, audio, video, and/or files containing such data) from data processing enterprise310to devices302a-302d.

Still referring toFIG. 3, data processing enterprise310can include one or more physical computer systems, such as servers312a-312n, which are coupled for communication by a communication fabric314, which can include, for example, cabling and/or network connections, such as an intranet, virtual private network (VPN) or socket connection. In the illustrated exemplary embodiment, server312aincludes one or more network interfaces316that permit server312ato communicate via communication networks304and communication fabric314. Server312aadditionally includes one or more processors320that process data and program code, for example, to manages, access and manipulate data organized in one or more databases. Server312aalso includes input/output (I/O) devices322, such as ports, displays, and attached devices, etc., which receive inputs and provide outputs of the processing performed by server312a. Finally, server312aincludes data storage330, which may include one or more volatile or non-volatile storage devices, including memories, solid state drives, optical or magnetic disk drives, tape drives, etc.

In the depicted embodiment, data storage330stores an operating system (OS)332that manages the hardware resources of server312aand provides common services to other software executing on server312a. For example, OS332may be implemented with one of the AIX®, Linux®, Android®, or Windows® operating systems. Data storage330also includes a database manager122, such as the DB2® relational database management system (RDBMS) available from IBM Corporation of Armonk, N.Y., which manages, accesses and manipulates data within one or more databases, such as exemplary database350. In some embodiments, database manager340may be integrated with OS332or another software program. In addition to database350, database manager340maintains one or more partition configuration data structures352that define the various logical partitions of database350and map the partitions to the physical storage resources of data processing enterprise310. Database manager340may optionally also maintain a partition map354that maps virtual partitions of database350to the logical partitions of database350, as discussed further below.

In various embodiments, database manager340and/or OS332may include code to support communication of server312awith other servers312and devices302a-302dvia communication fabric314and communication network(s)304. Should appropriate communication capabilities not be integrated within OS332and/or database manager340in some embodiments, data storage330may additionally include communication code342, such as a web server (e.g., Apache, IIS, etc.), Interactive Voice Response (IVR) and/or other program code, that enables server312ato communicate with other servers312and devices302a-302dvia communication fabric314and communication network(s)304. In particular, if implemented, communication code342supports the communication of database queries to database manager340and the communication of responsive data from database manager340to a requester.

It should be appreciated that the contents of data storage330can be localized on server312ain some embodiments and will be distributed across the data storage330of multiple of servers312a-312nin other embodiments. In addition, the contents depicted in data storage330of server312amay optionally partially or fully reside on a storage area network (SAN)360of data processing enterprise310. As shown, SAN360includes a switch/controller (SW/C)362that receives and services storage requests and multiple data storage nodes370a-370k, each of which may comprise one or more physical non-volatile memory drives, hard disk drives, optical storage drives, tape drives, etc. In some embodiments, data storage nodes370a-370kmay be logical entities presenting virtualized abstractions of such physical storage resources.

It will be appreciated upon review of the foregoing description that the form in which data processing enterprise312is realized can vary between embodiments based upon one or more factors, for example, the type of organization, the size of database350, the number of devices302a-302dthat can query database350, etc. All such implementations, which may include, for example, one or more handheld, notebook, desktop, or server computer systems, are contemplated as embodiments of the inventions set forth in the appended claims.

FIG. 4depicts a more detailed view of a data storage node400(e.g., a data storage node370of SAN360or a data storage node within data storage330of a server312) within data processing enterprise310ofFIG. 3. In the depicted example, data storage node400hosts eight logical or physical partitions, which are hereinafter assumed to be logical partitions numbered LP0-LP7, respectively. Logical partitions LP0-LP7store a database350, which includes sixteen data blocks numbered B0-B15, respectively. In a RDBMS, each of data blocks B0-B15may correspond to one or more database rows having a common row key hash.

In accordance with the present disclosure, database manager340assigns a subset of data blocks B0-B15to virtual partitions. For example, database manager340may assign each of data blocks B8-B15to a respective one of eight virtual partitions numbered VP8-VP15. In various scenarios, each virtual partition can include one or more data blocks, which preferably all reside on a common logical partition. As discussed further below with reference toFIGS. 7-10, database manager340can efficiently redistribute database350by reference to the virtual partitions.

With reference now toFIG. 5, there is illustrated an exemplary embodiment of a partition configuration data structure352in accordance with one embodiment. In the depicted embodiment, partition configuration data structure352, which may be implemented, for example, in one or more database configuration files, includes a plurality of configuration entries500defining a plurality of logical partitions of database350and mapping the logical partitions to the physical storage resources of data processing enterprise310.

In an exemplary embodiment, each configuration entry500of partition configuration data structure352comprises a number of fields, including a node number field502, a hostname field504, a logical partition number field506, and a virtual partition flag508. Node number field502specifies an integer number uniquely identifying a partition of database350. In contrast to conventional partitioned databases that restrict node numbers to logical partitions, node number field502preferably contains a unique node number for each logical and virtual partition of database350. Hostname field504identifies the TCP/IP hostname (e.g., “ServerA”) of the database partition identified in node number field502. In addition, logical port field506specifies the logical port (e.g., logical partition) assigned to the database partition identified in node number field502, and virtual partition flag508identifies whether or not the partition specified in node number field502is a virtual partition. It should be appreciated that configuration entries500may include one or more additional fields providing additional configuration information, such as a communication path to a logical partition and/or operating system-specific information.

Given the exemplary embodiment of partition configuration data structure352depicted inFIG. 5, the portion of partition configuration data structure352describing data storage node400ofFIG. 4can be given as shown in Table I below.

With reference now toFIG. 6, there is illustrated an exemplary partition map354in accordance with one embodiment. In the depicted embodiment, database manager340implements partition map354as a lookup table including a plurality of rows500, each of which includes a hash value field502, a virtual partition number field504, and a logical partition number field506. Thus, each row500associates a respective hash value (e.g., derived via a hash function from a row key of a row of database350) with a logical partition number, and if applicable, a virtual partition number. For example, assuming hash values ranging between 0 and 4095 and a data storage node400implementing eight logical partitions LP0-LP7as shown inFIG. 4, partition map354can include 4096 rows500storing the values summarized in Table II below.

With reference now toFIG. 7, there is illustrated a high level logical flowchart of an exemplary method of redistributing a database in accordance with a first embodiment. The depicted method may be performed, for example, through the execution of database manager340by one or more processors320of a server312. As with the other logical flowcharts presented herein, it should be understood that steps are depicted in a logical rather than strictly chronological order and that, in at least some embodiments, one or more steps may be performed contemporaneously or in a different order than illustrated.

The process depicted inFIG. 7begins at block700and thereafter proceeds to block702, which illustrates database manager340configuring a desired number of virtual partitions in database350, for example, in response to an administrator input or automatically based upon predetermined defaults. In the exemplary partitioned database350described by Table I and depicted inFIG. 4, database manager340may enter the last eight entries500of partition configuration data structure352at block702in order to establish virtual partitions VP8-VP15within logical partitions LP0-LP7, respectively. As noted above, the virtual partitions contain the data of database350that will be redistributed as the physical storage capacity allocated to store database350scales. With the number and location of virtual partitions configured, database manager340optionally establishes partition map354in order to quickly map between hash values (e.g., of row keys) of data and the logical and virtual partitions configured by partition configuration data structure352(block704). Block704is optional in that database manager340could alternatively compute the logical and virtual partition associated with each hash value as needed.

The process proceeds from block704to block710, which depicts database manager340determining whether or not an input has been received indicating that database350is to be redistributed over an expanded physical storage capacity. As will be appreciated, the expanded physical storage capacity available to store database350may become available through the addition of a server312to data processing enterprise310, the addition of an additional data storage node370to SAN360, and/or the reallocation of existing data storage node(s) of data processing enterprise310to store database350. If database manager340does not detect an input indicating that database350is to be redistributed over an expanded physical storage capacity, the process remains at block710. While the process remains at block710, database manager340performs conventional database processing, including providing data responsive to structured query language (SQL) queries of database350and performing any requested management or configuration functions, etc., as is known in the art. In response to a determination by database manager340at block710that an input (e.g., a user command) has been received indicating that database350is to be redistributed over an expanded physical storage capacity, the process passes to block712.

Block712depicts database manager340establishing logical partitions on the new physical storage node(s) allocated to store database350. The process then enters a loop including blocks720-730in which virtual partitions are redistributed from the preexisting logical partitions to the new logical partitions established at block712. Referring first to block720, database manager340determines, for example, by reference to partition configuration data structure352, whether or not all virtual partitions of database350have been processed. In response to database manager350determining at block720that all virtual partitions of database350have been processed, the process proceeds from block720to block740, which is described below. If, however, database manager350determines at block720that not all virtual partitions of database350have been processed, database manager350selects a virtual partition for processing, for example, the next virtual partition listed in partition configuration data structure352(block722).

At block724, database manager350determines whether or not to move the virtual partition selected for processing, for example, by determining whether or not the virtual partition number matches a logical partition number assigned to one of the logical partitions established on the newly allocated storage node(s). In response to a determination not to move the currently selected virtual partition, the process returns to block720, which has been described. If, however, database manager350determines at block724that the selected virtual partition is to be moved, the process passes to block726. Block726depicts database manager350moving the data of the virtual partition using sequential access operations from the existing logical partition to the logical partition having a matching logical partition number. Database manager350then updates the metadata stored in association with the moved partition on the data storage node (block728) and clears the virtual partition flag508of the associated configuration entry500in partition configuration data structure352(block730). As a result, the moved partition is no longer a virtual partition and is converted into a data block of one of the logical partitions on the newly allocated data storage node. The process returns from block730to block720, which depicts database manager340processing the next virtual partition, if any.

In response to database manager340determining at block720that all virtual partitions have been processed, database manager340updates partition map354to reflect the modified relationship between hash values and logical and virtual partition numbers (block740). Following block740, the process depicted inFIG. 7ends at block742.

FIG. 8illustrates an exemplary redistribution of a database350from in accordance with the first exemplary method depicted inFIG. 7. In the example shown inFIG. 8, database350is originally stored on only the eight logical partitions (i.e., LP0-LP7) of data storage node400, as previously discussed with reference toFIG. 4. On logical partitions LP0-LP7, database manager340configures data blocks B8-B15as virtual partitions VP8-VP15, respectively.

The physical data storage capacity of data processing environment310available to house database350is then expanded to include an additional data storage node800. As noted with respect to block712, database manager340configures data storage node800with eight logical partitions numbered LP8-LP15. In addition, in accordance with blocks720-730ofFIG. 7, database manager340redistributes each of virtual partitions VP8-VP15(corresponding to data blocks B8-B15, respectively) to a respective one of logical partitions LP8-LP15on data storage node800, leaving data blocks B0-B7on logical partitions LP0-LP7of data storage node400.

Assuming data storage node800resides on a server312having the hostname “ServerB,” database manager340updates partition configuration data structure352from the state summarized above in Table I to that given in Table III below.

TABLE IIINode No.HostnameLogical Port No.VP0ServerA0—1ServerA1—2ServerA2—3ServerA3—4ServerA4—5ServerA5—6ServerA6—7ServerA7—8ServerB0—9ServerB1—10ServerB2—11ServerB3—12ServerB4—13ServerB5—14ServerB6—15ServerB7—
In addition, database manager350updates partition map354from the state summarized above in Table II to that given in Table IV below.

It should be noted by comparison ofFIG. 1withFIGS. 7-8that the exemplary process depicted inFIG. 7renders unnecessary many of the processing-intensive steps ofFIG. 1. For example, inFIG. 7, there is no need to rehash the rows of database350, as depicted at block106. In addition, there is no need to backup database350before or after the redistribution of database350, as depicted at blocks102and122ofFIG. 1. Further, there is no need to reorganize database120, as depicted at block120, or to update database statistics, as depicted at block124. Finally, there is no need to update partition-aware applications, as shown at block126.

With reference toFIG. 9, there is illustrated a high level logical flowchart of an exemplary method of redistributing a database in accordance with a second embodiment. In particular, the process depicted inFIG. 9redistributes database350onto one or more newly allocated physical storage nodes via a backup and restore of the virtual partitions of database350.

The process depicted inFIG. 9begins at block900and thereafter proceeds to block902, which illustrates database manager340configuring a desired number of virtual partitions in database350, for example, in response to an administrator input, as described previously. With the number and location of virtual partitions configured, database manager340optionally establishes partition map354in order to quickly map between hash values (e.g., of row keys) of data and the logical and virtual partitions configured by partition configuration data structure352(block904). The process proceeds from block904to block910, which depicts database manager340determining whether or not an input has been received indicating that database350is to be redistributed over an expanded physical storage capacity. If database manager340does not detect an input indicating that database350is to be redistributed over an expanded physical storage capacity, the process remains at block910(during which time, database manager340may perform other conventional database management operations).

In response to a determination by database manager340at block910that an input has been received indicating that database350is to be redistributed over an expanded physical storage capacity, the process passes to block912. Block912depicts database manager340establishing logical partitions on the new physical storage node(s) allocated to store database350. The process then enters a loop including blocks920-930in which virtual partitions are backed up from the preexisting logical partitions established at block912. Referring first to block920, database manager340determines, for example, by reference to partition configuration data structure352whether or not all virtual partitions of database350have been processed. In response to database manager350determining at block920that all virtual partitions of database350have been processed, the process proceeds from block920to block940, which is described below. If, however, database manager350determines at block920that not all virtual partitions of database350have been processed, database manager350selects a virtual partition for processing, for example, the next virtual partition listed in partition configuration data structure352(block922). Next, database manager350makes a backup of the selected virtual partition, but preferably excludes from the backup the remainder of the logical partition hosting the virtual partition (block926). Database manager350then clears the virtual partition flag508associated with the selected virtual partition in partition configuration data structure352(block930). The process returns from block930to block920, which depicts database manager340processing the next virtual partition, if any.

In response to database manager340determining at block920that all virtual partitions of database350on the preexisting physical data storage node(s) have been processed, database manager340restores each of the virtual partitions from the backup made at block926to a respective logical partition of the newly allocated physical storage node(s) of data processing enterprise310(e.g., the logical partition having a logical partition number matching the virtual partition number of the backed up virtual partition). As a result, the moved partition is no longer a virtual partition and is converted into a data block on a logical partition of the newly allocated data storage node(s). Database manager350then updates the metadata stored in association with the restored partition on the data storage node (block942) and deletes the moved partitions from the preexisting physical storage node(s) (block944). Database manager340additionally updates partition map354, if present, to reflect the modified relationship between hash values and logical and virtual partition numbers (block946). Following block946, the process depicted inFIG. 9ends at block950.

FIG. 10depicts an exemplary redistribution of a database in accordance with the second exemplary method illustrated inFIG. 9. In the example shown inFIG. 10, database350is originally stored on only the eight logical partitions (i.e., LP0-LP7) of data storage node400, as previously discussed with reference toFIGS. 4 and 8. On logical partitions LP0-LP7, database manager340configures data blocks B8-B15as virtual partitions VP8-VP15, respectively.

The physical data storage capacity of data processing environment310allocated to house database350is then expanded to include an additional data storage node800, on which database manager340configures eight logical partitions numbered LP8-LP15. In accordance with blocks920-930ofFIG. 9, database manager340creates a virtual partition backup1000containing a backup of each of virtual partitions VP8-VP15(corresponding to data blocks B8-B15, respectively), and preferably excluding other data residing on logical partitions LP0-LP7. Rather than performing a conventional restore back to the host logical partitions, database manager340then restores each virtual partition from virtual partition backup1000to a respective one of logical partitions LP8-LP15on data storage node800. In addition, database manager340deletes the corresponding virtual partitions from data storage node400, leaving data blocks B0-B7on logical partitions LP0-LP7of data storage node400. In this manner, database manager340redistributes the virtual partitions of database350from preexisting physical data storage node400onto newly allocated physical data storage node800by leveraging its backup capabilities, rather than by directly moving the data as depicted inFIG. 8. The resulting partition configuration data structure352and partition map354will, however, be the same as summarized above in Tables III and IV.

As has been described, in at least some embodiments a partitioned database is stored in a plurality of logical or physical partitions on at least a logical or physical first data storage node, and a subset of a first partition among the plurality of logical partitions is configured as a virtual partition. An input indicating an allocation of a second physical data storage node to store the partitioned database is received. A second partition is configured on the second data storage node. In response to the input, the partitioned database is redistributed over the first and second data storage nodes by moving data within the virtual partition on the first partition to the second partition.

While the present invention has been particularly shown as described with reference to one or more preferred embodiments, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention. For example, although aspects have been described with respect to a computer system executing program code that directs the functions of the present invention, it should be understood that present invention may alternatively be implemented as a program product including a tangible, non-transient data storage medium (e.g., an optical or magnetic disk or memory) storing program code that can be processed by a data processing system to perform the functions of the present invention.