Technical Field
The present disclosure relates generally to a data partitioning for improved parallelism in data processing.
Description of Related Art
The concept of parallelism, in computing, is based on dividing a large problem into several small problems, which can then be tackled substantially simultaneously, reducing the overall length of time required to solve the problem. Locking is a programming tool which permits one thread to take control of a variable and prevent other threads from accessing it, until the variable is unlocked. Many storage systems utilize a model of parallelism in which data partitions are employed to minimize locking. Locking is not required under the model of parallelism because a given thread is assigned exclusive access to certain data objects. This is beneficial because a) locking can be expensive and b) locking requires a code re-write to become safe to execute on multiple CPUs.
Furthermore, some systems utilize a hierarchical data partitioning framework. This allows threads to exclude multiple partitions from being accessed, thereby providing broader object protection.
However, the conventional data partitioning models require a preset fixed number of partitions, which is not optimal for all workloads. Under such a conventional model the number of partitions may be insufficient for an offered workload. Specifically, since only a single thread can process a data partition at a time, if the workload maps to only a few partitions, then the parallelism will be low.
The problem becomes more complicated in a hierarchical model of parallelism where the provided number of partitions at any level in the hierarchy may be very low in comparison to the available number of central processing units (CPUs). This situation can result in decreased parallelism, and in turn, decreased performance, as the limited number of partitions fail to make use of all the available CPUs.
In a conventional hierarchical model of data partitioning, there are a fixed number of partitions at each level in the hierarchy. Each partition provides certain permissions to access particular objects. Higher levels of partitions in the hierarchy provide the full access rights of lower partitions as well as additional rights specific to that partition. For instance, each object of a given type ‘x’ may be mapped to a partition of type ‘X’. If there are more objects than partition instances, then multiple objects are mapped to a single partition. This results in serialization of accesses to all objects that map to that partition, even though no serialization is required for correctness (it is an artifact of the architecture). The number of partitions at each level can be tuned to be efficient for a wide range of workloads, but cannot be optimal in all cases as the objects being accessed can vary in number, size, access pattern, and other attributes. Each partition is associated with a single process/thread, so if the number of used partitions is too low in comparison to the available CPUs, then all available CPUs will not be utilized.
Therefore, there is a need for a method and system where the number of partitions of each level in the hierarchy is continually tuned at runtime based on the observed workload characteristics. By providing the workload with a larger number of partitions to exploit as needed (and fewer of those that it cannot exploit) and in turn enabling it to use more CPUs, parallelism and performance can be enhanced. Such a system incorporates optimal performance in a wide range of environments including environments in which the workload continually changes over time.
USPTO Backgrounds
USPTO Backgrounds