公开(公告)号：US09053140B2

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

申请号：US13630206

申请日：2012-09-28

Applicant: Apple Inc.

Inventor： Wenguang Wang ,  David A. Majnemer

IPC: G06F17/30

CPC classification number: G06F17/30371 ,  G06F17/30327

Abstract: 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.

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

公开(公告)号：US08868531B2

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

申请号：US13653367

申请日：2012-10-16

Applicant: Apple Inc.

Inventor： David A. Majnemer ,  Wenguang Wang

IPC: G06F17/00 ,  G06F17/30

CPC classification number: G06F17/30327 ,  G06F17/30008

Abstract: 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.

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

公开(公告)号：US20130204902A1

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

申请号：US13630206

申请日：2012-09-28

Applicant: APPLE INC.

Inventor： Wenguang Wang ,  David A. Majnemer

IPC: G06F17/30

CPC classification number: G06F17/30371 ,  G06F17/30327

Abstract: 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.

公开(公告)号：US09208258B2

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

申请号：US13861329

申请日：2013-04-11

Applicant: Apple Inc.

Inventor： Richard P. Spillane ,  Wenguang Wang ,  David A. Majnemer

IPC: G06F17/30

CPC classification number: G06F17/30961 ,  G06F17/30091

Abstract: 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.

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

公开(公告)号：US08914381B2

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

申请号：US13653363

申请日：2012-10-16

Applicant: Apple Inc.

Inventor： David A. Majnemer ,  Wenguang Wang

IPC: G06F17/30 ,  G06F3/06 ,  G06F3/048

CPC classification number: G06F17/30 ,  G06F3/048 ,  G06F3/061 ,  G06F3/0647 ,  G06F3/068 ,  G06F12/0866 ,  G06F17/30132

Abstract: 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.

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

公开(公告)号：US09575976B2

公开(公告)日：2017-02-21

申请号：US14489372

申请日：2014-09-17

Applicant: Apple Inc.

Inventor： Wenguang Wang ,  Deric Horn ,  David Alexander Majnemer ,  Owen Strain

IPC: G06F12/00 ,  G06F17/30 ,  G06F13/14

CPC classification number: G06F17/30082 ,  G06F17/30 ,  G06F17/30088 ,  G06F17/30115 ,  G06F17/3012

Abstract: Methods and apparatuses that maintain birth time for a file system to optimize file update operations are described. The file system can include a plurality of snapshots or clones of data stored in one or more extents of blocks allocated in a storage device. Each extent may be associated with a time stamp according to the birth time. A request may be received from an executable using the file system to update data in a particular extent associated with a particular time stamp. In response, the current birth time in the file system and the particular time stamp may be compared to determine if the particular extent is not shared by more than one of the snapshots. If the particular time stamp is equal to the current birth time, the particular extent may be updated directly without performing an expensive operation to check whether a reference count of the particular extent is equal to one.

Abstract translation: 描述了保持文件系统的出生时间来优化文件更新操作的方法和装置。 文件系统可以包括存储在存储设备中分配的块的一个或多个范围中的数据的多个快照或克隆。 每个范围可以根据出生时间与时间戳相关联。 可以使用文件系统从可执行程序接收请求以更新与特定时间戳相关联的特定范围内的数据。 作为响应，可以比较文件系统中的当前出生时间和特定时间戳，以确定特定范围是否不被多于一个快照共享。 如果特定时间戳等于当前出生时间，则可以直接更新特定范围，而不执行昂贵的操作来检查特定范围的引用计数是否等于1。

公开(公告)号：US09213634B2

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

申请号：US14088265

申请日：2013-11-22

Applicant: Apple Inc.

Inventor： Wenguang Wang ,  John Garvey ,  Richard Paul Spillane

IPC: G06F12/02 ,  G06F3/06 ,  G06F11/20 ,  G06F11/14

CPC classification number: G06F12/0246 ,  G06F3/06 ,  G06F3/0608 ,  G06F3/0613 ,  G06F3/0619 ,  G06F3/0643 ,  G06F3/0679 ,  G06F11/14 ,  G06F11/2082 ,  G06F12/0253 ,  G06F2212/7205

Abstract: A non-overwrite storage system, such as a log-structured file system, that includes a non-volatile storage having multiple storage segments, a volatile storage having an unsafe free segments list (UFSL), and a controller for managing storage resources of the non-volatile storage. The controller can be configured to copy page data from used segment(s) of the non-volatile storage, write the copied page data to free segment(s) of the non-volatile storage, index the UFSL with indications of the used segment(s), and thereafter prevent reuse of the used segment(s) while the indications of the used segment(s) remain indexed in the UFSL. In some implementations, the non-overwrite storage system may be associated with flash storage system, and a flash controller can be configured perform a flush track cache operation to clear the indications of the used segment(s) from the UFSL, to enable reuse of segment(s) that were previously indexed to the UFSL.

Abstract translation: 包括具有多个存储段的非易失性存储器的非覆盖存储系统（诸如日志结构化文件系统），具有不安全空闲段列表（UFSL）的易失性存储器，以及用于管理 非易失性存储。 控制器可以被配置为从非易失性存储器的使用的段复制页面数据，将复制的页面数据写入非易失性存储器的空闲段，利用所使用的段的指示来索引UFSL（ s），然后防止所使用的段的重用，同时所使用的段的指示在UFSL中保持索引。 在一些实现中，非重写存储系统可以与闪存存储系统相关联，闪存控制器可被配置为执行冲洗磁道高速缓存操作以从UFSL清除所使用的段的指示，以使得能够重用 之前已被索引到UFSL的段。

公开(公告)号：US20140195571A1

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

申请号：US13736817

申请日：2013-01-08

Applicant: APPLE INC.

Inventor： Wenguang Wang ,  David A. Majnemer ,  Deric S. Horn

IPC: G06F17/30

CPC classification number: G06F17/30091 ,  G06F3/068 ,  G06F3/0685 ,  G06F17/30132

Abstract: 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.

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

公开(公告)号：US20130219139A1

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

申请号：US13653371

申请日：2012-10-16

Applicant: Apple Inc

Inventor： Wenguang Wang ,  David A. Majnemer

IPC: G06F12/14 ,  G06F12/16

CPC classification number: G06F3/061 ,  G06F3/064 ,  G06F3/0644 ,  G06F3/0647 ,  G06F3/0685

Abstract: 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.

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

公开(公告)号：US09645946B2

公开(公告)日：2017-05-09

申请号：US14500943

申请日：2014-09-29

Applicant: Apple Inc.

Inventor： Richard Paul Spillane ,  Wenguang Wang

IPC: G06F21/79 ,  G06F12/14 ,  G06F21/78 ,  G06F12/02

CPC classification number: G06F12/1408 ,  G06F12/0246 ,  G06F21/78 ,  G06F21/79 ,  G06F2212/1052 ,  G06F2212/214 ,  G06F2212/402 ,  G06F2212/7201 ,  G06F2212/7205

Abstract: Disclosed herein are techniques for encrypting data stored on a solid-state drive (SSD) managed by a system (e.g., a computing device). Specifically, the system is configured to track block units of a larger size on the SSD so that a mapping table associated with the SSD can be kept small. After running SSD encryption using the large size block units, the entire SSD can be fully encrypted without requiring clear text to be written onto the SSD subsequent to SSD encryption being activated. Thereafter, the entire SSD can be defragmented to produce a single physical extent of encrypted data.