Flexible partitioning of data

Disclosed are various embodiments of a flexible application-level partitioning scheme for data storage components. A data store is accessible by one or more computing devices and includes multiple partitions. One of the partitions is identified by mapping a key value of a data item to one of the partitions according to one of multiple versions of mapping metadata. Each of the versions of mapping metadata specifies a respective list of some or all of the partitions and an approach for mapping the key value to one of the partitions. The data item is inserted into the identified partition.

BACKGROUND

Partitioning of data may refer to a division of a data store or its constituent elements into distinct independent parts. Partitioning of data storage components may be done, for example, to improve manageability, performance, and/or availability. For example, in horizontal partitioning, various ranges of data records may be stored in multiple tables instead of a single table. In vertical partitioning, various attributes of a data record may be distributed among multiple tables.

DETAILED DESCRIPTION

The present disclosure relates to a flexible partitioning scheme for data storage components. Although partitioning of data may offer significant benefits, it may be difficult, for example, to foresee how many partitions are needed and how best to assign data to the partitions. Various embodiments of the present disclosure implement an application-level partitioning of data that enables a user to add partitions, remove partitions, control the growth rate of partitions, change keys used for partitioning, change the methodology of mapping keys to partitions, and so on. In the following discussion, a general description of the system and its components is provided, followed by a discussion of the operation of the same.

With reference toFIG. 1, shown is a networked environment100according to various embodiments. The networked environment100includes one or more computing devices103in data communication with one or more clients106by way of a network109. The network109includes, for example, the Internet, intranets, extranets, wide area networks (WANs), local area networks (LANs), wired networks, wireless networks, or other suitable networks, etc., or any combination of two or more such networks.

The computing device103may comprise, for example, a server computer or any other system providing computing capability. Alternatively, a plurality of computing devices103may be employed that are arranged, for example, in one or more server banks or computer banks or other arrangements. For example, a plurality of computing devices103together may comprise a cloud computing resource, a grid computing resource, and/or any other distributed computing arrangement. Such computing devices103may be located in a single installation or may be distributed among many different geographical locations. For purposes of convenience, the computing device103is referred to herein in the singular. Even though the computing device103is referred to in the singular, it is understood that a plurality of computing devices103may be employed in the various arrangements as described above.

Various applications and/or other functionality may be executed in the computing device103according to various embodiments. Also, various data is stored in a data store112that is accessible to the computing device103. The data store112may be representative of a plurality of data stores112, as can be appreciated. The data stored in the data store112, for example, is associated with the operation of the various applications and/or functional entities described below. In one embodiment, the data store112corresponds to a relational database management system (RDBMS). In one embodiment, the data store112may comprise a distributed data store112.

The components executed on the computing device103, for example, include a data store management application115and other applications, services, processes, systems, engines, or functionality not discussed in detail herein. The data store management application115is executed to provide a management interface for the data store112. To this end, the data store management application115processes queries, inserts, updates, and other commands relating to data items stored in the data store112. In one embodiment, the data store management application115is operable to receive and process structured query language (SQL) statements. The data store112is divided into a plurality of partitions118a,118b. . .118N, and the data store management application115includes a mapping function for mapping data items to partitions118. The partitions118are provided in order to improve, for example, performance, reliability, and scaling of the data store112. In various embodiments, the partitions118may comprise distinct tables, databases, filesystems, disk partitions, storage devices, and/or other possible divisions of a data store112.

The data stored in the data store112includes, for example, application data stored in the partitions118, mapping metadata124, data access history127, and potentially other data. The application data stored in the partitions118may be regarded as data items. Such data items may correspond to serialized instances of objects, rows within tables of a relational data store, and other forms of data. The data items may correspond to an instance of a class, table, template, or other form of data item type. The data items may include multiple columns, fields, attributes, and/or other types of constituent data. A column, field, attribute, etc. may be designated as a key attribute for a type of data item.

The mapping metadata124is used by the mapping function121to map data items to partitions118. The mapping metadata124may include, for example, a list of some or all of the partitions118of the data store112, a description of an approach for mapping key values of data items to partitions118, a timestamp, a description of a key used for partitioning, and/or other data. In various embodiments, the mapping metadata124may include one or more versions130with varying lists of partitions118, varying approaches for mapping, varying timestamps, varying partition keys, etc.

The data access history127relates to previous accesses of data items in the data store112, for example, through queries. The data access history127may be associated with various types of data items to specify which attributes of the types of data items are most frequently accessed or queried. Such attributes may be identified by the data store management application115as key attributes in various embodiments.

The client106is representative of a plurality of client devices that may be coupled to the network109. The client106may comprise, for example, a processor-based system such as a computer system. Such a computer system may be embodied in the form of a desktop computer, a laptop computer, a server computer, personal digital assistants, cellular telephones, smartphones, set-top boxes, music players, web pads, tablet computer systems, game consoles, electronic book readers, or other devices with like capability. The client106may include a display that may comprise, for example, one or more devices such as cathode ray tubes (CRTs), liquid crystal display (LCD) screens, gas plasma-based flat panel displays, LCD projectors, or other types of display devices, etc.

The client106may be configured to execute various applications such as a data store client application133and/or other applications. The data store client application133may be executed to send SQL statements, queries, and/or other types of commands to the data store management application115over the network109. In one embodiment, the data store client application133may provide a user interface. In another embodiment, the data store client application133may interface with other applications executing in the client106, for example, in the form of a system service, library, module, etc. The client106may be configured to execute applications beyond the data store client application133such as, for example, browser applications, email applications, instant message applications, and/or other applications.

Next, a general description of the operation of the various components of the networked environment100is provided. To begin, a user or an application on a client106issues a command or query through the data store client application133. The command or query is sent via the network109to the data store management application115. The data store management application115may record the command or query in the data access history127and may associate the command or query with the various types of data items included in the command or query.

Various commands include adding or removing partitions118, inserting data items into the data store112, loading data items from the data store112, updating data items in the data store112, modifying the growth rate of partitions118, and so on. The insert operation, load operation, and update operation may be frequently used commands that are available to end users, while the add partition operation, remove partition operation, and partition growth modification operation may be privileged commands that are restricted to administrative users. The insert operation, load operation, add partition operation, and remove partition operation will be discussed in more detail in connection with the flowcharts ofFIGS. 2-5, respectively. The various operations involve storing data items in the partitions118in such a way as can be configured and reconfigured at the application level, which results in greater flexibility. After processing a command or query, the data store management application115returns the result to the data store client application133.

An important portion of the data store management application115is the mapping function121, which translates a key value of a data item into a specific partition118. In one embodiment, the mapping function121is implemented as an object that is instantiated according to a version130of mapping metadata124. Each version130may be configured to map the key value differently. Each version130is associated with a specific list of partitions118to which the key values may be mapped. Each version130also specifies an approach for mapping the key values to partitions118. One example of such an approach includes a modulo operation that distributes the key values to the partitions118. Other approaches may include hard-coded mappings of key values, hashing functions, etc.

Each version130may also specify the key attribute for a type of data item that is used in obtaining a key value. In other words, the mapping function121may consume objects or references thereto rather than merely key values. The mapping function121may then obtain the key value from the object. In some embodiments, the key attribute may be determined based at least in part on the data access history127associated with the type of data item when a version130of mapping metadata124is created. It may be advantageous to have a key attribute correspond to the attribute that is most commonly used in queries regarding the type of data item. If a key attribute is changed, the mapping function121may need to consult previous key attributes to obtain data items already stored in the data store112under previous keys.

Depending on the distribution of the key values and/or other factors, some partitions118may be filled more quickly than others. Thus, it may be desirable to rebalance data allocation to partitions118. A new version130of the mapping metadata124may be generated to address the issue. In the new version130, the approach to mapping may be customized to give more weight to certain partitions118over others. In one embodiment, elements in the list of partitions118(e.g., partition identifiers) may be duplicated a number of times. Consequently, it may be more likely that the mapping function121will map key values to the partitions118corresponding to the duplicated elements. Likewise, duplicated elements may be removed in additional versions130to reduce key allocation to the corresponding partitions118.

An application may be configured to archive data from the data store112. If an application is configured to archive old data and thereby remove it from the data store112, the data store management application115may be configured to discard old versions130of mapping metadata124that were used to insert the old data into the data store112. Which versions130are considered old or unnecessary may be determined with reference to a timestamp, or creation date, associated with each version130.

Other optimizations may be made for the data store management application115. For example, recently inserted data may be generally loaded and updated. If the versions130of mapping metadata124are used in descending order according to their creation date, it may be highly likely that the initial few queries will return the desired data item. This is applicable when all data for a given key value resides in one partition118. In addition, if the creation date of the data item is available, versions130created after the data item may be ruled out. Further, the data may be redistributed according to the latest version130of mapping metadata124, which permits the earlier versions130to be deleted once redistribution is completed.

Referring next toFIG. 2, shown is a flowchart that provides one example of the operation of a portion of the data store management application115according to various embodiments. In particular,FIG. 2illustrates the portion of the data store management application115that is configured to insert data items into the data store112(FIG. 1). It is understood that the flowchart ofFIG. 2provides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the data store management application115as described herein. As an alternative, the flowchart ofFIG. 2may be viewed as depicting an example method implemented in the computing device103(FIG. 1) according to one or more embodiments.

Beginning with box203, the data store management application115obtains a request to insert a data item into the data store112. In box206, the data store management application115configures the mapping function121(FIG. 1) to use the most recent version130(FIG. 1) of the mapping metadata124(FIG. 1). In one embodiment, the data store management application115determines which one of multiple versions130is most recent by referring to a timestamp associated with each version130. Such a timestamp may be a logical timestamp such as a sequence number, a physical timestamp such as seconds since a certain date, and/or other data that indicates relative time.

In box209, the data store management application115determines the key value for the data item based on the input data of the data item and one or more key attributes defined in the mapping metadata124. The key attribute for data items of that type is predetermined and is stored in a version130of mapping metadata124. Alternatively, the key attribute may be determined by analyzing the data access history127(FIG. 1) associated with data items of that type when the version130of mapping metadata124is created. In one embodiment, the key attribute for data items of a given type is the attribute most frequently used in queries. When the key attribute is determined, the key value for the data item may be determined.

In box212, the data store management application115uses the mapping function121to obtain a partition118for the given key value associated with the data item. As a non-limiting example, the version130of the mapping metadata124may include a list of partitions118(e.g., “1, 2, 3, 4”) and an approach for mapping the key value to one of the partitions118in the list (e.g., a modulo operation). Where a modulo operation is employed, the modulo operation may be applied to a dividend corresponding to a numeric representation of the key value and a divisor corresponding to a number of elements in the list.

In this non-limiting example, suppose that the numeric representation of the key value is 1024. The result from the modulo operation is 0, which corresponds to the first position in the list, which is “1” in this example. Thus, the key value is mapped to the partition118identified by “1.” Once the partition118is obtained, the data store management application115moves to box215and inserts the data item into the partition118. Thereafter, the portion of the data store management application115ends.

Turning now toFIG. 3, shown is a flowchart that provides one example of the operation of another portion of the data store management application115according to various embodiments. In particular,FIG. 3illustrates the portion of the data store management application115that is configured to load data items from the data store112(FIG. 1). It is understood that the flowchart ofFIG. 3provides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the data store management application115as described herein. As an alternative, the flowchart ofFIG. 3may be viewed as depicting an example method implemented in the computing device103(FIG. 1) according to one or more embodiments.

Beginning with box303, the data store management application115obtains a request to load a data item. In box306, the data store management application115loads all versions130(FIG. 1) of the mapping metadata124(FIG. 1) from the data store112. In box309, the data store management application115configures the mapping function121(FIG. 1) to use one of the versions130of the mapping metadata124. If recently inserted data is generally loaded and updated, the versions130may be ordered such that the most recent version130is used first, the next most recent version130is used second, and so on. Next, in box312, the data store management application115uses the mapping function121to obtain a partition118(FIG. 1) to which a key value of the data item is mapped. The key value may be determined according to a key attribute specified by the version130of mapping metadata124.

In box315, the data store management application115determines whether the partition118has been already queried for the data item. If the partition118has not already been queried for the data item, the data store management application115proceeds to box318and queries the partition118for the data item using, for example, the key value for the data item. In box321, the data store management application115determines whether the data item is in the partition118. If the data item is in the partition118, the data store management application115moves to box324and returns the data item from the partition118. In one embodiment, the data store management application115may cache an identifier of the partition118in association with the data item to provide in connection with subsequent update operations for the data item. Thereafter, the portion of the data store management application115ends.

However, if the data store management application115determines in box315that the partition118has already been queried (e.g., when the partition118is returned when the mapping function121is configured for a previous version130of mapping metadata124), or if the data store management application115determines in box321that the data item is not in the identified partition118, the data store management application115moves to box327. In box327, the data store management application115determines whether another version130of mapping metadata124remains to be processed. If there is not another version130of mapping metadata124, the data store management application115continues to box330and returns an indication that the data item has not been found in the data store112. Thereafter, the portion of the data store management application115ends.

If, instead, the data store management application115determines in box327that there is another version130of mapping metadata124to be processed, the data store management application115transitions to box333and configures the mapping function121to use another version130of the mapping metadata124. The data store management application115then returns to box312and uses the reconfigured mapping function121to obtain a partition118for the key value. The partition118may or may not be a previously queried partition118. Thereafter, the data store management application115continues to box315.

Moving on toFIG. 4, shown is a flowchart that provides one example of the operation of another portion of the data store management application115according to various embodiments. In particular,FIG. 4illustrates the portion of the data store management application115that is configured to add partitions118(FIG. 1) to the data store112(FIG. 1). It is understood that the flowchart ofFIG. 4provides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the data store management application115as described herein. As an alternative, the flowchart ofFIG. 4may be viewed as depicting an example method implemented in the computing device103(FIG. 1) according to one or more embodiments.

Beginning with box403, the data store management application115obtains a request to add one or more new partitions118to the data store112. In box406, the data store management application115creates the new partitions118in the data store112, which have respective partition identifiers. In box409, the data store management application115creates a new version130(FIG. 1) of the mapping metadata124(FIG. 1). The new version130has a list of partitions118that includes the new partitions118. Thereafter, the portion of the data store management application115ends.

Subsequently, when data items are inserted in the data store112as shown in the flowchart ofFIG. 2, the new version130of the mapping metadata124is used in the mapping function121(FIG. 1). Thus, depending on the mapping approach employed in the new version130, it is possible that data items may be inserted into the new partitions118.

Referring next toFIG. 5, shown is a flowchart that provides one example of the operation of yet another portion of the data store management application115according to various embodiments. In particular,FIG. 5illustrates the portion of the data store management application115that is configured to remove partitions118(FIG. 1) from the data store112(FIG. 1). It is understood that the flowchart ofFIG. 5provides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the data store management application115as described herein. As an alternative, the flowchart ofFIG. 5may be viewed as depicting an example method implemented in the computing device103(FIG. 1) according to one or more embodiments.

Beginning with box503, the data store management application115obtains a request to remove one or more partitions118from the data store112. In box506, the data store management application115creates a new version130of mapping metadata124reflecting the change. Specifically, the new version130excludes the removed partitions118from the list of partitions118included in the new version130. Thereafter, the portion of the data store management application115ends.

Subsequently, when data items are inserted into the data store112as depicted in the flowchart ofFIG. 2, the new version130of the mapping metadata124is employed. Because the list of partitions118embodied in the new version130excludes the removed partitions118, data items will not be inserted into the removed partitions118. However, in one embodiment, the removed partitions118may still physically exist in the data store112. Also, load and update queries may still be processed through the removed partitions118. Where the removed partitions118still physically exist in the data store112, they may be re-added through additional versions130of the mapping metadata124.

With reference toFIG. 6, shown is a schematic block diagram of the computing device103according to an embodiment of the present disclosure. The computing device103includes at least one processor circuit, for example, having a processor603and a memory606, both of which are coupled to a local interface609. To this end, the computing device103may comprise, for example, at least one server computer or like device. The local interface609may comprise, for example, a data bus with an accompanying address/control bus or other bus structure as can be appreciated.

Stored in the memory606are both data and several components that are executable by the processor603. In particular, stored in the memory606and executable by the processor603is the data store management application115, including the mapping function121, and potentially other applications. Also stored in the memory606may be a data store112and other data. In addition, an operating system may be stored in the memory606and executable by the processor603.

It is understood that there may be other applications that are stored in the memory606and are executable by the processors603as can be appreciated. Where any component discussed herein is implemented in the form of software, any one of a number of programming languages may be employed such as, for example, C, C++, C#, Objective C, Java, JavaScript, Perl, PHP, Visual Basic, Python, Ruby, Delphi, Flash, or other programming languages.

A number of software components are stored in the memory606and are executable by the processor603. In this respect, the term “executable” means a program file that is in a form that can ultimately be run by the processor603. Examples of executable programs may be, for example, a compiled program that can be translated into machine code in a format that can be loaded into a random access portion of the memory606and run by the processor603, source code that may be expressed in proper format such as object code that is capable of being loaded into a random access portion of the memory606and executed by the processor603, or source code that may be interpreted by another executable program to generate instructions in a random access portion of the memory606to be executed by the processor603, etc. An executable program may be stored in any portion or component of the memory606including, for example, random access memory (RAM), read-only memory (ROM), hard drive, solid-state drive, USB flash drive, memory card, optical disc such as compact disc (CD) or digital versatile disc (DVD), floppy disk, magnetic tape, or other memory components.

Also, the processor603may represent multiple processors603and the memory606may represent multiple memories606that operate in parallel processing circuits, respectively. In such a case, the local interface609may be an appropriate network109(FIG. 1) that facilitates communication between any two of the multiple processors603, between any processor603and any of the memories606, or between any two of the memories606, etc. The local interface609may comprise additional systems designed to coordinate this communication, including, for example, performing load balancing. The processor603may be of electrical or of some other available construction.