Search

US-12619577-B2 - Method and apparatus for free space management

US12619577B2US 12619577 B2US12619577 B2US 12619577B2US-12619577-B2

Abstract

There is provided a method and apparatus for free space management in a distributed database. Each datanode of the database is assigned a free space map to manage free space. When a datanode requires additional storage space, a new free space map may be assigned to the datanode, a free space map of a different datanode may be shared with the datanode, or a free space map of a different datanode may be reassigned to the datanode. A background process may be used to recycle inactive free space maps.

Inventors

  • Mingkun Ni
  • Ronen Grosman
  • Kelvin Ho
  • Kristian Robert LEJAO

Assignees

  • HUAWEI TECHNOLOGIES CO., LTD.

Dates

Publication Date
20260505
Application Date
20231214

Claims (20)

  1. 1 . A method for managing free space in a distributed database, comprising: issuing a request for a page from a first datanode of the distributed database; determining that the first datanode is not associated to a free space map that can fulfill the request, wherein free space maps track free space on data pages of the distributed database; selecting a free space map from a plurality of free space maps, each of the plurality of free space maps being associated to other datanodes of the distributed database; associating the selected free space map to the first datanode; responding to the request based on the selected free space map; and executing a recycling algorithm, the recycling algorithm comprising: identifying inactive free space maps within the distributed database, the inactive free space maps having a time since last access greater than a threshold; identifying active datanodes of the distributed database, the active datanodes being associated to free space maps having a time since last access less than the threshold; and associating the inactive free space maps to the active datanodes.
  2. 2 . The method of claim 1 , wherein the determining comprises finding that the first datanode is not associated to any free space map.
  3. 3 . The method of claim 1 , wherein the determining comprises finding that the first datanode is associated to a free space map which is full.
  4. 4 . The method of claim 1 , wherein the selecting comprises: finding that none of the other datanodes is associated to multiple free space maps; choosing a second datanode randomly from the other datanodes; wherein the selected free space map is associated to the second data node.
  5. 5 . The method of claim 1 , wherein the selecting comprises: finding that at least one of the other datanodes is associated to multiple free space maps; choosing a second datanode from the other datanodes, the second datanode being associated to a highest number of free space maps; wherein the selected free space map is a free space map associated the second datanode having an earliest time of last access.
  6. 6 . The method of claim 5 , further comprising disassociating the selected free space map from the second datanode.
  7. 7 . The method of claim 1 , the recycling algorithm further comprising: sorting inactive free space maps by number of pages owned by each of the inactive free space maps; sorting the active datanodes by number of pages owned by free space maps associated to each of the active datanodes; selecting a current datanode of the active datanodes, wherein the current datanode has the most pages of the active datanodes; wherein the associating comprises associating a free space map with the most pages of the inactive free space maps with the current datanode.
  8. 8 . The method of claim 7 , the recycling algorithm further comprising: determining that a maximum number of free space maps have been assigned to the current datanode; and changing the current datanode to the next datanode with the most pages of the active datanodes.
  9. 9 . The method of claim 8 , wherein the maximum number is proportional to a number of pages of the current datanode.
  10. 10 . The method of claim 1 , wherein the recycling algorithm is executed as a background thread.
  11. 11 . The method of claim 1 , wherein the recycling algorithm is executed periodically or continually.
  12. 12 . A computing device for managing free space in a distributed database, comprising: a processor; and memory; wherein the computing device is configured to: issue a request for a page from a first datanode of the distributed database; determine that the first datanode is not associated to a free space map that can fulfill the request, wherein free space maps track free space on data pages of the distributed database; select a free space map from a plurality of free space maps, each of the plurality of free space maps being associated to other datanodes of the distributed database; associate the selected free space map to the first datanode; respond to the request based on the selected free space map; and execute a recycling algorithm, the recycling algorithm comprising: identifying inactive free space maps within the distributed database, the inactive free space maps having a time since last access greater than a threshold; identifying active datanodes of the distributed database, the active datanodes being associated to free space maps having a time since last access less than the threshold; and associating the inactive free space maps to the active datanodes.
  13. 13 . The computing device of claim 12 , wherein the determining comprises finding that the first datanode is not associated to any free space map.
  14. 14 . The computing device of claim 12 , wherein the determining comprises finding that the first datanode is associated to a free space map which is full.
  15. 15 . The computing device of claim 12 , wherein the selecting comprises: finding that none of the other datanodes is associated to multiple free space maps; choosing a second datanode randomly from the other datanodes; wherein the selected free space map is associated to the second data node.
  16. 16 . The computing device of claim 12 , wherein the selecting comprises: finding that at least one of the other datanodes is associated to multiple free space maps; choosing a second datanode from the other datanodes, the second datanode being associated to a highest number of free space maps; wherein the selected free space map is a free space map associated the second datanode having an earliest time of last access.
  17. 17 . The computing device of claim 12 , further configured to disassociate the selected free space map from the second datanode.
  18. 18 . The computing device of claim 12 , the recycling algorithm further comprising: sorting inactive free space maps by number of pages owned by each of the inactive free space maps; sorting the active datanodes by number of pages owned by free space maps associated to each of the active datanodes; selecting a current datanode of the active datanodes, wherein the current datanode has the most pages of the active datanodes; wherein the associating comprises associating a free space map with the most pages of the inactive free space maps with the current datanode.
  19. 19 . The computing device of claim 18 , the recycling algorithm further comprising: determining that a maximum number of free space maps have been assigned to the current datanode; and changing the current datanode to the next datanode with the most pages of the active datanodes.
  20. 20 . The computing device of claim 19 , wherein the maximum number is proportional to a number of pages of the current datanode.

Description

OTHER APPLICATIONS The present application is the first application for this disclosure. TECHNICAL FIELD The present disclosure relates to free space management. Specifically, the present disclosure relates to a method of managing free space allocations in a multi-datanode database. BACKGROUND Multi-datanode databases conventionally use one of two architectures for data management, namely the shared-nothing architecture and the shared-everything architecture. In a shared-nothing architecture, each data node may modify its own independent set of files on disk without any negotiations with other nodes. In contrast, in a shared-everything architecture, each data node shares an allocation table with the other nodes. While this requires data nodes to negotiate with other nodes when making modifications, it also allows each data node to access any file within the database. SUMMARY It is an object of the present disclosure to provide a method for distributed free space management in a database. According to a first aspect, there is provided a method for managing free space in a distributed database, comprising issuing a request for a page from a first datanode of the distributed database, determining that the first datanode is not associated to a free space map that can fulfill the request, selecting a free space map from a plurality of free space maps from other datanodes of the distributed database, associating the selected free space map to the first datanode, and responding to the request based on the selected free space map. According to another aspect, there is provided a computing device for managing free space in a distributed database, comprising a processor and memory, wherein the computing device is configured to issue a request for a page from a first datanode of the distributed database, determine that the first datanode is not associated to a free space map that can fulfill the request, select a free space map from a plurality of free space maps from other datanodes of the distributed database, associate the selected free space map to the first datanode, and respond to the request based on the selected free space map. According to yet another aspect, there is provided a computer readable medium having stored thereon executable code for execution by a processor of a computing device, the executable code comprising instructions for issuing a request for a page from a first datanode of the distributed database, determining that the first datanode is not associated to a free space map that can fulfill the request, selecting a free space map from a plurality of free space maps from other datanodes of the distributed database, associating the selected free space map to the first datanode, and responding to the request based on the selected free space map. BRIEF DESCRIPTION OF THE DRAWINGS The present disclosure will be better understood with reference to the drawings in which: FIG. 1 is a graphical representation of a shared-nothing architecture. FIG. 2 is a graphical representation of a shared-everything architecture. FIG. 3 is a graphical representation of multiple Free Space Maps (FSMs) according to at least some embodiments of the present disclosure. FIG. 4 is a block diagram of a method for assigning FSMs according to at least some embodiments of the present disclosure. FIG. 5 is a graphical representation of a reassignment of an FSM according to at least some embodiments of the present disclosure. FIG. 6 is a graphical representation of a reassignment of an FSM according to at least some embodiments of the present disclosure. FIG. 7 is a block diagram of a method for recycling FSMs according to at least some embodiments of the present disclosure. FIG. 8 is a performance graph of a conventional distributed database. FIG. 9 is a performance graph of a distributed database according to an embodiment of the present disclosure. FIG. 10 is a bar graph comparing performance between a conventional distributed database and a database according to an embodiment of the present disclosure. FIG. 11 is a block diagram of an exemplary computing device for implementing embodiments of the present disclosure. DETAILED DESCRIPTION The present disclosure is directed to a method and apparatus for distributed free space management in a database. Throughout this disclosure, the present terms are given the following definitions. Free Space Management: system in a database providing a lookup for pages with free space. Datanode: A machine or host in a multi-node database architecture that has access to the on-disk database files for reading and writing. Coordinator Node: A machine or host in a multi-node database architecture that manages query parsing and distribution and controls transaction progress. Transactions Per Minute (TPMC): A performance index used in the Transaction Processing Performance Council Benchmark C (TPC-C) test, which is a widely used method to evaluate the performance of distributed database systems. A