System and method for managing storage of partitioned datasets in a distributed database

Disclosed herein is a system, comprising a distributed database comprising a plurality of partitions allocated in memory for storing a plurality of datasets. Wherein each dataset stored in the distributed database comprises at least a primary data portion stored in a respective primary partition of the plurality of partitions and at least zero additional data portions stored in respective secondary partitions of the plurality of partitions. Wherein each data portion of each dataset is mapped to a respective partition in which it is stored by a respective identifier. Wherein the primary data portion of each dataset comprises metadata stored in the primary partition, the metadata is indicative of the identifier of all additional data partitions of the respective dataset.

BACKGROUND

The present invention, in some embodiments thereof, relates to storing datasets in a distributed database and, more specifically, but not exclusively, to storing datasets in a distributed database by segmenting each dataset to one or more data portions stored in respective partitions of the database and associating a primary portion of each dataset with metadata mapping all additional portions of the respective dataset to secondary partitions.

Data storage is the corner stone for practically any application, service, platform and/or infrastructure in the present information driven era. Data storage systems, for example, databases, datacenters, cloud storage services and/or the like may be therefore essential to maintain the need for storing data.

Databases have proven to be highly efficient for data storage and with constant demand for additional storage space, much research and innovation is invested to improve database architecture and capabilities to address diverse requirements, such as, for example, robustness, reliability, efficiency and capability typically coupled with the need to ensure integrity, consistency, security and often privacy of the stored data.

Efficiency of database systems may be measured in a plurality of aspects and terms, for example, capacity, integrity, scalability, recoverability, and/or the like. Another key factor which is of great significance is the performance of the database system which may be expressed in one or more parameters, for example, latency, access time, bandwidth, and/or the like.

SUMMARY

According to a first aspect of the present invention there is provided a system, comprising a distributed database comprising a plurality of partitions allocated in memory for storing a plurality of datasets. Wherein each dataset stored in the distributed database comprises at least a primary data portion stored in a respective primary partition of the plurality of partitions and at least zero additional data portions stored in respective secondary partitions of the plurality of partitions. Wherein each data portion of each dataset is mapped to a respective partition in which it is stored by a respective identifier. Wherein the primary data portion of each dataset comprises metadata stored in the primary partition, the metadata is indicative of the identifier of all additional data partitions of the respective dataset.

According to a second aspect of the present invention there is provided a computer implemented method of storing datasets in a distributed database, comprising:Receiving a plurality of datasets for store in a distributed database deployed comprising a plurality of partitions allocated in memory for storing a plurality of datasets.Segmenting each of the plurality of datasets to a respective primary data portion and at least zero respective additional data portions according to a size of the respective dataset.Writing the respective primary data portion of the respective dataset in a respective primary partition of the plurality of partitions allocated for the respective dataset.Writing each additional data portion of the respective dataset in a respective secondary partition of the plurality of partitions allocated for the respective dataset, each additional data portion is mapped to the respective secondary partition by a respective identifier.Updating metadata of the primary data portion of the respective dataset to include the identifiers of all additional data portions of the respective dataset. The metadata is stored in the respective primary partition allocated for the respective dataset in association with the primary data portion of the respective dataset.

In a further implementation form of the first, and/or second aspects, the respective identifier of the primary portion of the respective dataset mapping the respective primary portion to a respective primary partition further serves as an identifier of the entire respective dataset.

In a further implementation form of the first, and/or second aspects, each of the plurality of partitions is allocated a predefined size for storing a respective data portion of a respective dataset.

In a further implementation form of the first, and/or second aspects, the plurality of partitions are deployed across a plurality of concurrently accessible clusters such that multiple data portions of a respective dataset are accessible concurrently.

In a further implementation form of the first, and/or second aspects, the additional data portions of a respective dataset are stored in consecutive partitions.

In a further implementation form of the first, and/or second aspects, a read cycle for fetching a respective dataset from the distributed database comprises, reading the primary data portion of the respective dataset from its respective primary partition, and analyzing the metadata of the primary data portion to identify each additional data portion of the respective dataset. Responsive to detecting that the respective dataset comprises only the primary data portion, completing the read cycle. Responsive to detecting that the respective dataset comprises one or more additional data portions, reading all of the additional data portions of the respective dataset from the respective secondary partitions according to the identifiers extracted from the metadata which map each additional data portion to a respective secondary partition.

In a further implementation form of the first, and/or second aspects, in case the respective dataset comprises a plurality of additional data portions, the plurality of additional data portions are read concurrently from multiple respective second partitions.

In a further implementation form of the first, and/or second aspects, a write cycle for storing a new dataset to the distributed database comprises, determining, based on a size of the new dataset, whether the new dataset comprises a single data portion or a plurality of data portions. Responsive to determining that the new dataset comprises a single data portion, storing the new dataset by updating metadata of a primary data portion of the new dataset to indicate the new dataset has no additional data portions, and writing the primary data portion including its metadata in a respective primary partition allocated for the new dataset. Responsive to determining that the new dataset comprises a plurality of data portions, storing the new dataset by writing each additional data portion of the new dataset in a respective secondary partition of the plurality of partitions allocated for the new dataset, each additional data portion of the new dataset is mapped to the respective secondary partition by a respective identifier, updating the metadata of the primary data portion of the new dataset to include the identifier of each additional data portion of the new dataset, and writing the primary portion including its metadata in the respective primary partition.

In a further implementation form of the first, and/or second aspects, in case the new dataset comprises a plurality of additional data portions, the plurality of additional data portions are written concurrently to multiple respective secondary partitions.

In a further implementation form of the first, and/or second aspects, a write cycle for updating a respective dataset stored in the distributed database with an update dataset comprises determining, based on a size of the update dataset, whether the update dataset comprises a single data portion or a plurality of data portions. Responsive to determining that the update dataset comprises a single data portion, storing the update dataset by updating metadata of a primary data portion of the update dataset to indicate the update dataset has no additional data portions, and writing the primary data portion including its metadata in a respective primary partition storing the stored dataset to overwrite the stored dataset. Responsive to determining that the updated dataset comprises a plurality of data portions, storing the update dataset by writing each additional data portion of the update dataset in a respective one of a plurality of secondary partitions allocated for the update dataset which is different from the respective secondary partition storing an additional data portion of the stored dataset, the respective additional data portion of the updated dataset is mapped to the respective different secondary partition by a respective new identifier, updating metadata associated with the primary data portion of the update dataset to indicate the new identifier of each additional data portion of the update dataset, and writing the primary portion of the update dataset including its associated metadata in the respective primary partition storing the stored dataset to overwrite the primary data partition of the stored dataset.

In a further implementation form of the first, and/or second aspects, in case the update dataset comprises a plurality of additional data portions, the plurality of additional data portions are written concurrently to multiple respective secondary partitions.

In a further implementation form of the first, and/or second aspects, the additional portions partitions of the stored dataset are discarded after a predefined time period to release the respective secondary partitions.

In an optional implementation form of the first, and/or second aspects, a plurality of write cycles for updating one or more datasets stored in the distributed database are accumulated according to one or more accumulation rules and initiating the accumulated write cycles when one or more of the accumulation rules are fulfilled.

In a further implementation form of the first, and/or second aspects, one or more of the accumulation rules define a certain timing for accumulating write cycles.

In a further implementation form of the first, and/or second aspects, one or more of the accumulation rules define a certain number of accumulated write cycles.

In an optional implementation form of the first, and/or second aspects, one or more lock mechanisms are applied during each of the accumulated write cycles to prevent simulations access of multiple write cycles to a common dataset.

DETAILED DESCRIPTION

The present invention, in some embodiments thereof, relates to storing datasets in a distributed database and, more specifically, but not exclusively, to storing datasets in a distributed database by segmenting each dataset to one or more data portions stored in respective partitions of the database and associating a primary portion of each dataset with metadata mapping all additional portions of the respective dataset to secondary partitions.

According to some embodiments of the present invention, there are provided methods, systems and computer program products for storing datasets in a distributed database comprising a plurality of partitions allocated for storing the datasets in a memory hosting the distributed database.

One or more distributed databases for example, an SQL database, a NoSQL database, a NewSQL database, and/or the like may be configured for storing a plurality of datasets, for example, tables, columns, rows, entries, and/or the like. The distributed database(s) may be controlled and managed by one or more Database Management Systems (DBMS), for example, Apache Cassandra, ScyllaDB, Aero spike, Amazon Keyspaces, Bigtable, Datastax, HBase, and/or the like.

The distributed database(s) and its DBMS may be typically deployed across a plurality of concurrently accessible storage clusters which may be accessed simultaneously for read and/or write accesses (queries).

As such, the partitions of the distributed database may be allocated over the storage clusters in an arrangement making them concurrently accessible partitions which are distinct and independent of each other and may be therefore accessed simultaneously.

Each of the partitions allocated in the distributed database may have a predefined size, for example, 512 KB, 1 MB, 2 MB, 5 MB, and/or the like. Each dataset stored in the distributed database may be therefore segmented, based on its size compared to the partition size, and stored in one or more partitions of the of the plurality of partitions of the distributed database which are allocated for storing the respective dataset.

However, regardless of its size, each dataset may comprise at least one data portion stored in a respective primary partition of the distributed database. Larger datasets may comprise one or more additional data portions stored in respective secondary partitions of the distributed database. Each dataset stored in the distributed database may therefore have a primary data portion stored in a respective primary partition and zero or more additional data portions stored in respective secondary partitions.

Moreover, the primary data portion of each dataset may comprise metadata stored in its respective primary partition in association with the primary data portion. The metadata may comprise at least an identifier of each additional data portion of the receptive dataset which maps the respective additional data portion to a respective secondary partitions.

Each read access (query) to a receptive dataset stored in the distributed database may therefore comprise an access to the primary partition to retrieve the primary data portion of the respective dataset and its associated metadata. The metadata of the primary portion may be analyzed to determine if the respective dataset comprises additional data portions and, in case it does, determine the mapping of the additional data portions to respective secondary partitions based on the identifiers extracted from the metadata. The respective secondary partition(s) may be then accessed, optionally concurrently, to retrieve the additional data portions. The primary data portion and the secondary data portions (id exits) may be then merged to reconstruct the complete requested dataset which may be provided in response to the query.

When storing a new dataset in the distributed database, i.e., a dataset which is stored in the distributed database for the first time, the new dataset may be first segmented to one or more data portions according to its size compared to the partition size. In case the new dataset may be stored in a partition, the new dataset may not be segmented as it may comprise only a primary data portion which may be stored in a respective primary partition. The metadata of the primary data portion of such single-portion datasets may be updated to indicate the respective dataset does not include additional data portions.

However, in case the new dataset requires multiple (two or more) partitions for storing it in the distributed database, the new dataset may be segmented to a primary data portion which may be stored in a respective primary partition and one or more additional data portions which may be stored in one or more respective secondary partitions. The metadata of the primary data portion of such multi-portion datasets may be updated to indicate the identifiers of all additional data portions mapping each additional data portion to a respective secondary partition.

The process and/or algorithm for storing an update dataset in the distributed database, i.e., a dataset which replaces a corresponding dataset (already) stored in the distributed database is slightly different from storing a new dataset for the first time.

In case of single-portion datasets, the primary data portion of a new dataset may be written to a free primary partition which does not store data of any other dataset. In contrast, in case of single-portion datasets written to replace corresponding datasets stored in the distributed database, the primary data portion of an update dataset may be written to the same primary partition storing the primary portion of the replaced dataset thus overwriting it.

The storing process is different between new datasets and update datasets also for multi-portion datasets written to replace corresponding datasets stored in the distributed database. A multi-portion dataset may require multiple (two or more) partitions for storing it, and the dataset may be therefore segmented to a primary data portion and one or more additional data portions. In case of a new dataset, the plurality of data portions, both the primary data portion and the additional data portion(s) may be stored in free primary partition which does not store data of any other dataset. However, in case of an update dataset, the additional data portions are first written into one or more respective secondary partitions which are free and are therefore different from the secondary partitions storing the additional data portions of the replaced dataset such that the (new) additional data portion(s) of the update dataset do not overwrite the (old) additional data portion(s) of the replaced dataset. Rather the additional data portions of both the update dataset and the replaced dataset co-exist at least for a predefined time period.

The metadata of the primary data portion of the update dataset may be updated to indicate the (new) identifiers of all additional data portions mapping each additional data portion in a respective secondary partition and the primary data portion may be written with its metadata in a respective primary partition. Specifically, the primary data portion of the (new) update dataset may be written in the primary partition storing to the same primary partition storing the primary portion of the replaced dataset thus overwriting it the primary data portion of the (old) replaced dataset.

The additional datasets of the replaced dataset may be discarded after a predefined time period, for example, 15 seconds, 30 seconds, 60 seconds, and/or the like to enable read (query) accesses to the distributed database which are in progress during the update process to complete. The additional data portions of the (old) replaced dataset and the additional data portions of the (new) update dataset therefore co-exist for the predefined time interval.

As such, the update process for updating a dataset stored in the distributed database is practically an atomic operation since as long as the primary data portion of the update dataset is not written to overwrite the primary data portion of the replaced dataset, all data portions, i.e., primary and additional data portions, of the replaced dataset are available for read (query) accesses. Once, the atomic operation of overwriting the primary data portion of the replaced dataset with the primary data portion of the update dataset, only the updated dataset is accessible while the replaced dataset is no longer accessible.

Optionally, a plurality of write cycles for writing new and/or update datasets to the distributed database are accumulated, for example, in a buffer, and written to the distributed database when reaching one or more accumulation thresholds and/or fulfilling one or more accumulation criteria which may be based on timing, volume, and/or the like.

Optionally, one or more lock mechanism may be applied for locking the distributed database and/or part thereof when writing one or more datasets to the distributed database.

Storing the primary portion of each dataset in the distributed database together with its metadata may present significant benefits and advantages compared to existing distributed databases systems.

First, since the metadata relating to each dataset is stored in a respective primary partition allocated in the distributed database in association with the primary data portion of the respective dataset, i.e., integrated with the primary data portion, a single query, i.e., read cycle (access) to the respective primary partition may retrieve the primary data portion and its metadata indicative of whether the respective dataset comprises additional data portions or not. The integrated metadata architecture may significantly improve access performance, for example, reduce query count compared to existing partitioned database systems in which the metadata is typically stored separately from the datasets thus requiring separate queries (read cycles) for retrieving the dataset and its metadata.

Moreover, since a plurality of secondary partitions may be accessed concurrently, in case a certain queried (read) dataset comprises multiple additional data portions stored respectively in multiple respective secondary partitions, the multiple secondary partitions may be accessed concurrently to simultaneously retrieve all additional data of the respective dataset.

Furthermore, since updating a dataset in the distributed database is an atomic operation, data integrity is ensured for each read (query) cycle conducted to the distributed database including such read cycles which are initiated to retrieve datasets during the time of updating the very same datasets. This is since up until the atomic operation of overworking the primary data portion of a replaced dataset with the primary data portion of a replacing dataset (update dataset), the read access may retrieve the previously (old) stored dataset, and once the primary data portion of the replacing dataset is written to overwrite the primary data portion of the replaced dataset, the read cycle may retrieve the new updated dataset.

In addition, accumulating a plurality of write and/or update cycles and initiating the accumulated cycles together may significantly reduce risk of racing between simultaneous update and read cycles thus further reducing the risk of data confection for the read cycles.

Also, applying the lock mechanism(s) to lock one or more of the partitions when writing one or more datasets may further increase reduce risk of racing between simultaneous write cycles and/or between simultaneous update and read cycles.

Finally, while the additional data portions of a replaced dataset are stored for a certain time period to support atomicity the update process and ensure data integrity for read cycles, the additional data portions are eventually discarded, when no longer needed, in order to release the partitions storing them and make them available for storing other datasets

Computer program code comprising computer readable program instructions embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wire line, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

Referring now to the drawings,FIG.1AandFIG.1Bare flowcharts of exemplary processes of storing and fetching datasets in and from a distributed database comprising a plurality of partitions, according to some embodiments of the present invention.

An exemplary process100may executed a write cycle for storing one or more datasets in a distributed database comprising of a plurality of partitions such that each dataset may be allocated one or more partitions. Moreover, the plurality of partitions storing each dataset may be concurrently accessible partitions which may be accessed simultaneously independently of each other.

Each dataset stored in the distributed database may be therefore segmented, based on its size, to one or more data portions, specifically at least a primary data portion and zero or more additional data portions.

The primary data portion of each dataset is stored in a primary partition allocated for the respective dataset from the plurality of partitions of the distributed database. Each additional data portion of the respective dataset, if exists, is stored in a respective one of a plurality of secondary partitions allocated for the respective dataset from the plurality of partitions of the distributed database.

Moreover, the primary data portion of each dataset may comprise metadata stored in its respective primary partition in association with the primary data portion. The metadata may comprise at least an identifier mapping each additional data portion of the receptive dataset in a respective one of the secondary partitions.

An exemplary process150may execute a read cycle for retrieving (fetching) one or more datasets stored in the distributed database.

Each read access to a receptive stored dataset may comprise accessing the primary partition of the respective dataset to retrieve its primary data portion, determining whether the receptive dataset has additional data portions, and accessing accordingly one or more of the secondary partitions of the respective dataset, according to the mapping identifier(s) extracted from the metadata of the dataset's primary portion, to retrieve the additional data portion(s) of the respective dataset.

Reference is also made toFIG.2, which is a schematic illustration of a system for storing and fetching datasets in and from a distributed database comprising a plurality of partitions, according to some embodiments of the present invention.

An exemplary database system200, for example, a server, a computing node, a cluster of computing nodes, a cloud platform, a cloud service, a datacenter, and/or the like, interchangeably designated Database Management System (DBMS), may comprise a distributed database202, for example, an SQL database, a NoSQL database, a NewSQL database, and/or the like configured for storing a plurality of datasets, for example, tables, columns, rows, entries, and/or the like.

In particular, the distributed database202managed by the database system200, for example, Apache Cassandra, ScyllaDB, Aerospike, Amazon Keyspaces, Bigtable, Datastax, HBase, and/or the like may be deployed across a plurality of concurrently accessible storage clusters which may be accessed simultaneously for read and/or write accesses. For example, the distributed database202may be utilized by a cluster of multiple storage servers (also known as commodity servers) which may be accessed concurrently where each server may host a respective segment of the distributed database202. In another example, the distributed database202may be utilized by a plurality of separate hard drives which may be accessed concurrently where each hard drive may host a respective segment of the distributed database202.

The database system200may comprise an Input/Output (I/O) interface210for receiving and/or outputting datasets stored in the distributed database202, a processor(s)212for executing the processes100and150, and a memory214for storing data and/or code (program store).

The I/O interface210may comprise one or more communication channels, interconnections, buses and/or the like for connecting to one or more other devices, systems, platforms, services, and/or the like collectively designated database clients herein after. Via the I/O interface210, one or more of the database clients may therefore provide data to the database system200for storage in the distributed database202. Via the I/O interface210, one or more of the database clients may also request the database system200to retrieve and output one or more datasets204stored in the distributed database202.

The I/O interface210may comprise one or more communication channels, interconnections, buses and/or the like such as, for example, PCI-e, InfiniBand, switch fabric Ethernet, and/or the like through which the database system200may connect to one or more close proximity storage client devices for example, an on-board device, an on-site device, and/or the like.

The I/O interface210may further comprise one or more wired and/or wireless interfaces for connecting to one or more wired and/or wireless networks, for example, Local Area Network (LAN), Wireless LAN (WLAN, e.g. Wi-Fi), Wide Area Network (WAN), Metropolitan Area Network (MAN), cellular network, the internet and/or the like. Via the network interface(s), the database system200may connect to one or more remote database client devices, systems, platforms and/or services, for example, a remote server, a cloud service, a datacenter, a remote client device (e.g., computer, Smartphone, tablet, etc.), and/or the like.

The processor(s)212, homogenous or heterogeneous, may include one or more processing nodes and/or cores arranged for parallel processing, as clusters and/or as one or more multi core processor(s). The memory214may include one or more non-transitory persistent storage devices, for example, a ROM, a Flash array, a Solid State Drive (SSD), a hard drive (HDD) and/or the like. The memory214may also include one or more volatile devices, for example, a RAM, a cache, and/or the like. The memory214may further comprise one or more local and/or remote network storage resources, for example, a storage server, a Network Attached Storage (NAS), a network drive, a cloud storage service and/or the like accessible via the I/O interface210.

The processor(s)212may execute one or more software modules, for example, a process, a script, an application, an agent, a utility, a tool, an Operating System (OS), a service, a plug-in, an add-on and/or the like each comprising a plurality of program instructions stored in a non-transitory medium (program store) such as the memory214and executed by one or more processors such as the processor(s)212.

Optionally, the processor(s)212may include, utilize and/or apply one or more hardware elements available in the database system200, for example, a circuit, a component, an Integrated Circuit (IC), a Field Programmable Gate Array (FPGA), an Application Specific Integrated Circuit (ASIC), a Digital Signals Processor (DSP), a Graphic Processing Unit (GPU), an Artificial Intelligence (AI) accelerator and/or the like.

The processor(s)212may therefore execute one or more functional modules utilized by one or more software modules, one or more of the hardware modules and/or a combination thereof. For example, the processor(s)212may execute a database manager220, interchangeably designated DBMS, for managing access to the distributed database202.

The distributed database202may comprise a plurality of partitions206allocated in the distributed database202for storing a plurality of datasets204. Specifically, the plurality of partitions206are allocated in a memory, for example, the storage clusters hosting the distributed database202.

In particular, each dataset204may be stored in one or more respective partitions206allocated specifically for the respective dataset204. This means that a respective set of partitions206is allocated for storing each dataset204where the number of partitions in each set is set according to a size of the respective dataset204it stores compared to a partition size defined for each of the plurality of partitions206. As such each partition206may either store a certain dataset and/or part thereof or it may be free and thus available for allocation to store a dataset204and/or part thereof.

Moreover, a plurality of respective partitions206allocated to store a respective dataset204may be deployed across the plurality of storage clusters such that multiple partitions206storing the respective dataset204may be accessed concurrently independently of each other such that multiple and potentially all the partitions206storing the respective dataset may be accessed simultaneously at the same time. This concurrently accessible partitions approach may be expanded to a plurality of datasets204and optionally to all datasets204stored in the distributed database202.

The datasets204stored in the distributed database202may be segmented to one or more data portions each stored in a respective partition206. Specifically, each dataset204is segmented to one or more data portions according to the size of the dataset compared to the size allocated for each partition206.

Regardless of its size, each dataset204stored in the distributed database202may comprise a primary data portion stored in a primary partition206A allocated to store the respective dataset204. Datasets204which are smaller and/or equal to the partition size may fit in a single partition206and may therefore comprise only the primary data portion stored in a respective primary partition206A.

However, datasets204which are bigger than the partition size may not fit in a single partition206and may be therefore segmented to a primary data portion stored in a respective primary partition206A allocated to store the respective dataset204and one or more additional data portions each stored in a respective secondary partition206B allocated to store the respective dataset204. The number of additional data portions of a respective dataset204may depend on its size compared to the partition size. In case a respective dataset204comprises multiple additional data portions, the additional data portions may be stored in successive secondary partitions206B.

For example, an exemplary dataset204-1stored in the distributed database202may have a size fitting in N partitions206and may be therefore segmented to N data portions, specifically a primary data portion stored in a respective primary portion206A1allocated for storing the dataset204-1and N−1 additional data portions stored in N−1 respective secondary partitions206B1(1) to206B1(N−1) allocated for storing the dataset204-1.

The partition size of each of the plurality of partitions206may be predefined, for example, 512 KB, 1 MB, 2 MB, 5 M, and/or the like according to one or more operational parameters relating to the database system200, and/or to the data, specifically the datasets stored in the distributed database202.

For example, the partition size may defined according to on one or more parameters of the database system200and/or the distributed database202, for example, storage technology, storage architecture, capacity, access speed (via the I/O interface210), and/or the like.

In another example, the partition size may be defined by one or more parameters of the datasets stored in the distributed database202, for example, a type, a typical size, a maximal size, a structure, and/or the like.

In another example, the partition size may be defined by one or more parameters of one or more client applications using the distributed database202, for example, size of data chucks typically retrieved and/or written by the client application(s) accessing the database system200, and/or the like. For example, the partition size may be defined according to the size of the datasets (entities) stored in the database, for example, columns, rows, entries, tables, and/or the like.

In another example, the parameters defining the partition size may relate to one or more performance requirements for retrieving and/or string data in the distributed database202, for example, data throughput, access latency, access concurrency, and/or the like. For example, in case high throughput and/or low latency are required, the partition size may be reduced to store the datasets in a large number of partitions stored across more concurrently accessible storage clusters thus increasing concurrency of retrieving and/or storing smaller chunks of data (dataset portions).

Each of the primary data portions and the additional data portions of each dataset204may be mapped to its primary partition206A and its secondary partitions206B respectively by respective identifiers. The identifier of each data portion of each dataset204may therefore indicate the partition in which the respective data portion is stored. For example, the identifier of the primary data portion of each dataset204may indicate the primary partition206A storing the primary data portion of the respective dataset204and the identifier of each additional data portion of the respective dataset204may map a receptive secondary partition206B in which the respective additional data portion is stored.

The identifier of the primary data portion of each dataset204may further serve as the identifier of the entire dataset204. The identifier of the primary data portion of a respective dataset204may be therefore used to query, search, identify and/or access the respective dataset204in the distributed database202.

Since the additional data portions of datasets204stored in multiple partitions206may be typically stored in successive secondary partitions206B, the identifiers of the additional data portions may be also consecutive to indicate the successive secondary partitions206B accordingly.

In order to track each dataset in the distributed database202, specifically datasets comprising multiple data portions, the primary data portion of each dataset204may comprise metadata stored in the primary partition206A in association with the respective primary data portion. The metadata associated with the respective primary data portion of each dataset204may be indicative of, for example, include the identifier of each additional data portion of the respective dataset204, if such additional data portions exist.

When accessing a respective dataset204stored in the distributed database202, the first read access may be done to retrieve the respective primary data portion of the respective dataset204together with its metadata indicative of each additional data portion of the respective dataset204and indicative of the identifier mapping of the respective additional data portion in the respective secondary partition206B. In case, based on analysis of the retrieved metadata, it is determined that the respective dataset204compromises one or more additional data portions, one or more additional read accesses may be conducted, optionally concurrently, to read the additional data portion(s) from the secondary partition(s)206B allocated for storing the receptive dataset204.

Reference is now made toFIG.3, which is a schematic illustration of exemplary datasets stored in a distributed database comprising a plurality of partitions, according to some embodiments of the present invention.

An exemplary distributed database such as the distributed database202may comprise a plurality of partitions such as the partitions206which may be allocated for storing a plurality of datasets such as the datasets204.

As described herein before, each of the datasets204stored in the distributed database202may be segmented to one or more data portions according to its size compared to the partition size, for example, 1 MB, 2 MB, 5 MB, and/or the like and stored in one or more partitions206accordingly. In particular, each dataset204may be segmented to comprise at least a primary data portion and optionally, depending on the size of the respective dataset204, zero or more additional data portions.

The primary data portion of each dataset204may be stored in a respective primary partition206A allocated for the respective dataset204and each additional data portion of the respective dataset204may be stored in respective secondary partition206B allocated for the respective dataset204, typically in successive (consecutive) order.

For example, a first dataset204-1may have a size smaller than the partition size and may be therefore stored in a single partition206. In particular, the first dataset204-1may have only a primary data portion306-1A which is stored in a respective primary partition (0)206A1.

A second exemplary dataset204-2may have a size between four and five times the partition size and may be therefore segmented to five data portions stored in five different partitions206. Specifically, the second dataset304-2may be segmented to a primary data portion306-2A and four additional data portions, a first additional data portion306-2B1, a second additional data portion306-2B2, a third additional data portion306-2B3, and a fourth additional data portion306-2B4. The primary data portion306-2A may be stored in a respective primary partition (0)206A2, the first additional data portion306-2B1may be stored in a respective secondary partition (1)206B2(1), the second additional data portion306-2B2may be stored in a respective secondary partition (2)206B2(2), the third additional data portion306-2B3may be stored in a respective secondary partition (3)206B2(3), and the fourth additional data portion306-2B4may be stored in a respective secondary partition (4)206B2(4).

A third exemplary dataset204-3may have a size between two and three times the partition size and may be therefore segmented to three portions stored in three different partitions206. Specifically, the second dataset304-3may be segmented to a primary data portion306-3A and two additional data portions, a first additional data portion306-3B1, and a second additional data portion306-3B2. The primary data portion306-3A may be stored in a respective primary partition (0)206A3, the first additional data portion306-3B1may be stored in a respective secondary partition (1)206B3(1), and the second additional data portion306-3B2may be stored in a respective secondary partition (2)206B3(2).

Each of the data portions306of each of the plurality of datasets204stored in the distributed database202may be mapped by a respective identifier (ID) to the respective partition206storing the respective data portion306. For example, the primary portion306A1of the dataset204-1may be mapped by a respective identifier set to ‘0’ to indicate the primary partition (0)206A(1).

In another example, the primary portion306-2A of the dataset204-2may be mapped by a respective identifier set to ‘0’ to indicate the primary partition (0)206A2, the first additional portion306-2B1of the dataset204-2may be mapped by a respective identifier set to ‘1’ to indicate the secondary partition (1)206B2(1), the second additional portion306-2B2of the dataset204-2may be mapped by a respective identifier set to ‘2’ to indicate the secondary partition (2)206B2(2), the third additional portion306-2B3of the dataset204-2may be mapped by a respective identifier set to ‘3’ to indicate the secondary partition (3)206B2(3), and the fourth additional portion306-2B4of the dataset204-2may be mapped by a respective identifier set to ‘4’ to indicate the secondary partition (4)206B2(4).

In another example, the primary portion306-3A of the dataset204-3may be mapped by a respective identifier set to ‘0’ to indicate the primary partition (0)206A3, the first additional portion306-3B1of the dataset204-3may be mapped by a respective identifier set to ‘1’ to indicate the secondary partition (1)206B3(1), and the second additional portion306-3B2of the dataset204-3may be mapped by a respective identifier set to ‘3’ to indicate the secondary partition (3)206B3(2).

The primary data portion306A of each dataset204may comprise, in addition to data of the respective dataset204, metadata308A stored in the respective primary partition206A in association with the respective primary data portion306A. The metadata308A may be added to the primary data portion306A of each dataset204stored in a respective primary partition206A, for example, as an additional field, an additional column, and/or the like.

The metadata308A associated with the primary data portion306A of each dataset204may be indicative of the identifiers mapping all additional data portions306B of the respective dataset204in respective one or more secondary partitions206B.

For example, the primary data portion306-1A of the dataset204-1may comprise metadata308-1A. Since the dataset204-1comprises only a single data portion, specifically the primary data portion306-1A stored in the primary partition204-1A, the metadata308-1A may indicate that the dataset204-1has no additional data portions. For example, the metadata308-1A may comprise ‘null’.

In another example, the primary data portion306-2A of the dataset204-2may comprise metadata308-2A indicative of the additional data portions of the dataset304-2which are stored in the respective secondary partitions206B2(1),206B2(2),206B2(3) and206B2(4). The metadata308-2A may therefore comprise the identifiers ‘1’, ‘2’, ‘3’ and ‘4’.

In another example, the primary data portion306-3A of the dataset204-3may comprise metadata308-3A indicative of the additional data portions of the dataset304-2which are stored in the respective secondary partitions204B2(1), and206B3(2). The metadata308-3A may therefore comprise the identifiers ‘1’ and ‘2’.

As described herein before, a different set of partitions206is stores each dataset204in the distributed database202. The identifiers mapping the partitions206storing each dataset204therefore relate only to the partitions206of the respective dataset204. Therefore, while the identifiers may hold similar values (e.g., ‘0’, ‘1’, ‘2’, etc.) for partitions206storing different datasets204, since each set of partitions206is separate from any other set of partitions206, the identifiers of partitions206relating to different datasets204are separate and do not overlap with each other.

For example, the primary data portion306-1A is mapped to its primary partition206A1by identifier ‘0’, the primary data portion306-2A is mapped to its primary partition206A2by identifier ‘0’, and the primary data portion306-3A is mapped to its primary partition206A3by identifier ‘0’. However, since the set of partitions206storing each of the primary data portions306-1A,306-2A, and306-3A is different from each other the identifiers ‘0’ mapping each of these primary data portions306-1A,306-2A, and306-3A exist in a separate range and therefore do not overlap.

In another example, the first additional data portion306-2B1is mapped to its secondary partition206B2(1) by identifier ‘1’, and first additional data portion306-3B1is mapped to its secondary partition206B3(1) by identifier ‘1’. However, the identifiers ‘1’ mapping each of these additional data portions306-2B1, and306-3B1exist in a separate range and therefore do not overlap.

Optionally, one or more of the additional data portions306B of one or more of the datasets204may also include metadata308, designated, metadata308B. However, the metadata308B of the additional data portion306B of the datasets204may be typically empty, for example, ‘null’. For example, the additional data portion306-2B1may comprise metadata308-2B1, the additional data portion306-2B2may comprise metadata308-2B2, the additional data portion306-2B3may comprise metadata308-2B3, and the additional data portion306-2B4may comprise metadata308-2B4. In another example, the additional data portion306-3B1may comprise metadata308-3B1, and the additional data portion306-3B2may comprise metadata308-3B2.

Reference is made once again toFIGS.1A-B.

For brevity, the process100is described for storing a single dataset204to the distributed database202. This however, should not be construed as limiting since the process100may be easily duplicated and/or repeated for writing a plurality of datasets204to the distributed database202.

As shown at102, the process100starts with the database manager220receiving a dataset204for storage in the distributed database202.

The write access (cycle) for storing the dataset204in the distributed database202may be conducted through one or more queries initiated by one or more database clients to the database manager220as known in the art. Each query may comprise one or more query keys which may be matched against datasets204in the distributed database202. Such queries may be received via the I/O interface210of the database system200, for example, via one or more networks, interconnections and/or the like. The database manager220may optionally respond to the query(s), when receiving it and/or when completing the write cycle, to acknowledge receipt of the query and/or to indicate a result of the query, for example, success, failure, error, status, and/or the like.

As shown at104, the database manager220may determine, based on the size of the received dataset204, whether the received dataset204comprises a single data portion or a plurality of data portions. In particular, the database manager220may determine whether the received dataset may be stored in a single partition206or does it have to be stored in multiple partitions206.

As such, in case the size of the received dataset204is smaller than the partition size defined for the distributed database202, the database manager220may determine that the received dataset204comprise only a single data portion which may be stored in a single partition206. However, in case the size of the received dataset204exceeds the partition size, the database manager220may determine that the received dataset204comprises a plurality of data portions which should be stored in a plurality of partitions206.

A shown at106, which is a conditional step, in case the received dataset204is determined to comprise a single data portion, the process may branch to108for storing the single-portion received dataset204. In case the received dataset204is determined to comprise a plurality of data portions, the process may branch to114for storing the multi-portion received dataset204.

As shown at108, since the received dataset204comprises a single data portion, the database manager220may allocate the entire received dataset in a respective primary data portion.

As shown at110, since the received dataset has no additional data portions, the database manager220may update metadata308A associated with the primary data portion of the received dataset204accordingly to indicate that the dataset204has no additional data portions.

As shown at112, the database manager220may write the primary data portion of the received dataset204together with its associated metadata in a respective primary partition206A allocated for storing the received dataset204.

As shown at114, since the received dataset comprises a plurality of data portions, the database manager220may segment the received dataset204to a plurality of data portions according to its size compared to the partition size. Specifically, the database manager220may segment the received dataset204to a respective primary data portion and one or more respective additional data portions. For example, assuming the size of a certain dataset204received for storage in the distributed database202is between three and four times the partition size defined for the distributed database202, the database manager220may segment the certain dataset204to four data portions, specifically a primary data portion to be stored in a respective primary partition and three additional data portions to be stored in three respective secondary partitions.

As shown at116, the database manager220may write each of the additional data portions of the received dataset204in a respective secondary partitions206B, typically in successive order such that in case the received dataset204comprises more than one additional data portions, these additional data portions are stored in successive secondary partitions206B.

As described herein before, each additional data portion of the received dataset204is mapped in the respective secondary partition206B by a respective identifier (ID) indicating the respective secondary partition206B. Moreover, since the additional data portions of the received dataset204may be stored in successive partitions206B, the identifiers mapping the successive secondary partitions206B may be also consecutive.

Optionally, in case the dataset204comprises a plurality of additional data portions, the database manager220may write concurrently the plurality of additional data portions in the multiple secondary partitions206B allocated for the dataset204which are concurrently accessible.

As shown at118, the database manager220may update the metadata associated with the primary data portion of the received dataset204to indicate the identifiers mapping each additional data portion in a respective secondary partition206B.

As shown at120, the database manager220may write the primary data portion of the received dataset204together with its associated metadata in the primary partition206A.

The database manager220may execute the process100for storing one or more new datasets204received for storage in the distributed database202, i.e., datasets204which are stored in the distributed database202for the first time. The database manager220may execute the process100also for storing one or more update datasets204received for storage in the distributed database202, i.e., datasets which replace corresponding datasets already stored in the distributed database202.

However, one or more steps of the process100may differ when storing an update dataset204to replace a corresponding stored dataset204compared to storing a new dataset204for the first time.

First, when storing a new dataset having only a primary data portion, the database manager220, in step112, may write the primary data portion of the new dataset204in a respective primary partition206A allocated from free partitions206of the distributed database202. In contrast, when storing in the distributed database202an update dataset having only a primary data portion, the database manager220, in step112, may write the primary data portion of the update dataset in the same primary partition206A storing the primary data portion of the stored dataset204thus overwriting and replacing the corresponding stored dataset204.

Moreover, the database manager220may execute one or more other steps of the process100differently for storing update datasets204having multiple data portions, i.e., a primary data portion and one or more additional data portions compared to execution of these steps for storing new datasets204having multiple data portion.

Specifically, when receiving a new dataset204comprising multiple data portions for store in the distributed database202, the database manager220, in step116, may write each additional data portion of the new dataset204in a respective secondary partition206B which is free and stores no data of any other dataset204. In such case, in step120, the database manager220may write the primary data portion of the new dataset204, together with its metadata indicative of the identifiers of the additional data portion(s), in a respective primary partition206A in which no data of any other dataset204is stored.

However, when receiving an update dataset204comprising multiple data portions for store in the distributed database202, the database manager220, in step116, may write each additional data portion of the update dataset204in a respective secondary partition206B different from the secondary partition206B storing an additional data portion of the corresponding stored dataset204, specifically a partition206which is free and hence not storing data of any other dataset204. The additional data portion(s) of the update dataset204therefore do not overwrite the additional data portion(s) of the corresponding stored dataset204which are thus still available in the distributed database202at their original secondary partition(s)206B.

In step118, the database manager220may update the metadata of the primary data portion of the update dataset204to indicate the identifiers mapping all additional data portions of the update dataset204to their respective secondary partition(s)206B. In such case, in step120, the database manager220may write the primary data portion of the update dataset204, together with its metadata, in the same primary partition206A storing the (old) primary data portion of the replaced dataset204to overwrite the old primary data portion.

As described herein before, the database manager220may write multiple additional data portions of a new dataset204and/or of an update dataset204concurrently in a plurality of secondary partitions206B in case the dataset204comprises multiple additional data portions.

Optionally, the database manager220may accumulate a plurality of write cycles for adding and/or updating one or more datasets204in the distributed database202. Moreover, the database manager220may accumulate the write cycles according to one or more accumulation rules and initiate the accumulated write cycles to the distributed database202when one of more of the accumulation rules are fulfilled.

The accumulation rules may define one or more criteria, conditions, and/or parameters for accumulating the write cycles received for adding and/or updating one or more datasets204in the distributed database202. For example, one or more accumulation rules may relate to timing. For example, an exemplary accumulation rule may define a certain timing for accumulating and initiating the write cycles, for example, accumulate write cycles for an hour and initiate them every round hour. In another example, one or more accumulation rules may relate to volume. For example, another exemplary accumulation rule may define a certain number of accumulated write cycles, for example, 10, 100, 1,000, and/or the like such that when the certain number of accumulated write cycles is reached, the accumulated write cycles may be initiated.

Optionally, one or more lock mechanisms, for example, Redlock, semaphore, and/or the like are may be applied for locking the distributed database202and/or part thereof when initiating the write cycles to the distributed database202. Locking the distributed database202and/or part thereof may prevent data contention and/or data corruption of one or more datasets204stored in the distributed database202as result of multiple simultaneously write accesses to the same dataset204.

Moreover, locking the distributed database202and/or part thereof may further prevent data corruption for one or more read accesses (cycles) initiated for fetching one or more datasets204stored in the distributed database202during one or more write cycles initiated for updating the same datasets204.

Optionally, the database manager220may discard the (old) additional data portions of one or more stored datasets204, replaced in the distributed database202by corresponding update datasets204, after a predefined time period, for example, 15 seconds, 30 seconds, 60 seconds, 90 seconds, and/or the like. This means that after the predefined time period following an update write cycle, the database manager220may delete (remove) the additional portion(s) of the replaced dataset204and release (de-allocate) the secondary partitions206B previously allocated for storing the old additional portion(s).

Allowing some time before discarding the data additional data portions of the replaced dataset204may be done to atomically update a dataset204stored in the distributed database202which is replaced by an update dataset204and prevent data corruption for one or more read cycles initiated for fetching one or more datasets204during the process of updating the same datasets204.

Since the additional data portion(s) of an update dataset204are not written to overwrite the corresponding (old) additional data portions of the corresponding stored dataset204replaced by the update dataset, the old additional data portions are still available for the predefined time. Therefore, a read cycle of a certain dataset initiated during an update write cycle to the same dataset204may read the primary data portion of the certain dataset before overwritten with the primary data portion of the update dataset204. The read cycle may then retrieve the additional data portion(s) of the dataset as mapped by the identifiers extracted from the metadata of the primary data portion, before these additional data portion(s) are discarded.

As such, every read cycle may retrieve a complete, coherent and uncorrupted dataset204comprising all the data portions as saved in the distributed database202prior to the update write cycle or all the data portions as saved in the distributed database202following the update write cycle.

The process150executes a read cycle for efficiently retrieving (fetching) one or more datasets204stored in the distributed database202by taking advantage of the metadata308A stored in the respective primary partition206A in association with the primary data portion306A of the respective stored dataset204.

For brevity, the process150is described for retrieving a single dataset204stored in the distributed database202. This however, should not be construed as limiting since the process150may be easily duplicated and/or repeated for reading a plurality of datasets204from the distributed database202.

As shown at152, the process150starts with the database manager220receiving a request to retrieve (read) a dataset204stored in the distributed database202.

As shown at154, the database manager220may read the primary data portion of the requested dataset204from its respective primary partition206A.

As shown at156, the metadata of the database manager220may analyze the metadata of the primary portion, which is retrieved together with the primary data portion from the respective primary partition206A, to determine whether the requested dataset204comprises one or more additional data portions.

A shown at158, which is a conditional step, in case the requested dataset204has no additional data portions, the process may branch to160and in case the requested dataset204has one or more additional data portions, the process may branch to162.

As shown at160, since the requested dataset204comprises only the primary data portion, the database manager220may output the primary data portion of the requested dataset and complete the read cycle.

As shown at162, since the requested dataset204comprises one or more additional data portions stored in one or more respective secondary partitions206B, the database manager220may read the additional data portion(s) of the requested dataset from the respective secondary partition(s)206B.

In particular, the database manager220may extract from the metadata of the primary data portion the identifier(s) mapping the additional data portion(s) to the respective secondary partition(s)206B and access the secondary partition(s)206B accordingly.

Optionally, in case the requested dataset204comprises multiple additional data portions stored in multiple secondary partitions206B, the database manager220may read concurrently the additional data portions from the multiple secondary partitions206B.

As shown at164, the database manager220may merge the primary data portion read in step154and the additional data portions read in step162to reconstruct the requested dataset and output the requested (merged) dataset204to complete the read cycle.

Read accesses for fetching datasets204from the distributed database202are typically conducted through queries initiated by one or more database clients to the database manager220as known in the art. Such queries may be received via the I/O interface210of the database system200, for example, via one or more networks, interconnections and/or the like. Each query may comprise one or more query keys which may be matched against datasets204stored in the distributed database202to identify datasets204matching the query. The database manager220may output the retrieved datasets204by responding to the queries as known in the art and transmitting the retrieved datasets204via the I/O interface210.

Reference is now made toFIG.4, which is a schematic illustration of mapping an exemplary dataset segmented across multiple partitions of a distributed database comprising a plurality of partitions, according to some embodiments of the present invention.

A distributed database such as the distributed database202may comprise a plurality of partitions such as the partitions206allocated for storing datasets such as the datasets204. The partitions206designated buckets herein after may each have a predefined size.

For example, a certain dataset204may be split into N data portions which may be stored in N buckets such that each of the N buckets may hold 1/N of the respective dataset.

As described herein before for the partitions206, the plurality of buckets may be distinct and independent of each other such that multiple and possible all buckets may be accessed concurrently. Moreover, each of the plurality of buckets may be queried using one or more query keys as known in the art.

Each dataset204may be stored in one or more buckets allocated in the distributed database202according to its size compared to the size of the buckets (partition size), specifically each dataset204may be stored in a primary bucket designated bucket 0 and one or more of a plurality of N−1 secondary buckets, designated buckets 1, 2, 3, 4, 5, 6, 7, and so on.

An identifier ‘Bucket ID’ and metadata ‘Bucket's metadata’ columns may be added to each dataset204stored in the distributed database202, specifically a metadata may be added to each data portion of each dataset204stored in one of the buckets. The ‘Bucket ID’ and metadata ‘Bucket's metadata’ columns are stored with each data portion in the same partition206as the respective data portion.

As described herein before, all datasets204have at least a single data portion, namely the primary data portion stored in a respective bucket (0). Most of the datasets204have only this single primary data portion and their ‘Bucket's metadata’ may be therefore empty (e.g., null) indicating the dataset204has not additional data portions.

Larger datasets204which require more than a single bucket for storing them in the distributed database202may comprise multiple data portions, specifically a primary data portion and one or more additional data portions as described herein before in detail. The metadata of the primary data portion of such datasets204may comprise the IDs of the additional data portions mapping the additional data portions in the secondary buckets, for example, a range of those IDs which are typically consecutive as described herein before. The ‘Bucket's metadata’ of the additional data portions may be empty (e.g., null).

A mapping table402of a certain dataset204, for example, an entry (row) stored in the distributed database202indicates that the certain dataset204comprises four data portions stored in multiple buckets of the distributed database202. Specifically mapping table402indicates that the dataset204comprises a primary data portion stored in a respective primary bucket (0), a first additional data portion stored in a respective first secondary bucket (1), a second additional data portion stored in a respective second secondary bucket (2), and a third additional data portion stored in a respective third secondary bucket (3). As seen, all of the data portions of the certain dataset204are associated with an exemplary primary query key ‘a’.

Accordingly, the metadata ‘Bucket metadata’ of the primary data portion which is also stored in the respective primary bucket (0) in association with the primary data portion may comprise identifiers (ID) mapping the three additional data portions of the certain dataset204stored in the respective secondary buckets, for example, the range of respective secondary buckets (1) to (3).

It should be noted that while the IDs of the additional data portions may be consecutive, since the primary data portion is always stored in a respective primary bucket (0), the IDs of the additional data portions may not be sequential, and may comprise, for example, IDs (0), (5), (6), (7).

Optionally, the dataset204described by the mapping table402may be associated with a compound key comprising one or more data items which may be used to track, identify, query and/or access the dataset204, for example, an account ID, a board (table) ID, a column ID, etc., and/or a combination thereof.

A read access for retrieving a dataset204from the distributed database202according to a certain query key, for example, the primary key ‘a’, may be executed, for example, by a database manager such as the database manager220executing the process150.

The database manager220may query the primary bucket ‘0’ with a query key (primary key=‘a’ AND Bucket ID=0), annotated (‘a’, 0) for brevity and retrieve the primary data portion stored in the respective primary bucket ‘0’ together with its metadata. The database manager220may analyze the metadata ‘Bucket metadata’ of the primary data portion retrieved from the bucket (0) and may determine that additional queries are required to retrieve the additional data portions of the dataset204, in this case three additional queries (‘a’, 1), (‘a’, 2), and (‘a’, 3). After retrieving the additional data portions, the database manager220may merge them with the primary data portion to reconstruct the complete dataset204and respond to the query with the merged dataset204.

When updating the dataset204stored in the database which is mapped by mapping table402with an update dataset, a process and/or an algorithm such as the process100may be initiated, for example, by the database manager220for replacing the stored (old) dataset with an update (new) dataset.

The update dataset204may be split, for example, by the database manager220, to a plurality of data portions, specifically a primary data portion and one or more additional data portions. The number of data portions of the update dataset204may not be necessarily the same as the number of data portions of the stored dataset204which is to be replaced with the update dataset. For example, while the stored dataset204has four data portions stored in the respective primary bucket and three respective secondary buckets, the update dataset204may comprise a different number of data portions for example, five data portions.

The database manager220may then find free secondary buckets which are not in use and therefore available for storing the additional data portions of the update dataset204, specifically, secondary buckets which are different from the buckets in which the additional data portions of the old dataset204are stored.

The database manager220may then write the additional data portions of the update dataset204in the respective secondary buckets identified as free and available and may map them accordingly with respective new Bucket IDs. As such, the (new) additional data portions of the update dataset204are written in different buckets from those storing the additional data portions of the old corresponding dataset204thus the new additional data portions do not overwrite the old additional data portions and both sets (new and old) of additional data portions exist at least until the old additional data portions are discarded.

After writing the additional data portions to the secondary buckets, the database manager220may write the primary data portion of the update dataset204in the primary bucket (0). Specifically, the database manager220overwrites the primary data portion of the (old) dataset204stored in the primary bucket (0) with the primary data portion of the update dataset204.

As described herein before, the database manager220may write the primary data portion of the update dataset204in the primary bucket (0) together with its metadata which is updated to indicate the new bucket IDs mapping the additional data portions of the update dataset database in the respective secondary buckets.

The new mapping of the dataset204after updated in the distributed database202are reflected in mapping table404which indicates that the updated dataset204now comprises five data portions stored in multiple buckets of the database. Specifically, the mapping table404indicates that the dataset204comprises a primary data portion stored in a respective primary bucket (0), a first additional data portion stored in a respective secondary bucket (4), a second additional data portion stored in a respective secondary bucket (5), a third additional data portion stored in a respective secondary bucket (5), and a fourth additional data portion stored in a respective secondary bucket (7). As before, all data portions of the updated dataset204are associated with the exemplary primary query key ‘a’.

Accordingly, the metadata ‘Bucket metadata’ of the primary data portion which is also stored in the respective primary bucket (0) in association with the primary data portion may comprise the IDs mapping the four additional data portions of the certain dataset204stored in the respective secondary buckets, for example, the range of secondary buckets (4) to (7).

This dataset update algorithm executed, for example, by the database manager220, is an atomic operation ensuring that read (query) accesses to any dataset204, including during the time of update, may retrieve a complete dataset204as a whole, either the complete previous dataset204as stored before the update process, or the complete new dataset204as stored after the update process.

Continuing the previous example, the algorithm may guarantee that during the multi-buckets update, every read access initiated by one or more database clients for reading the dataset204would get all the data portions from the old buckets (0, 1, 2, 3). After the update process completes, the dataset204retrieved from the new buckets (0, 4, 5. 6, 7) are available as a whole unit together, and there is therefore no race condition risk that a client may fetch incomplete data during the update process. In other words, since the new additional data portions do not overwrite the old additional data portions, every read access may fetch either the complete old dataset204, if the read is initiated before the primary portion of the new datasets204is written in the primary bucket, of the complete new dataset204, if the read is initiated after the primary portion of the new datasets204is written in the primary bucket.

During the update process until the primary data portion of the old dataset is overwritten by the new primary data portion in the primary bucket (0), every read (query) access made by a client to the database with query key ‘a’ may first retrieve the old primary data portion of the dataset204and its metadata indicating the three additional data portions stored in secondary buckets (1), (2), and (3). The read access may therefore query these three secondary buckets with the query key ‘a’ to retrieve the three additional data portions of the dataset204.

However, in case a read (query) access is made by a client to the distributed database202with query key ‘a’ after the primary data portion of the dataset204is updated in the primary bucket (0), the read access may retrieve the new primary data portion of the dataset204and its metadata indicating the four additional data portions stored in secondary buckets (4), (5), (6), and (7). The read access may therefore query these four secondary buckets with the query key ‘a’ to retrieve the four additional data portions of the dataset204.

As described herein before, the additional data portions of the replaced datasets204stored in the secondary buckets (1), (2), and (3) may be discarded after a predefined time period thus releasing the secondary buckets (1), (2), and (3) to the pool of partitions206of the distributed database202and may be used for storing one or more other datasets204.

It is expected that during the life of a patent maturing from this application many relevant systems, methods and computer programs will be developed and the scope of the terms storage unit and database are intended to include all such new technologies a priori.

As used herein the term “about” refers to ±10%.

The word “exemplary” is used herein to mean “serving as an example, an instance or an illustration”. Any embodiment described as “exemplary” is not necessarily to be construed as preferred or advantageous over other embodiments and/or to exclude the incorporation of features from other embodiments.