[go: up one dir, main page]

RU2015139057A - Способ и система распределенного хранения данных - Google Patents

Способ и система распределенного хранения данных Download PDF

Info

Publication number
RU2015139057A
RU2015139057A RU2015139057A RU2015139057A RU2015139057A RU 2015139057 A RU2015139057 A RU 2015139057A RU 2015139057 A RU2015139057 A RU 2015139057A RU 2015139057 A RU2015139057 A RU 2015139057A RU 2015139057 A RU2015139057 A RU 2015139057A
Authority
RU
Russia
Prior art keywords
search
tree
data storage
search tree
elements
Prior art date
Application number
RU2015139057A
Other languages
English (en)
Inventor
Михаил ДАНИЛОВ
Михаил МАЛЫГИН
Иван ЧУБ
Андрей ФОМИН
Максим ТРУСОВ
Чэнь ВАН
Шашват СРИВАСТАВ
Original Assignee
ИЭмСи КОРПОРЕЙШН
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by ИЭмСи КОРПОРЕЙШН filed Critical ИЭмСи КОРПОРЕЙШН
Priority to RU2015139057A priority Critical patent/RU2015139057A/ru
Priority to US15/083,324 priority patent/US10402316B2/en
Publication of RU2015139057A publication Critical patent/RU2015139057A/ru

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0253—Garbage collection, i.e. reclamation of unreferenced memory
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0238—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
    • G06F12/0246—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory in block erasable memory, e.g. flash memory
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/23—Updating
    • G06F16/2308—Concurrency control
    • G06F16/2315—Optimistic concurrency control
    • G06F16/2329—Optimistic concurrency control using versioning

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Claims (40)

1. Способ распределенного хранения данных, включающий:
выделение одного или нескольких деревьев поиска, подлежащих отслеживанию, причем деревья поиска содержат указатели на один или несколько элементов дерева;
выделение одной или нескольких подходящих секций хранения, каждая из которых: соответствует памяти, выделенной на соответствующем устройстве хранения данных, содержит один или несколько элементов деревьев и отмечена как закрытая;
обход деревьев поиска для нахождения элементов деревьев, на которые на текущий момент времени имеются указатели;
указание тех подходящих секций хранения, которые не содержат элементы деревьев, на которые имеются указатели, как секции хранения, содержащие "мусор"; и
для одной или нескольких секций хранения, содержащих "мусор", освобождение соответствующей памяти, выделенной в соответствующем устройстве хранения данных.
2. Способ по 1, включающий также:
сохранение точки восстановления;
приостановку обхода деревьев поиска;
определение первого из элементов дерева поиска, с которого необходимо возобновлять обход, в соответствии с точкой восстановления; и
возобновление обхода деревьев поиска с указанного первого элемента дерева.
3. Способ по п. 2, в котором приостановка обхода деревьев поиска включает приостановку обхода в связи с обновлением дерева поиска.
4. Способ по п. 3, в котором приостановка обхода деревьев поиска включает приостановку обхода в связи с обновлением журнала дерева поиска.
5. Способ по п. 2, в котором сохранение точки восстановления включает сохранение информации о последнем обходимом элементе дерева поиска.
6. Способ по п. 5, в котором сохранение информации о последнем обходимом элементе дерева поиска включает сохранение ключа поиска, связанного с этим элементом.
7. Способ по п. 6, в котором определение первого из элементов дерева поиска, с которого необходимо возобновлять обход, включает определение первого из элементов дерева поиска, с которого необходимо возобновлять обход, в соответствии с ключом поиска, связанным с последним обходимым элементом дерева поиска.
8. Способ по п. 7, в котором определение первого из элементов дерева поиска, с которого необходимо возобновлять обход, включает нахождение элемента дерева поиска, расположенного слева от последнего обходимого элемента дерева поиска.
9. Способ по п. 2, в котором сохранение точки восстановления включает ее сохранение в устройстве хранения данных, совместно используемом первым и вторым узлами кластера хранения, причем приостановка обхода деревьев поиска выполняется первым узлом хранения, а возобновление обхода деревьев поиска выполняется вторым узлом хранения.
10. Способ по п. 9, в котором приостановка обхода деревьев поиска включает выявление изменения принадлежности дерева.
11. Распределенная система хранения данных, содержащая:
множество устройств хранения данных;
два или более узлов хранения данных, каждый из которых содержит модуль деревьев поиска, сконфигурированный для:
выделения одного или нескольких деревьев поиска, подлежащих отслеживанию, причем деревья поиска содержат указатели на один или несколько элементов дерева;
выделения одной или нескольких подходящих секций хранения данных, каждая из которых соответствует памяти, выделенной на соответствующем устройстве хранения данных, содержит один или несколько элементов деревьев и отмечена как закрытая;
обхода деревьев поиска для нахождения элементов деревьев, на которые на текущий момент времени имеются указатели;
указания тех подходящих секций хранения, которые не содержат элементы деревьев, на которые имеются указатели, как секции, содержащие "мусор"; и
для одной или нескольких секций хранения, содержащих "мусор", освобождения соответствующей памяти, выделенной в соответствующем устройстве хранения данных.
12. Распределенная система хранения данных по п. 11, в которой модули деревьев поиска сконфигурированы также для:
сохранения точки восстановления;
приостановки обхода деревьев поиска;
определения первого из элементов дерева поиска, с которого следует возобновлять обход, в соответствии с точкой восстановления; и
возобновления обхода деревьев поиска с указанного первого элемента дерева.
13. Распределенная система хранения данных по п. 12, в которой модули деревьев поиска сконфигурированы для приостановки обхода деревьев поиска в связи с обновлением дерева поиска.
14. Распределенная система хранения данных по п. 13, в которой модули деревьев поиска сконфигурированы для приостановки обхода деревьев поиска в связи с обновлением журнала дерева поиска.
15. Распределенная система хранения данных по п. 12, в которой точка восстановления содержит информацию о последнем обходимом элементе дерева поиска.
16. Распределенная система хранения данных по п. 15, в которой точка восстановления содержит ключ поиска, связанный с последним обходимым элементом дерева поиска.
17. Распределенная система хранения данных по п. 16, в которой модули деревьев поиска сконфигурированы для определения первого из элементов дерева поиска, с которого необходимо возобновлять обход, в соответствии с ключом поиска, связанным с последним обходимым элементом дерева поиска.
18. Распределенная система хранения данных по п. 17, в которой модули деревьев поиска сконфигурированы для определения первого из элементов дерева поиска, с которого необходимо возобновлять обход, путем нахождения элемента дерева поиска, расположенного слева от последнего обходимого элемента дерева поиска.
19. Распределенная система хранения данных по п. 12, в которой точка восстановления используется совместно узлами хранения данных и обход деревьев поиска может быть приостановлен на первом узле хранения данных и возобновлен на втором узле хранения данных.
20. Распределенная система хранения данных по п. 19, в которой модули деревьев поиска сконфигурированы для приостановки обхода деревьев поиска в связи с изменением принадлежности дерева поиска.
RU2015139057A 2015-09-14 2015-09-14 Способ и система распределенного хранения данных RU2015139057A (ru)

Priority Applications (2)

Application Number Priority Date Filing Date Title
RU2015139057A RU2015139057A (ru) 2015-09-14 2015-09-14 Способ и система распределенного хранения данных
US15/083,324 US10402316B2 (en) 2015-09-14 2016-03-29 Tracing garbage collector for search trees under multi-version concurrency control

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
RU2015139057A RU2015139057A (ru) 2015-09-14 2015-09-14 Способ и система распределенного хранения данных

Publications (1)

Publication Number Publication Date
RU2015139057A true RU2015139057A (ru) 2017-03-17

Family

ID=58282457

Family Applications (1)

Application Number Title Priority Date Filing Date
RU2015139057A RU2015139057A (ru) 2015-09-14 2015-09-14 Способ и система распределенного хранения данных

Country Status (2)

Country Link
US (1) US10402316B2 (ru)
RU (1) RU2015139057A (ru)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10776426B1 (en) 2017-04-28 2020-09-15 EMC IP Holding Company LLC Capacity management for trees under multi-version concurrency control

Families Citing this family (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10831742B2 (en) 2016-12-09 2020-11-10 EMC IP Holding Company LLC Data set verification
US10776322B2 (en) 2016-12-13 2020-09-15 EMC IP Holding Company LLC Transformation processing for objects between storage systems
US10564883B2 (en) 2016-12-13 2020-02-18 EMC IP Holding Company LLC Efficient migration to distributed storage
US10817204B1 (en) * 2017-10-11 2020-10-27 EMC IP Holding Company LLC Migration of versioned data between storage devices
US10783022B2 (en) 2018-08-03 2020-09-22 EMC IP Holding Company LLC Immediate replication for dedicated data blocks
CN110968649B (zh) * 2018-09-30 2023-08-18 伊姆西Ip控股有限责任公司 用于管理数据集的方法、设备和计算机程序产品
US11093163B2 (en) 2019-05-10 2021-08-17 EMC IP Holding Company LLC Efficient capacity management for a data storage system
US11755366B2 (en) * 2020-09-01 2023-09-12 EMC IP Holding Company LLC Parallel handling of a tree data structure for multiple system processes
CN115599704B (zh) * 2022-11-30 2023-03-17 湖南国科亿存信息科技有限公司 一种文件系统元数据分离存储方法、装置及存储介质

Family Cites Families (54)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6070003A (en) 1989-11-17 2000-05-30 Texas Instruments Incorporated System and method of memory access in apparatus having plural processors and plural memories
US5870764A (en) 1993-05-12 1999-02-09 Apple Computer, Inc. Method of managing a data structure for concurrent serial and parallel revision of a work
US5519855A (en) 1994-01-14 1996-05-21 Microsoft Corporation Summary catalogs
US5987468A (en) 1997-12-12 1999-11-16 Hitachi America Ltd. Structure and method for efficient parallel high-dimensional similarity join
JP2000124813A (ja) 1998-10-20 2000-04-28 Texas Instr Japan Ltd リードソロモン符号化装置およびその方法とリードソロモン復号装置およびその方法
US20020073103A1 (en) * 2000-08-25 2002-06-13 Bottomley Thomas Mark Walter Memory garbage collection method and apparatus
US6567905B2 (en) * 2001-01-23 2003-05-20 Gemstone Systems, Inc. Generational garbage collector with persistent object cache
TWI257085B (en) 2002-01-21 2006-06-21 Koninkl Philips Electronics Nv Method of encoding and decoding
US7069469B2 (en) * 2002-03-14 2006-06-27 Sun Microsystems, Inc. Versioning and replaying performance tuning projects
US7581156B2 (en) 2002-12-16 2009-08-25 Microsoft Corporation Systems and methods for providing improved encoding and reconstruction of data
CN1813429B (zh) 2003-07-16 2011-09-21 日本电信电话株式会社 使用光频率编码的光通信系统、其光发送装置以及接收装置、反射型光通信装置
JP2005062928A (ja) 2003-08-11 2005-03-10 Hitachi Ltd 複数のサイトにリモートコピーを行うシステム
US6988180B2 (en) * 2003-09-29 2006-01-17 Microsoft Corporation Method and apparatus for lock-free, non-blocking hash table
US20060074990A1 (en) * 2004-09-28 2006-04-06 International Business Machines Corporation Leaf avoidance during garbage collection in a Java Virtual Machine
JP4065276B2 (ja) 2004-11-12 2008-03-19 三洋電機株式会社 送信方法およびそれを利用した無線装置
JP2006293981A (ja) 2005-03-18 2006-10-26 Hitachi Ltd データベース格納方法、および、データベース格納システム
US7707232B2 (en) 2005-05-13 2010-04-27 Microsoft Corporation Implementation for collecting unmanaged memory
US7559007B1 (en) 2006-03-10 2009-07-07 Xilinx, Inc. Encoding and decoding with puncturing
US20080126357A1 (en) 2006-05-04 2008-05-29 Wambo, Inc. Distributed file storage and transmission system
JP4856605B2 (ja) 2006-08-31 2012-01-18 パナソニック株式会社 符号化方法、符号化装置、及び送信装置
FR2908203B1 (fr) 2006-11-03 2009-04-24 Suanez Patricia Etienne Procedes et dispositifs d'authentification d'un produit et d'un code bidimensionnel et application nouvelle d'un code bidimensionnel.
US8037112B2 (en) * 2007-04-23 2011-10-11 Microsoft Corporation Efficient access of flash databases
EP2153528A1 (en) 2007-05-16 2010-02-17 Thomson Licensing Apparatus and method for encoding and decoding signals
US20100091842A1 (en) 2007-10-19 2010-04-15 Hiroshi Ikeda Coding rate conversion apparatus, coding rate conversion method, and integrated circuit
US8868623B2 (en) 2007-10-30 2014-10-21 International Business Machines Corporation Enhanced garbage collection in a multi-node environment
US20100076940A1 (en) 2008-09-09 2010-03-25 International Business Machines Corporation Method for providing maximal concurrency in a tree structure
JP4670934B2 (ja) 2008-10-10 2011-04-13 ソニー株式会社 無線通信システム、無線通信装置、無線通信方法およびコンピュータプログラム
US8572036B2 (en) * 2008-12-18 2013-10-29 Datalight, Incorporated Method and apparatus for fault-tolerant memory management
US8762642B2 (en) 2009-01-30 2014-06-24 Twinstrata Inc System and method for secure and reliable multi-cloud data replication
CN102576330B (zh) * 2009-06-12 2015-01-28 提琴存储器公司 具有持久化无用单元收集机制的存储系统
US20110055494A1 (en) 2009-08-25 2011-03-03 Yahoo! Inc. Method for distributed direct object access storage
US8458515B1 (en) 2009-11-16 2013-06-04 Symantec Corporation Raid5 recovery in a high availability object based file system
US20110196900A1 (en) 2010-02-09 2011-08-11 Alexandre Drobychev Storage of Data In A Distributed Storage System
US8843459B1 (en) 2010-03-09 2014-09-23 Hitachi Data Systems Engineering UK Limited Multi-tiered filesystem
CA2700217C (en) * 2010-04-01 2011-07-19 Ibm Canada Limited - Ibm Canada Limitee Write barrier elision for reference arrays
US9887754B2 (en) 2010-05-04 2018-02-06 Qualcomm Incorporated Method and apparatus for optimizing power distribution between symbols
US20120051208A1 (en) 2010-08-27 2012-03-01 Daoben Li Methods and systems for multiple access encoding, transmission and decoding
US8180811B2 (en) 2010-10-19 2012-05-15 Symantec Corporation Identifying unreferenced file system components
US8601036B2 (en) * 2011-03-23 2013-12-03 International Business Machines Corporation Handling persistent/long-lived objects to reduce garbage collection pause times
US8793463B2 (en) 2011-09-12 2014-07-29 Microsoft Corporation Allocation strategies for storage device sets
US8886781B2 (en) 2011-12-13 2014-11-11 Microsoft Corporation Load balancing in cluster storage systems
US8914706B2 (en) 2011-12-30 2014-12-16 Streamscale, Inc. Using parity data for concurrent data authentication, correction, compression, and encryption
US8683296B2 (en) 2011-12-30 2014-03-25 Streamscale, Inc. Accelerated erasure coding system and method
US9128949B2 (en) 2012-01-18 2015-09-08 Cloudera, Inc. Memory allocation buffer for reduction of heap fragmentation
US20130282676A1 (en) 2012-03-28 2013-10-24 Quantum Corporation Garbage collection-driven block thinning
US9071631B2 (en) 2012-08-09 2015-06-30 International Business Machines Corporation Service management roles of processor nodes in distributed node service management
US9563683B2 (en) 2013-05-14 2017-02-07 Actifio, Inc. Efficient data replication
US9268806B1 (en) 2013-07-26 2016-02-23 Google Inc. Efficient reference counting in content addressable storage
US9823969B2 (en) 2014-09-02 2017-11-21 Netapp, Inc. Hierarchical wide spreading of distributed storage
US10114745B2 (en) 2014-10-07 2018-10-30 Red Hat, Inc. Assisted garbage collection in a virtual machine
US10209956B2 (en) 2014-10-09 2019-02-19 Splunk Inc. Automatic event group actions
US9588778B2 (en) 2015-06-29 2017-03-07 International Business Machines Corporation JNI object access
US10235240B2 (en) 2015-07-03 2019-03-19 Acronis International Gmbh System and method of reliable distributed data storage with controlled redundancy
US10025806B2 (en) * 2015-08-27 2018-07-17 Vmware, Inc. Fast file clone using copy-on-write B-tree

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10776426B1 (en) 2017-04-28 2020-09-15 EMC IP Holding Company LLC Capacity management for trees under multi-version concurrency control

Also Published As

Publication number Publication date
US20170083549A1 (en) 2017-03-23
US10402316B2 (en) 2019-09-03

Similar Documents

Publication Publication Date Title
RU2015139057A (ru) Способ и система распределенного хранения данных
WO2016111954A4 (en) Metadata management in a scale out storage system
JP2015521310A5 (ru)
JP2018022529A5 (ru)
US20140156666A1 (en) Method for Automated Scaling of a Massive Parallel Processing (MPP) Database
US20190012258A1 (en) Allocation of distributed data structures
BR112015016352A2 (pt) sistema e método para motores de consulta distribuída a bancos de dados
US20160048551A1 (en) Relationship-based wan caching for object stores
RU2014127817A (ru) Система и способ управления и организации кэша веб-браузера
JP2013004101A5 (ru)
US9798674B2 (en) N-ary tree for mapping a virtual memory space
RU2019111895A (ru) Прохождение по базе данных смарт-контрактов через логическую карту
Pal et al. An experimental approach towards big data for analyzing memory utilization on a hadoop cluster using HDFS and MapReduce
US20140082316A1 (en) Selecting pages implementing leaf nodes and internal nodes of a data set index for reuse
RU2017118151A (ru) Системы и способы для обеспечения распределенного обхода дерева с использованием аппаратной обработки
CN103412889A (zh) 智能电表的数据存储和查询方法及其系统
US8768979B2 (en) In-memory data grid hash scheme optimization
CN105760553A (zh) 数据管理方法和装置
RU2016140114A (ru) Способ и устройство для обнаружения несанкционированного использования веб-адресов
Koh et al. MapReduce skyline query processing with partitioning and distributed dominance tests
CN103455284A (zh) 一种读写数据的方法及装置
IN2015DN01332A (ru)
CN117806659A (zh) 一种es高可用集群容器化部署方法及相关装置
US10324837B2 (en) Reducing minor garbage collection overhead
CN106202121B (zh) 数据存储及导出的方法和设备

Legal Events

Date Code Title Description
FA93 Acknowledgement of application withdrawn (no request for examination)

Effective date: 20180917