公开(公告)号：US5717921A

公开(公告)日：1998-02-10

申请号：US407151

申请日：1995-03-17

Applicant: David Lomet ,  Betty Salzberg

Inventor： David Lomet ,  Betty Salzberg

IPC: G06F11/00 ,  G06F17/30

CPC classification number: G06F17/30327 ,  G06F17/30362 ,  G06F17/30371 ,  G06F11/1474 ,  Y10S707/99953

Abstract: The present invention includes an approach to index tree structure changes which provides high concurrency while being usable with many recovery schemes and with many varieties of index trees. The present invention permits multiple concurrent structure changes. In addition, all update activity and structure change activity above the data level executes in short independent atomic actions which do not impede normal database activity. Only data node splitting executes in the context of a database transaction. This feature makes the approach usable with the diverse recovery mechanisms, while only impacting concurrency in a modest way. Even this impact can be avoided by re-packaging the atomic actions, at the cost of requiring more from the recovery system.

Abstract translation: 本发明包括索引树结构变化的方法，其提供高并发性，同时可用于许多恢复方案和许多种类的索引树。 本发明允许多个并发结构改变。 此外，数据级别以上的所有更新活动和结构更改活动都会在短时间内执行，而不会妨碍正常的数据库活动。 只有数据节点分割在数据库事务的上下文中执行。 此功能使该方法可用于各种恢复机制，同时仅以适度的方式影响并发性。 即使这种影响可以通过重新打包原子行动来避免，以牺牲更多的恢复系统为代价。

公开(公告)号：US09003162B2

公开(公告)日：2015-04-07

申请号：US13527880

申请日：2012-06-20

Applicant: David Lomet ,  Justin Levandoski ,  Sudipta Sengupta

Inventor： David Lomet ,  Justin Levandoski ,  Sudipta Sengupta

IPC: G06F12/10

CPC classification number: G06F12/10 ,  G06F12/0804 ,  G06F17/30327 ,  G06F17/30377 ,  Y10S707/99951

Abstract: A request to modify an object in storage that is associated with one or more computing devices may be obtained, the storage organized based on a latch-free B-tree structure. A storage address of the object may be determined, based on accessing a mapping table that includes map indicators mapping logical object identifiers to physical storage addresses. A prepending of a first delta record to a prior object state of the object may be initiated, the first delta record indicating an object modification associated with the obtained request. Installation of a first state change associated with the object modification may be initiated via a first atomic operation on a mapping table entry that indicates the prior object state of the object. For example, the latch-free B-tree structure may include a B-tree like index structure over records as the objects, and logical page identifiers as the logical object identifiers.

Abstract translation: 可以获得修改与一个或多个计算设备相关联的存储中的对象的请求，该存储是基于无闩锁B树结构组织的。 可以基于访问包括将逻辑对象标识符映射到物理存储地址的映射指示符的映射表来确定对象的存储地址。 可以启动对对象的先前对象状态的第一增量记录的前缀，所述第一增量记录指示与所获取的请求相关联的对象修改。 可以通过指示对象的先前对象状态的映射表项上的第一原子操作来启动与对象修改相关联的第一状态改变的安装。 例如，无闩锁B树结构可以包括作为对象的记录上的B树类索引结构，以及逻辑页标识符作为逻辑对象标识符。

公开(公告)号：US20130346725A1

公开(公告)日：2013-12-26

申请号：US13527880

申请日：2012-06-20

Applicant: David Lomet ,  Justin Levandoski ,  Sudipta Sengupta

Inventor： David Lomet ,  Justin Levandoski ,  Sudipta Sengupta

IPC: G06F12/10

CPC classification number: G06F12/10 ,  G06F12/0804 ,  G06F17/30327 ,  G06F17/30377 ,  Y10S707/99951

Abstract: A request to modify an object in storage that is associated with one or more computing devices may be obtained, the storage organized based on a latch-free B-tree structure. A storage address of the object may be determined, based on accessing a mapping table that includes map indicators mapping logical object identifiers to physical storage addresses. A prepending of a first delta record to a prior object state of the object may be initiated, the first delta record indicating an object modification associated with the obtained request. Installation of a first state change associated with the object modification may be initiated via a first atomic operation on a mapping table entry that indicates the prior object state of the object. For example, the latch-free B-tree structure may include a B-tree like index structure over records as the objects, and logical page identifiers as the logical object identifiers.

Abstract translation: 可以获得修改与一个或多个计算设备相关联的存储中的对象的请求，该存储是基于无闩锁B树结构组织的。 可以基于访问包括将逻辑对象标识符映射到物理存储地址的映射指示符的映射表来确定对象的存储地址。 可以启动对对象的先前对象状态的第一增量记录的前缀，所述第一增量记录指示与所获取的请求相关联的对象修改。 可以通过指示对象的先前对象状态的映射表项上的第一原子操作来启动与对象修改相关联的第一状态改变的安装。 例如，无闩锁B树结构可以包括作为对象的记录上的B树类索引结构，以及逻辑页标识符作为逻辑对象标识符。

公开(公告)号：US20080071809A1

公开(公告)日：2008-03-20

申请号：US11859597

申请日：2007-09-21

Applicant: David Lomet

Inventor： David Lomet

IPC: G06F17/00

CPC classification number: G06F16/2246 ,  G06F16/2272 ,  G06F16/2308 ,  Y10S707/99942 ,  Y10S707/99943

Abstract: A data structure, added to a modified form of the Blink-tree data structure, tracks delete states for nodes. The index delete state (DX) indicates whether it is safe to directly access an index node without re-traversing the B-tree. The DX state is maintained globally, outside of the tree structure. The data delete state (DD) indicates whether it is safe to post an index term for a new leaf node. A DD state is maintained in each level 1 node for its leaf nodes. Delete states indicate whether a specific node has not been deleted, or whether it may have been deleted. Delete states are used to remove the necessity for atomic node splits and chains of latches for deletes, while not requiring retraversal. This property of not requiring a retraversal is exploited to simplify the tree modification operations.

Abstract translation: 添加到B ^{链接树数据结构的修改形式的数据结构跟踪节点的删除状态。 索引删除状态（D X）表示在不重新遍历B树的情况下直接访问索引节点是否安全。 在树结构之外，全局地维护D 状态。 数据删除状态（D D ）表示是否可以安全地为新的叶节点发布索引项。 在其叶节点的每个1级节点中保持D D D N状态。 删除状态表示特定节点是否未被删除，或者是否可能被删除。 删除状态用于消除用于删除的原子节点拆分和锁存链的必要性，而不需要重新进行穿越。 利用这种不需要重穿的属性来简化树的修改操作。}

公开(公告)号：US20060248386A1

公开(公告)日：2006-11-02

申请号：US11399759

申请日：2006-04-07

Applicant: Roger Barga ,  David Lomet

Inventor： Roger Barga ,  David Lomet

IPC: G06F11/00

CPC classification number: G06F11/1482 ,  G06F11/1438 ,  G06F11/1471

Abstract: Persistent components are provided across both process and server failures, without the application programmer needing take actions for component recoverability. Application interactions with a stateful component are transparently intercepted and stably logged to persistent storage. A “virtual” component isolates an application from component failures, permitting the mapping of a component to an arbitrary “physical” component. Component failures are detected and masked from the application. A virtual component is re-mapped to a new physical component, and the operations required to recreate a component and reinstall state up to the point of the last logged interaction is replayed from the log automatically.

公开(公告)号：US20060167960A1

公开(公告)日：2006-07-27

申请号：US11040598

申请日：2005-01-21

Applicant: David Lomet

Inventor： David Lomet

IPC: G06F17/30

CPC classification number: G06F17/30353 ,  Y10S707/99933 ,  Y10S707/99953 ,  Y10S707/99957

Abstract: Lazy timestamping in a transaction time database is performed using volatile reference counting and checkpointing. Volatile reference counting is employed to provide a low cost way of garbage collecting persistent timestamp information about a transaction by identifying exactly when all record versions of a transaction are timestamped and the versions are persistent. A volatile timestamp (VTS) table is created in a volatile memory, and stores timestamp, reference count, transaction ID, and LSN information. Active portions of a persisted timestamp (PTS) table are stored in the VTS table to provide faster and more efficient timestamp processing via accesses to the VTS table information. The reference count information is stored only in the VTS table for faster access. When the reference count information decrements to zero, it is known that all record versions that were updates for a transaction were timestamped. A checkpointing component facilitates checkpoint processing for verifying that timestamped records have been written to the persistent database and that garbage collection of the PTS table can be performed for transaction entries with zero reference counts.

Abstract translation: 使用易失性引用计数和检查点执行事务处理时间数据库中的延迟时间戳。 使用易失性引用计数来提供一种低成本的垃圾收集关于交易的持续时间戳信息的方式，通过确定事务的所有记录版本是否具有时间戳并且版本是持久的。 在易失性存储器中创建易失性时间戳（VTS）表，并存储时间戳记，引用计数，事务ID和LSN信息。 持久时间戳（PTS）表的活动部分存储在VTS表中，以通过访问VTS表信息来提供更快更有效的时间戳处理。 参考计数信息仅存储在VTS表中，以便更快的访问。 当引用计数信息递减到零时，已知所有作为事务更新的记录版本都是时间戳的。 检查点组件有助于检查点处理，以验证时间戳记已被写入持久数据库，并且可以对具有零引用计数的事务条目执行PTS表的垃圾回收。

公开(公告)号：US20060036896A1

公开(公告)日：2006-02-16

申请号：US11203489

申请日：2005-08-12

Applicant: Rod Gamache ,  Michael Massa ,  Sunita Shrivastava ,  Gor Nishanov ,  David Lomet ,  Philip Bernstein ,  Rohit Jain

Inventor： Rod Gamache ,  Michael Massa ,  Sunita Shrivastava ,  Gor Nishanov ,  David Lomet ,  Philip Bernstein ,  Rohit Jain

IPC: G06F11/00

CPC classification number: G06F11/182 ,  G06F11/1425 ,  G06F11/1482 ,  G06F11/1662 ,  G06F11/181 ,  G06F11/2023 ,  G06F11/2035

Abstract: A method and system for increasing server cluster availability by requiring at a minimum only one node and a quorum replica set of replica members to form and operate a cluster. Replica members, independent from the nodes, maintain cluster operational data. A cluster operates when one node possesses a majority of replica members, which ensures that any new or surviving cluster includes consistent cluster operational data via at least one replica member from the immediately prior cluster. Arbitration provides exclusive ownership by one node of the replica members, including at cluster formation, and when the owning node fails. Arbitration uses a fast mutual exclusion algorithm and a reservation mechanism to challenge for and defend the exclusive reservation of each member. A quorum replica set algorithm brings members online and offline with data consistency, including updating unreconciled replica members, and ensures consistent read and update operations.