公开(公告)号：US09208258B2

公开(公告)日：2015-12-08

申请号：US13861329

申请日：2013-04-11

申请人： Apple Inc.

发明人： Richard P. Spillane ,  Wenguang Wang ,  David A. Majnemer

IPC分类号： G06F17/30

CPC分类号： G06F17/30961 ,  G06F17/30091

摘要： In one embodiment, two-phase mutation of an ordered tree data structure is performed, wherein a lock can be acquired on a first node in an ordered tree data structure, and an identifier for the first node can be added to a lock path data structure. A second node can also be locked, and an identifier for the second node can be added to the lock path data structure. Subsequently, a set of operations to perform on the ordered tree responsive to a modification of the second node can be determined for each node affected by the modification, and the operation for each node can be stored in the lock path data structure. Once the operations for the nodes have been determined, the operations listed in the lock path can be performed.

摘要翻译： 在一个实施例中，执行有序树数据结构的两相变异，其中可以在有序树数据结构中的第一节点上获取锁，并且可以将第一节点的标识符添加到锁路数据结构 。 也可以锁定第二节点，并且可以将第二节点的标识符添加到锁路径数据结构。 随后，可以针对受修改影响的每个节点确定响应于第二节点的修改而在有序树上执行的一组操作，并且可以将每个节点的操作存储在锁定路径数据结构中。 一旦确定了节点的操作，就可以执行锁定路径中列出的操作。

公开(公告)号：US08914381B2

公开(公告)日：2014-12-16

申请号：US13653363

申请日：2012-10-16

申请人： Apple Inc.

发明人： David A. Majnemer ,  Wenguang Wang

IPC分类号： G06F17/30 ,  G06F3/06 ,  G06F3/048

CPC分类号： G06F17/30 ,  G06F3/048 ,  G06F3/061 ,  G06F3/0647 ,  G06F3/068 ,  G06F12/0866 ,  G06F17/30132

摘要： In one embodiment, the correlation filter can use one of several data structure to track each migration unit and reject successive accesses within a period of time to each migration unit. In one embodiment, the correlation filter uses a space efficient data structure, such as a hash indexed correlation array to store the address of referenced migration units, and to filter accesses to a single migration unit that are correlated accesses resulting from multiple accesses to the same migration unit during a sequential I/O stream. In one embodiment, the correlation array contains a global timeout, which resets each element to a default value, clearing all store migration unit address values from the correlation array. In one embodiment, each element of the migration array can time-out separately.

摘要翻译： 在一个实施例中，相关滤波器可以使用几个数据结构之一来跟踪每个迁移单元，并且在一段时间内拒绝对每个迁移单元的连续访问。 在一个实施例中，相关滤波器使用空间有效的数据结构，例如散列索引相关阵列来存储所引用的迁移单元的地址，并且过滤对单个迁移单元的访问，该移动单元是对其进行多次访问而产生的相关访问 在顺序I / O流期间迁移单元。 在一个实施例中，相关阵列包含全局超时，其将每个元素重置为默认值，从相关阵列清除所有存储迁移单元地址值。 在一个实施例中，迁移阵列的每个元素可以分别超时。

公开(公告)号：US20140195571A1

公开(公告)日：2014-07-10

申请号：US13736817

申请日：2013-01-08

申请人： APPLE INC.

发明人： Wenguang Wang ,  David A. Majnemer ,  Deric S. Horn

IPC分类号： G06F17/30

CPC分类号： G06F17/30091 ,  G06F3/068 ,  G06F3/0685 ,  G06F17/30132

摘要： In one embodiment, a new file creation cache is reserved on a fast storage device that is part of a composite storage device that also includes a slow storage device; the composite storage device is treated as a single logical volume (or a plurality of logical volumes) by a file system which maintains a mapping table that is used to determine whether the write operation is for a new file. If the write operation is for a new file, the file system attempts to write the new file to the fast storage device. If the write operation is not for a new file, the mapping table specifies which device is used for the write operation.

摘要翻译： 在一个实施例中，在快速存储设备上保留新的文件创建高速缓存，快速存储设备也是还包括慢速存储设备的复合存储设备的一部分; 复合存储设备被维护用于确定写入操作是否用于新文件的映射表的文件系统被视为单个逻辑卷（或多个逻辑卷）。 如果写入操作是用于新文件，则文件系统会尝试将新文件写入快速存储设备。 如果写操作不适用于新文件，则映射表指定用于写入操作的设备。

公开(公告)号：US20130219139A1

公开(公告)日：2013-08-22

申请号：US13653371

申请日：2012-10-16

申请人： Apple Inc

发明人： Wenguang Wang ,  David A. Majnemer

IPC分类号： G06F12/14 ,  G06F12/16

CPC分类号： G06F3/061 ,  G06F3/064 ,  G06F3/0644 ,  G06F3/0647 ,  G06F3/0685

摘要： In one embodiment, a method for managing access to a fast non-volatile storage device, such as a solid state device, and a slower non-volatile storage device, such as a magnetic hard drive, can include a method of managing a sparse logical volume in which unmapped blocks of the logical volume are not allocated until use. In one embodiment, a method of sparse hole filling operates in which range locks are dynamically adjusted to perform allocations for sparse hole filling, and then re-adjusted to perform standard operations using a byte range lock. In one embodiment, a high level data structure can be used in the range lock service in the form of an ordered search tree, which could use any search tree algorithm, such as red-black tree, AVL tree, splay tree, etc.

摘要翻译： 在一个实施例中，用于管理对诸如固态设备的快速非易失性存储设备以及诸如磁性硬盘驱动器的较慢非易失性存储设备的访问的方法可以包括管理稀疏逻辑的方法 在使用之前未分配逻辑卷的未映射块的卷。 在一个实施例中，稀疏孔填充的方法操作，其中动态地调整范围锁定以执行稀疏填充的分配，然后重新调整以使用字节范围锁来执行标准操作。 在一个实施例中，可以在有序搜索树的形式的范围锁定服务中使用高级数据结构，其可以使用诸如红黑树，AVL树，播放树等的任何搜索树算法。

公开(公告)号：US09053140B2

公开(公告)日：2015-06-09

申请号：US13630206

申请日：2012-09-28

申请人： Apple Inc.

发明人： Wenguang Wang ,  David A. Majnemer

IPC分类号： G06F17/30

CPC分类号： G06F17/30371 ,  G06F17/30327

摘要： In some implementations, a B+tree (b plus tree) can provide concurrent access to data while modifying nodes of the B+tree. In some implementations, a top-down B+tree can be provided where nodes of the B+tree can be proactively merged, rebalanced and split to prevent recursive operations moving up the B+tree. In some implementations, node (or page) record data can be merged to consolidate record entries within nodes of the B+tree while only locking 1-3 nodes of the tree at the same time. In some implementations, record data can be merged across multiple nodes of the B+tree. In some implementations, ranges of data can be removed from the tree while only locking 1-3 nodes of the tree at the same time. In some implementations, range of data can be replaced with new data while only locking 1-3 nodes of the tree at the same time.

摘要翻译： 在一些实现中，B +树（b加树）可以在修改B +树的节点的同时提供数据访问。 在一些实现中，可以提供自顶向下的B +树，其中可以主动地合并，重新平衡和分割B +树的节点，以防止向上移动B +树的递归操作。 在一些实现中，可以合并节点（或页面）记录数据以合并B +树节点内的记录条目，同时只同时锁定树的1-3个节点。 在一些实现中，记录数据可以在B +树的多个节点上合并。 在一些实现中，可以从树中移除数据范围，同时只同时锁定树的1-3个节点。 在一些实现中，可以用新数据替换数据范围，同时只同时锁定树的1-3个节点。

公开(公告)号：US08868531B2

公开(公告)日：2014-10-21

申请号：US13653367

申请日：2012-10-16

申请人： Apple Inc.

发明人： David A. Majnemer ,  Wenguang Wang

IPC分类号： G06F17/00 ,  G06F17/30

CPC分类号： G06F17/30327 ,  G06F17/30008

摘要： In one embodiment, non-transitory computer-readable medium stores instructions for implementing a file system, which include operations for acquiring an exclusive lock on a first node in an ordered tree data-structure, and adding an identifier and index of the first node to a path data structure. If the value of the index in the first node is non-zero, then each exclusive lock acquired between the first node and the root of the tree data structure is released. In any case, the operation proceeds to a second node, which is addressed at the index on the first node. In one embodiment, operations further include acquiring an exclusive lock on the second node, and, if the second node is a leaf node, performing updates to the second node, and then releasing each exclusive lock in the data-structure.

摘要翻译： 在一个实施例中，非暂时性计算机可读介质存储用于实现文件系统的指令，其包括用于获取有序树数据结构中的第一节点上的排他锁的操作，以及将第一节点的标识符和索引添加到 路径数据结构。 如果第一个节点中的索引值不为零，则释放在第一个节点和树数据结构的根之间获取的每个排它锁。 在任何情况下，操作进行到在第一节点上的索引处寻址的第二节点。 在一个实施例中，操作还包括获取第二节点上的排他锁，并且如果第二节点是叶节点，则执行对第二节点的更新，然后释放数据结构中的每个排他锁。

公开(公告)号：US20130204902A1

公开(公告)日：2013-08-08

申请号：US13630206

申请日：2012-09-28

申请人： APPLE INC.

发明人： Wenguang Wang ,  David A. Majnemer

IPC分类号： G06F17/30

CPC分类号： G06F17/30371 ,  G06F17/30327

摘要： In some implementations, a B+tree (b plus tree) can provide concurrent access to data while modifying nodes of the B+tree. In some implementations, a top-down B+tree can be provided where nodes of the B+tree can be proactively merged, rebalanced and split to prevent recursive operations moving up the B+tree. In some implementations, node (or page) record data can be merged to consolidate record entries within nodes of the B+tree while only locking 1-3 nodes of the tree at the same time. In some implementations, record data can be merged across multiple nodes of the B+tree. In some implementations, ranges of data can be removed from the tree while only locking 1-3 nodes of the tree at the same time. In some implementations, range of data can be replaced with new data while only locking 1-3 nodes of the tree at the same time.

公开(公告)号：US20150347495A1

公开(公告)日：2015-12-03

申请号：US14733861

申请日：2015-06-08

申请人： Apple Inc.

发明人： Wenguang Wang ,  David A. Majnemer

IPC分类号： G06F17/30

CPC分类号： G06F16/2365 ,  G06F16/2246

摘要： In some implementations, a B+tree (b plus tree) can provide concurrent access to data while modifying nodes of the B+tree. In some implementations, a top-down B+tree can be provided where nodes of the B+tree can be proactively merged, rebalanced and split to prevent recursive operations moving up the B+tree. In some implementations, node (or page) record data can be merged to consolidate record entries within nodes of the B+tree while only locking 1-3 nodes of the tree at the same time. In some implementations, record data can be merged across multiple nodes of the B+tree. In some implementations, ranges of data can be removed from the tree while only locking 1-3 nodes of the tree at the same time. In some implementations, range of data can be replaced with new data while only locking 1-3 nodes of the tree at the same time.

摘要翻译： 在一些实现中，B +树（b加树）可以在修改B +树的节点的同时提供数据访问。 在一些实现中，可以提供自顶向下的B +树，其中可以主动地合并，重新平衡和分割B +树的节点，以防止向上移动B +树的递归操作。 在一些实现中，可以合并节点（或页面）记录数据以合并B +树节点内的记录条目，同时只同时锁定树的1-3个节点。 在一些实现中，记录数据可以在B +树的多个节点上合并。 在一些实现中，可以从树中移除数据范围，同时只同时锁定树的1-3个节点。 在一些实现中，可以用新数据替换数据范围，同时只同时锁定树的1-3个节点。

公开(公告)号：US09134908B2

公开(公告)日：2015-09-15

申请号：US13737929

申请日：2013-01-09

申请人： Apple Inc.

发明人： Deric S. Horn ,  David A. Majnemer ,  Wenguang Wang

IPC分类号： G06F12/00 ,  G06F3/06

CPC分类号： G06F3/0631 ,  G06F3/0607 ,  G06F3/0644 ,  G06F3/0683 ,  G06F3/0689

摘要： Space sharing between logical volumes is achieved through a technique that enables available storage space to be flexibly consumed and released by the logical volumes. Each logical volume is associated with an address tree that defines how available storage space is consumed by the logical volume. The technique involves receiving an input/output (I/O) operation that specifies a logical address within an address tree associated with the logical volume, parsing the address tree to identify an entry therein, if any, that is associated with the logical address, where the entry stores physical address information that is associated with the logical address. If it is determined that the entry exists, then one or more translated I/O operations are generated based on the physical address information and forwarded to a physical device manager to carry out the translated one or more I/O operations.

摘要翻译： 通过使逻辑卷灵活地消耗和释放可用存储空间的技术来实现逻辑卷之间的空间共享。 每个逻辑卷与定义逻辑卷所消耗的可用存储空间的地址树相关联。 该技术包括接收指定与逻辑卷相关联的地址树内的逻辑地址的输入/输出（I / O）操作，解析地址树以识别与逻辑地址相关联的条目（如果有的话） 其中条目存储与逻辑地址相关联的物理地址信息。 如果确定该条目存在，则基于物理地址信息生成一个或多个翻译的I / O操作，并将其转发到物理设备管理器以执行已翻译的一个或多个I / O操作。

公开(公告)号：US20140310317A1

公开(公告)日：2014-10-16

申请号：US13861329

申请日：2013-04-11

申请人： APPLE INC.

发明人： Richard P. Spillane ,  Wenguang Wang ,  David A. Majnemer

IPC分类号： G06F17/30

CPC分类号： G06F17/30961 ,  G06F17/30091

摘要： In one embodiment, two-phase mutation of an ordered tree data structure is performed, wherein a lock can be acquired on a first node in an ordered tree data structure, and an identifier for the first node can be added to a lock path data structure. A second node can also be locked, and an identifier for the second node can be added to the lock path data structure. Subsequently, a set of operations to perform on the ordered tree responsive to a modification of the second node can be determined for each node affected by the modification, and the operation for each node can be stored in the lock path data structure. Once the operations for the nodes have been determined, the operations listed in the lock path can be performed.

摘要翻译： 在一个实施例中，执行有序树数据结构的两阶段变异，其中可以在有序树数据结构中的第一节点上获取锁，并且可以将第一节点的标识符添加到锁路数据结构 。 也可以锁定第二节点，并且可以将第二节点的标识符添加到锁路径数据结构。 随后，可以针对受修改影响的每个节点确定响应于第二节点的修改而在有序树上执行的一组操作，并且可以将每个节点的操作存储在锁定路径数据结构中。 一旦确定了节点的操作，就可以执行锁定路径中列出的操作。