Vector lifecycle management in distributed storage systems

Patent metadata

Field	Value
Publication number	US-2026003846-A1
Application number	US-202418759311-A
Country	US
Kind code	A1
Filing date	Jun 28, 2024
Priority date	Jun 28, 2024
Publication date	Jan 1, 2026
Grant date	—

Abstract

Systems and methods are provided for receiving a vector to be inserted into a set of vectors, wherein the set of vectors is stored as a plurality of leaf objects of a distributed proximity-based graph across a plurality of storage devices of a distributed object storage system, identifying a subset of the plurality of leaf objects based at least partly on a similarity of the vector to one or more vectors stored in the subset of the plurality of leaf objects, storing the vector in an insert buffer associated with the subset of the plurality of leaf objects, and in response to a vector query, generating query results comprising the vector stored in the insert buffer, and at least one of the one or more vectors stored in the subset of the plurality of leaf objects.

First claim

1 . A vector management system comprising:
a distributed object storage service comprising a plurality of object storage devices; an index service comprising a first set of one or more computing devices, the index service configured to:
receive a vector to be inserted into a set of vectors, wherein the set of vectors is stored as a plurality of leaf objects of a distributed proximity-based graph across the plurality of object storage devices of the distributed object storage service;
identify a subset of the plurality of leaf objects based at least partly on a similarity of the vector to one or more vectors stored in the subset of the plurality of leaf objects; and
store the vector in an insert buffer associated with the subset of the plurality of leaf objects; and
a query service comprising a second set of one or more computing devices, the query service configured to, in response to a query for vectors similar to a query vector:
load at least one leaf object of the subset of the plurality of leaf objects based on a similarity, to the query vector, of individual vectors in the at least one leaf object;
in parallel with loading the leaf object, load the vector from the insert buffer based on a similarity of the vector to the query vector; and
generate query results comprising the vector and at least a portion of vectors from the leaf object.

2 . The vector management system of claim 1 , wherein the insert buffer comprises an append-only sequential buffer maintained in memory of the index service.

3 . The vector management system of claim 1 , wherein the index service is further configured to:
receive a vector deletion command to delete a second vector stored in the leaf object; and update a deletion log to indicate the second vector has been deleted, wherein the second vector remains stored in the leaf object.

4 . The vector management system of claim 1 , wherein the index service is further configured to:
determine that a compaction trigger has occurred; remove a first plurality of vectors from a first insert buffer associated with a first subset of the plurality of leaf objects; generate a first subset of second version leaf objects using vectors from the first subset of the plurality of leaf objects and the first plurality of vectors; remove a second plurality of vectors from a second insert buffer associated with a second subset of the plurality of leaf objects; and generate a second subset of second version leaf objects using vectors from the second subset of the plurality of leaf objects and the second plurality of vectors.

5 . A computer-implemented method comprising:
under control of a computing system comprising a computer-readable memory and a processor configured to execute specific instructions:
receiving a vector to be inserted into a set of vectors, wherein the set of vectors is stored as a plurality of leaf objects of a distributed proximity-based graph across a plurality of storage devices of a distributed object storage system;
identifying a subset of the plurality of leaf objects based at least partly on a similarity of the vector to one or more vectors stored in the subset of the plurality of leaf objects;
storing the vector in an insert buffer associated with the subset of the plurality of leaf objects; and
in response to a query:
searching the insert buffer using a query vector at least partially in parallel with searching the distributed proximity-based graph using the query vector; and
generating query results comprising the vector stored in the insert buffer, and at least one of the one or more vectors stored in the subset of the plurality of leaf objects.

6 . The computer-implemented method of claim 5 , wherein storing the vector in the insert buffer comprises storing the vector in an append-only sequential buffer maintained in memory.

7 . The computer-implemented method of claim 5 , further comprising:
receiving a vector deletion command to delete a second vector stored in a leaf object of the plurality of leaf objects; and updating a deletion log to indicate the second vector has been deleted, wherein the second vector remains stored in the leaf object.

8 . The computer-implemented method of claim 7 , further comprising excluding the second vector from the query results based on the deletion log indicating the second vector has been deleted.

9 . The computer-implemented method of claim 5 , further comprising:
determining that a flushing trigger associated with the insert buffer has occurred; removing a plurality of vectors from the insert buffer; generating a storage object comprising the plurality of vectors removed from the insert buffer; and storing the storage object in the distributed object storage system.

10 . The computer-implemented method of claim 5 , further comprising:
determining that a compaction trigger has occurred; removing a first plurality of vectors from a first insert buffer associated with a first subset of the plurality of leaf objects; generating a first subset of second version leaf objects using vectors from the first subset of the plurality of leaf objects and the first plurality of vectors; removing a second plurality of vectors from a second insert buffer associated with a second subset of the plurality of leaf objects; and generating a second subset of second version leaf objects using vectors from the second subset of the plurality of leaf objects and the second plurality of vectors.

11 . The computer-implemented method of claim 10 , further comprising updating a course proximity-based graph to include representative vectors from each of the first subset of second version leaf objects and the second subset of second version leaf objects.

12 . The computer-implemented method of claim 10 , wherein generating the first subset of second version leaf objects comprises generating a plurality of serialized proximity-based graph data structures using the vectors from the first subset of the plurality of leaf objects and the first plurality of vectors.

13 . The computer-implemented method of claim 10 , further comprising updating index metadata, associated with the distributed proximity-based graph, to indicate the first subset of second version leaf objects are to be used in place of the first subset of the plurality of leaf objects.

14 . A system comprising:
computer-readable memory storing executable instructions; and one or more computing devices programmed by executable instructions to at least:
receive a vector to be inserted into a set of vectors, wherein the set of vectors is stored as a plurality of leaf objects of a distributed proximity-based graph across a plurality of storage devices of a distributed object storage system;
identify a subset of the plurality of leaf objects based at least partly on a similarity of the vector to one or more vectors stored in the subset of the plurality of leaf objects;
store the vector in an insert buffer associated with the subset of the plurality of leaf objects; and
in response to a query:
search the insert buffer using a query vector at least partially in parallel with searching the distributed proximity-based graph using the query vector; and
generate query results comprising the vector stored in the insert buffer, and at least one of the one or more vectors stored in the subset of the plurality of leaf objects.

15 . The system of claim 14 , wherein the insert buffer comprises an append-only sequential buffer maintained in memory.

16 . The system of claim 14 , wherein the one or more computing devices are further progr

Assignees

• Amazon Tech Inc

Inventors

• Ferhatosmanoglu Hakan
• Kutsy Andrew
• Katz Jonathan S
• Annapragada Mrithyunjaya Kumar
• Brooker Marc
• Warfield Andrew Kent
• Huang Yu-Ju

Classifications

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F16/2455 Primary

  Query execution · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title