Spatial-temporal storage system, method, and recording medium

• US 10,108,637 B2
• Filed: 03/08/2016
• Issued: 10/23/2018
• Est. Priority Date: 03/08/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ganti, Raghu Kiran, Li, Shen, Srivatsa, Mudhakar
• Primary Examiner(s): Burke, Jeffrey A
• Assistant Examiner(s): Vu, Thong
• Application Number:
  US15/064,161
• Publication Number:
  US 20170262469A1
• Time in Patent Office: 959 Days
• Field of Search: 707622, 707639, 707746, 707784, 707709, 707722
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

A spatial-temporal storage method, system, and non-transitory computer readable medium, include, in a first layer, a geometric translation circuit configured to split spatial-temporal information into row keys and translate a geometry query into a range scan, and a multi-scan optimization circuit configured to compute an optimal read strategy to optimize the range scan translated by the geometric translation circuit into a series of block starting offsets and block sizes, and, in a second layer, a block grouping circuit configured to allow grouping of blocks in the second layer while preserving spatial data locality when splits of spatial-temporal information occur in the first layer.

Claims

1. A spatial-temporal storage system, comprising:

in a first layer,

a geometric translation circuit configured to split spatial-temporal information representing different geometric regions and respective servers into row keys and translate a geometry query into a range scan; and

a multi-scan optimization circuit configured to compute an optimal read strategy to optimize the range scan translated by the geometric translation circuit into a series of block starting offsets and block sizes; and

in a second layer,

a block grouping circuit configured to allow grouping of blocks in the second layer while preserving spatial data locality when splits of spatial-temporal information occur in the first layer,

wherein, in the second layer, the block grouping circuit groups spatial-temporal information such that data corresponding to a first group in a first server is replicated to create a replica and the replica is placed in a second group in a second server where the replicas of a same group are stored in a same physical server at the second server, and

wherein, when retrieving the split spatial-temporal information for a moving hotspot in the second layer, the block grouping circuit splits the replica into multiple daughters on different physical servers at the second server to make use of resources on the different physical servers.

2. The system of claim 1, further comprising, in the first layer, a determination circuit configured to determine if the optimal read strategy is greater than a predetermined threshold.

3. The system of claim 1, wherein the block grouping circuit specifies replica groups when writing data into the second layer, and

wherein replicas in a same group are placed into a same data node.

4. The system of claim 3, wherein block sizes are made by the multi-scan optimization circuit to respect splits such that a daughter region server including one of the multiple daughters is moved into a remote physical server.

5. The system of claim 1, wherein the block grouping circuit groups the blocks by replicating the blocks a predetermined number of times according to a predefined number of spit keys within a given region.

6. The system of claim 1, wherein the spatial-temporal information is split so as to have uniform density in a first server and a second server.

7. A non-transitory computer-readable recording medium recording a spatial-temporal storage program, the program causing a computer to perform:

in a first layer,

splitting spatial-temporal information into row keys and translating a geometry query into a range scan; and

computing an optimal read strategy to optimize the range scan translated by the translating into a series of block starting offsets and block sizes; and

in a second layer,

grouping of blocks in the second layer while preserving spatial data locality when splits of spatial-temporal information occur in the first layer,

wherein the second layer, the grouping groups spatial-temporal information such that data corresponding to a first group in a first server is replicated to create a replica and the replica is placed in a second group in a second server where the replicas of a same group are stored in a same physical server at the second server, and

wherein, when retrieving the split spatial-temporal information for moving hotspot in the second layer, the group spits the replica into multiple daughters on different physical servers at the second server to make use of resources on the different physical servers.

8. The non-transitory computer-readable recording medium of claim 7, further comprising, in the first layer, determining if the optimal read strategy is greater than a predetermined threshold.

9. The non-transitory computer-readable recording medium of claim 7, wherein the grouping specifies replica groups when writing data into the second layer, and

wherein replicas in a same group are placed into a same data node.

10. The non-transitory computer-readable recording medium of claim 9, wherein block sizes are made by the computing to respect splits such that a daughter region server including one of the multiple daughters is moved into a remote physical server.

11. The non-transitory computer-readable recording medium of claim 7, wherein the grouping groups the blocks by replicating the blocks a predetermined number of times according to a predefined number of spit keys within a given region.

12. A spatial-temporal storage method, comprising:

in a first layer,

splitting spatial-temporal information into row keys and translating a geometry query into a range scan; and

computing an optimal read strategy to optimize the range scan translated by the translating into a series of block starting offsets and block sizes; and

in a second layer,

grouping of blocks in the second layer while preserving spatial data locality when splits of spatial-temporal information occur in the first layer,

wherein, in the second layer, the grouping groups spatial-temporal information such that data corresponding to a first group in a first server is replicated to create a replica and the replica is placed in a second group in a second server where the replicas of a same group are stored in a same physical server at the second server, and

wherein, when retrieving the split spatial-temporal information for a moving hotspot in the second layer, the grouping splits the replica into multiple daughters on different physical servers at the second server to make use of resources on the different physical servers.

13. The method of claim 12, further comprising, in the first layer, determining if the optimal read strategy is greater than a predetermined threshold.

14. The method of claim 12, wherein the grouping specifies replica groups when writing data into the second layer, and

wherein replicas in a same group are placed into a same data node.

15. The method of claim 14, wherein block sizes are made by the computing to respect splits such that a daughter region server including one of the multiple daughters is moved into a remote physical server.

16. The method of claim 12, wherein the grouping groups the blocks by replicating the blocks a predetermined number of times according to a predefined number of spit keys within a given region.

17. The method of claim 12, wherein, the spatial-temporal information is split so as to have uniform density in a first server and a second server.