Systems and methods for maintaining distributed data
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-007/00
G06F-017/30
출원번호
US-0862060
(2010-08-24)
등록번호
US-8214400
(2012-07-03)
발명자
/ 주소
Fachan, Neal T.
Passey, Aaron J.
Schack, Darren P.
출원인 / 주소
EMC Corporation
대리인 / 주소
Knobbe Martens Olson & Bear LLP
인용정보
피인용 횟수 :
4인용 특허 :
232
초록▼
Systems and methods are disclosed that provide an indexing data structure. In one embodiment, the indexing data structure is mirrored index tree where the copies of the nodes of the tree are stored across devices in a distributed system. In one embodiment, nodes that are stored on an offline device
Systems and methods are disclosed that provide an indexing data structure. In one embodiment, the indexing data structure is mirrored index tree where the copies of the nodes of the tree are stored across devices in a distributed system. In one embodiment, nodes that are stored on an offline device are restored, and an offline device that comes back online is merged into the distributed system and given access to the current indexing data structure. In one embodiment, the indexing data structure is traversed to locate and restore nodes that are stored on offline devices of the distributed system.
대표청구항▼
1. A computer-implemented method of accessing a data unit stored at a leaf node of a distributed index tree, the method comprising: using a reference from a superblock to access an available copy of a root node, copies of the root node stored on different devices among a plurality of storage devices
1. A computer-implemented method of accessing a data unit stored at a leaf node of a distributed index tree, the method comprising: using a reference from a superblock to access an available copy of a root node, copies of the root node stored on different devices among a plurality of storage devices, each copy of the root node comprising a first reference to a first copy of a branch of the distributed index tree and a second reference to a second copy of the branch, wherein the branch leads to one or more copies of a parent node;accessing, by a computer processor, an available copy of the parent node, copies of the parent node stored on different devices among the plurality of storage devices, each copy of the parent node comprising a first electronic reference to a first copy of a leaf node stored on a first storage device, a second electronic reference to a second copy of the leaf node stored on a second storage device, and a third electronic reference to a third copy of the leaf node stored on a third storage device, the first storage device different from the second storage device;determining, by a computer processor, that the first storage device is unavailable;based on the determination that the first storage device is unavailable, choosing to access the second copy of the child node instead of the third copy of the child node based on a technique including at least one of a round robin technique based on the last storage device used, selecting a most recently used storage device, and choosing based on a preference of local storage devices over remote storage devices; andprocessing, by a computer processor, the second electronic reference to access the second copy of the leaf node stored on the second storage device. 2. The computer-implemented method of claim 1, further comprising: maintaining at least as many copies of the parent node as the maximum number of copies of any of its one or more children, wherein the one or more children of the parent node include the leaf node. 3. The computer-implemented method of claim 1, further comprising: creating a third copy of the leaf node;storing the third copy of the leaf node on a third storage device which is different than the first storage device and the second storage device; andmodifying each available copy of the parent node to include a reference to the third copy of the leaf node stored on the third storage device. 4. The computer-implemented method of claim 1, further comprising determining that a first copy of the parent node is stored on an unavailable device, and wherein accessing the available copy of the parent node comprises using a reference to a second copy of the parent node, the reference stored in a parent of the parent node. 5. The computer-implemented method of claim 1, further comprising maintaining a copy of the superblock on each of the plurality of storage devices. 6. The computer-implemented method of claim 5, further comprising maintaining an indication of a version of the superblock on each of the plurality of storage devices. 7. The computer-implemented method of claim 1, wherein the parent node and the leaf node each comprise one or more keys, and the data unit is associated with an index which corresponds to one of the one or more keys of the leaf node. 8. The computer-implemented method of claim 1, wherein the parent node is the root node. 9. The computer-implemented method of claim 1, wherein the data unit comprises a physical address. 10. The computer-implemented method of claim 1, wherein the data unit comprises at least one of a database record, a physical address, content data, and metadata. 11. The computer-implemented method of claim 1, wherein the distributed indexed tree is implemented using at least one of a balanced tree, a hash table and a linked list. 12. A system for accessing a data unit stored in a distributed index tree comprising: one or more computer processors;at least one computer memory accessible by at least one of the one or more computer processors; anda computing component comprising an executable software module executed by the one or more computer processors, wherein the computing component is operable to: use a reference from a superblock to access an available copy of a root node, copies of the root node stored on different devices among a plurality of storage devices, each copy of the root node comprising a first reference to a first copy of a branch of the distributed index tree and a second reference to a second copy of the branch, wherein the branch leads to one or more copies of a parent node;access an available copy of the parent node, copies of the parent node stored on different devices among the plurality of storage devices, each copy of the parent node comprising a first electronic reference to a first copy of a leaf node stored on a first storage device, a second electronic reference to a second copy of the leaf node stored on a second storage device, and a third electronic reference to a third copy of the leaf node stored on a third storage device, the first storage device different from the second storage device;determine that the first storage device is unavailable;based on the determination that the first storage device is unavailable, choose to access the second copy of the child node instead of the third copy of the child node based on a technique including at least one of a round robin technique based on the last storage device used, selecting a most recently used storage device, and choosing based on a preference of local storage devices over remote storage devices; andprocess the second electronic reference to access the second copy of the leaf node stored on the second storage device. 13. The system of claim 12, wherein the computing component is further operable to maintain at least as many copies of the parent node as the maximum number of copies of any of its one or more children, wherein the one or more children of the parent node include the leaf node. 14. The system of claim 12, wherein the computing component is further operable to: create a third copy of the leaf node;store the third copy of the leaf node on a third storage device which is different than the first storage device and the second storage device; andmodify each available copy of the parent node to include a reference to the third copy of the leaf node stored on the third storage device. 15. The system of claim 12, wherein the computing component is further operable to determine that a first copy of the parent node is stored on an unavailable device, and wherein accessing the available copy of the parent node comprises using a reference to a second copy of the parent node, the reference stored in a parent of the parent node. 16. The system of claim 12, wherein the computing component is further operable to maintain a copy of the superblock on each of the plurality of storage devices. 17. The system of claim 16, wherein the computing component is further operable to maintain an indication of a version of the superblock on each of the plurality of storage devices. 18. The system of claim 12, wherein the parent node and the leaf node each comprise one or more keys, and the data unit is associated with an index which corresponds to one of the one or more keys of the leaf node. 19. The system of claim 12, wherein the parent node is the root node. 20. The system of claim 12, wherein the data unit comprises at least one of a database record, a physical address, content data, and metadata.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (232)
McGoveran,David O., Adaptive transaction manager for complex transactions and business process.
Stirpe Paul Alan ; Verma Dinesh Chandra ; Nadas Stephen Joseph ; Gupta Manish ; Hervatic Elizabeth A., Automatic reconfiguration of multipoint communication channels.
Alverson, Gail A.; Callahan, II, Charles David; Kahan, Simon H.; Koblenz, Brian D.; Porterfield, Allan; Smith, Burton J., Detecting access to a memory location in a multithreaded environment.
Watanabe Naoki,JPX ; Kakuta Hitoshi,JPX ; Takamoto Yoshifumi,JPX, Disk array system having adjustable parity group sizes based on storage unit capacities.
Smith Robert M. (Andover MA) Ting David M. T. (Sudbury MA) Boer Jan H. (Lexington MA) Mendelssohn Marvin (Melrose MA), Document management and production system.
Leblang David B. (Wayland MA) Allen Larry W. (Cambridge MA) Chase ; Jr. Robert P. (Newton MA) Douros Bryan P. (Framingham MA) Jabs David E. (Sudbury MA) McLean ; Jr. Gordon D. (Brookline MA) Minard D, Dynamic rule-based version control system.
Solter,Nicholas A.; Kong,Wei; Rao,Anil; Tripathi,Ashutosh, Facilitating event notification through use of an inverse mapping structure for subset determination.
Napolitano Richard ; Silverman Herbert W. ; Juzsczak Chester ; Panner Bryan K. ; Franklin Chris ; Noya Eric S. ; Hoskins Timothy Lee ; Luke Stanley ; Shaughnessy Paul Richard ; McLeod Alexander C. ; , File array storage architecture having file system distributed across a data processing platform.
Belsan Jay S. (Nederland CO) Laughlin Jeffrey S. (Nederland CO) Pedersen Mogens H. (Longmont CO) Raicer Robert J. (Niwot CO) Rudeseal George A. (Boulder CO) Schafer Charles P. (Louisville CO) Steele , File server having snapshot application data groups.
Akizawa Mitsuru (Hachioji JPX) Yamashita Hirofumi (Yokohama JPX) Kawaguchi Hisamitsu (Sagamihara JPX) Tada Katsumi (Yokohama JPX) Kato Kanji (Yokohama JPX) Kito Akira (Ebina JPX) Yamada Hidenori (Had, File server system and file access control method of the same.
Christensen Steve W. ; Dasher John M. ; Martherus Robin E., File wrapper containing cataloging information for content searching across multiple platforms.
Nunnelley Lewis L. (San Jose CA) Williams Larry L. (Los Altos CA) Wood ; Jr. Leighton C. (Morgan Hill CA), High capacity data storage system using disk array.
Calvignac Jean (La Gaude FRX) Saint Georges Eric (La Gaude FRX) Orsatti Daniel (Cagnes sur Mer FRX) Toubol Gilles (Villeneuve Loubet FRX) Verplanken Fabrice (Le Haute de Cagnes FRX) Nicolas Francois , Hybrid switching system for a communication node.
Perycz,Krzysztof S.; Iwanojko,Bohdan T.; Kamiński,Adam; Kogut,Jaroslaw; Oriol,Mariusz; Przekop,Zbigniew, Initialization, reconfiguration, and shut down of a module function.
Lincoln, Patrick D.; Dawson, Steven M.; Samarati, Pierangela; De Capitani di Vimercati, Sabrina, Lattice-based security classification system and method.
Humlicek, Donald R.; DeKoning, Rodney A.; Delaney, William P., Managing a snapshot volume or one or more checkpoint volumes with multiple point-in-time images in a single repository.
Cabrera Luis Felipe ; Long Darrell Don Earl, Method and apparatus for establishing and maintaining the status of membership sets used in mirrored read and write inpu.
Gondi, Albert C.; Klein, Johannes; de Roo, John S.; Lanka, Sitaram V.; Sripada, Ramprasad K. L., Method and apparatus for handling failures of resource managers in a clustered environment.
Philip E. Tamer ; Terry Seto Lee, Method and apparatus for identifying changes to a logical object based on changes to the logical object at physical level.
Liu,Yu Jih; Visvader,Joseph John; Schnabel,Jon William, Method and apparatus for on demand multicast and unicast using controlled flood multicast communications.
Matthew J. D'Errico ; Steven M. Blumenau ; Erez Ofer, Method and apparatus for providing a host computer with information relating to the mapping of logical volumes within an intelligent storage system.
Bond Milton F. (Rochester MN) Clark Brian E. (Rochester MN) McRoberts Raymond S. (Rochester MN), Method and apparatus for recovering parity protected data.
Fagen Scott Andrew ; Frey Jeffrey Alan ; Fulkerson ; Jr. Carroll Eugene ; Kowalski Mark Albert ; North Benjamin John,IEX, Method and apparatus for serializing resource access requests in a multisystem complex.
Menon Jaishankar M. (San Jose CA) Mattson Richard L. (San Jose CA) Ng Spencer W. (San Jose CA), Method and means for distributed sparing in DASD arrays.
Huffman,William A.; Anderson,Michael L.; Thorson,Gregory M.; Garcia,Susan; Kunkel,Daniel L., Method and system for covering multiple resourcces with a single credit in a computer system.
Litwin Witold,FRX ; Menon Jaishankar Moothedath ; Risch Tore Johan Martin,SEX, Method and system for data recovery using a distributed and scalable data structure.
Brent Cameron Beardsley ; Michael Thomas Benhase ; Douglas A. Martin ; Robert Louis Morton ; Kenneth Wayne Todd, Method and system for managing meta data.
Frey ; Jr. Alexander H. (Pasadena CA) Mosteller Richard C. (Sierra Madre CA), Method for balancing of distributed tree file structures in parallel computing systems to enable recovery after a failur.
Stallmo David C. ; Hall Randy K., Method for organizing storage devices of unequal storage capacity and distributing data using different raid formats depending on size of rectangles containing sets of the storage devices.
Gentry Timothy W. (Wichita KS) Fredin Gerald J. (Wichita KS) Riedl Daniel A. (Andover KS), Method for partitioning disk drives within a physical disk array and selectively assigning disk drive partitions into a.
Burton, David Alan; Morton, Robert Louis, Method, system, program, and data structures for mapping logical units to a storage space comprises of at least one array of storage units.
Bingham, Scott Forrest; Buchman, Matthew D.; Singhal, Upanshu; Rokicki, John C.; Murthy, Venkatesha, Mirrored storage architecture using continuous data protection techniques.
Marcelo Weinberger ; Tomas G. Rokicki ; Gadiel Seroussi ; Rajiv Gupta ; Neri Merhav IL; Joesp M. Ferrandiz, Optimizing computer performance by using data compression principles to minimize a loss function.
Row Edward J. (Mountain View CA) Boucher Laurence B. (Saratoga CA) Pitts William M. (Los Altos CA) Blightman Stephen E. (San Jose CA), Parallel I/O network file server architecture.
Popelka Paul ; Tripathy Tarun Kumar ; Walter Richard Allen ; Del Fante Paul Brian ; Repakula Murali Sundaramoorthy ; Narayanaswamy Lakshman ; Sterk Donald Wayne ; Bodas Amod Prabhakar ; McCutcheon Le, Processing system with dynamically allocatable buffer memory.
Hinshaw, Foster D.; Meyers, David L.; Zane, Barry M., Programmable streaming data processor for database appliance having multiple processing unit groups.
Blackmon, Herman Lee; Drehmel, Robert Allen; Haselhorst, Kent Harold; Marcella, James Anthony, Reordering and flushing commands in a computer memory subsystem.
Bauer,Andreas L.; Gruttadauria,Brian R.; Lazar,Gregory W.; Dobberpuhl,Walter T., Scalable communication within a distributed system using dynamic communication trees.
Rafert,James Lee; Martin,Marcia R.; Abramovitz,Michael Paul, Storage backup system for backing up data written to a primary storage device to multiple virtual mirrors using a reconciliation process that reflects the changing state of the primary storage device.
Manley,Stephen L.; Owara,Shane S., System and method for asynchronous mirroring of snapshots at a destination using a purgatory directory and inode mapping.
Benson Max L. ; Morais Dinarte ; Norin Scott ; Champion William P. ; Fakes Thomas F. ; Joshi Milind M., System and method for incremental change synchronization between multiple copies of data.
Heil Thomas F. ; Francis Martin H. ; DeKoning Rodney A. ; Weber Bret S., System and method for peer-to-peer accelerated I/O shipping between host bus adapters in clustered computer network.
Kekre,Anand A.; Pendbarkar,Niranjan S., System and method for recording the order of a change caused by restoring a primary volume during ongoing replication of the primary volume.
Mark S. Day ; Donald J. Brady ; Deric S. Horn, System and method for storing and retrieving filenames and files in computer memory using multiple encodings.
Zayas, Edward R.; Haynes, Thomas; Gillono, John Francis; Kahn, Andy C., System and method for verifying and restoring the consistency of inode to pathname mappings in a filesystem.
Patel, Sujal M.; Mikesell, Paul A., System and methods for providing a distributed file system utilizing metadata to track information about data stored throughout the system.
Klein Johannes (San Francisco CA) Lutgardo Alberto (Santa Clara CA) Chang Edward Y. (Santa Clara CA) Cheng Edward C. (S. San Francisco CA) Lee Dora L. (San Francisco CA) Lu Edward S. (San Bruno CA), System for distributed computation processing includes dynamic assignment of predicates to define interdependencies.
Bertin Olivier (Nice FRX) Chobert Jean-Paul (Carros FRX) Pruvost Alain (Valauris FRX), System for managing topology of a network in spanning tree data structure by maintaining link table and parent table in.
Anderson, Robert J.; Fachan, Neal T.; Husted, Justin M.; Lemar, Eric M.; Passey, Aaron J.; Schack, Darren P., Systems and methods for a snapshot of data.
Anderson, Robert J.; Fachan, Neal T.; Lemar, Eric M.; Passey, Aaron J.; Richards, David W.; Schack, Darren P., Systems and methods for a snapshot of data.
Anderson, Robert J.; Fachan, Neal T.; Lemar, Eric M.; Passey, Aaron J.; Richards, David W.; Schack, Darren P., Systems and methods for a snapshot of data.
Passey, Aaron J.; Schack, Darren P.; Godman, Peter J.; Anderson, Robert J.; Fachan, Neal T., Systems and methods for accessing and updating distributed data.
Patel,Sujal M.; Mikesell,Paul A.; Schack,Darren P.; Passey,Aaron J., Systems and methods for providing a distributed file system incorporating a virtual hot spare.
Patel, Sujal M.; Mikesell, Paul A.; Schack, Darren P., Systems and methods for providing a distributed file system utilizing metadata to track information about data stored throughout the system.
Mikesell, Paul A.; Anderson, Rob; Passey, Aaron James; Godman, Peter John; Khan, Hassan F.; Schack, Darren P., Systems and methods for restriping files in a distributed file system.
Akidau, Tyler Arthur; Dire, Nate E.; Fachan, Neal T.; Godman, Peter J.; Loafman, Zachary M., Systems and methods of managing resource utilization on a threaded computer system.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.