[WIP] Implement Delete for OCI Layout by wangxiaoxuan273 · Pull Request #582 · oras-project/oras-go

wangxiaoxuan273 · 2023-09-01T08:19:23Z

Attempt to resolve #454

Based on the implementation of #470, but with RWMutex.

DeletableStore is basically copied from oci.Store with an added RWMutex.
DeletableMemory is basically copied from graph.Memory with an added RWMutex.

shizhMSFT · 2023-09-01T10:41:06Z

 // There is no data consistency issue as long as deletion is not implemented
 // for the underlying storage.


Here's the note to RemoveFromIndex.

Moved the lock to the DeletableStore level.

codecov-commenter · 2023-09-04T06:53:03Z

Codecov Report

❌ Patch coverage is 53.46535% with 141 lines in your changes missing coverage. Please review.
✅ Project coverage is 72.63%. Comparing base (cb8c8bc) to head (6a4ade0).
⚠️ Report is 129 commits behind head on main.

Files with missing lines	Patch %	Lines
content/oci/deletableoci.go	42.45%	98 Missing and 24 partials ⚠️
internal/graph/deletablememory.go	85.00%	9 Missing and 3 partials ⚠️
content/oci/storage.go	57.14%	2 Missing and 1 partial ⚠️
internal/container/set/set.go	0.00%	2 Missing ⚠️
internal/resolver/memory.go	0.00%	2 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #582      +/-   ##
==========================================
- Coverage   74.64%   72.63%   -2.02%     
==========================================
  Files          59       62       +3     
  Lines        5266     5635     +369     
==========================================
+ Hits         3931     4093     +162     
- Misses        983     1162     +179     
- Partials      352      380      +28

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

Wwwsylvia · 2023-09-06T08:04:05Z

 // Memory is a memory based PredecessorFinder.
 type Memory struct {
 	predecessors sync.Map // map[descriptor.Descriptor]map[descriptor.Descriptor]ocispec.Descriptor
+	successors   sync.Map // map[descriptor.Descriptor]map[descriptor.Descriptor]ocispec.Descriptor


Since the successor list of a node is immutable and we don't need random access on the successors, the mapping can be from a descriptor to a successor list (map[descriptor.Descriptor][]ocispec.Descriptor).

changed both successors and predecessors to the regular map, and added locks in index and Remove.

Wwwsylvia · 2023-09-06T08:06:51Z

+	key := descriptor.FromOCI(node)
+	m.predecessors.LoadOrStore(key, &sync.Map{})
+	m.successors.LoadOrStore(key, &sync.Map{})
+	m.indexed.LoadOrStore(key, &sync.Map{})


We should mark a node as indexed after it gets indexed.

I think the node's presence in indexed means it has been indexed? Do we need an extra mark?

The current implementation marks the node as indexed before it gets indexed.

Good point. I did not notice that I changed the behavior of indexed from the original behavior. Changed it back now. Currently indexed is updated after the node gets indexed.

The variable indexed has been removed now.

Wwwsylvia · 2023-09-06T08:08:11Z

 	}
 }
+
+func (m *Memory) indexIntoMemory(ctx context.Context, node ocispec.Descriptor) {


Why is it called indexIntoMemory? Everything is in memory in this file. 🤔

Renamed it as createEntriesInMaps.

Wwwsylvia · 2023-09-06T08:12:30Z

+
+func (m *Memory) removeFromMemory(ctx context.Context, node ocispec.Descriptor) {
+	key := descriptor.FromOCI(node)
+	m.predecessors.Delete(key)


We might not want to delete the key from predecessors when a node is deleted.

Why not? Do we have a scenario of still needing it after the node is deleted? The information is stored in the node's predecessors' successors anyway.

To get the predecessors of a deleted node.

Added the entry back. Currently we don't delete the entry in predecessors when doing Delete.

Wwwsylvia · 2023-09-06T08:21:51Z

+
+// loadIndexFile reads index.json from the file system.
+// Create index.json if it does not exist.
+func (ds *DeletableStore) loadIndexFile(ctx context.Context) error {


Looks like this part was not locked (I can't recall why not, probably a bug😟). Should we lock it?

Oh it was because loadIndexFile is only called on initialization. We need a comment for this then. (I wrote this code bug I already forget it😅)

I don't think we need to. This function is only used in New() and I guess it's called only once?

Yeah but people (like me) might not realize that😂

shizhMSFT · 2023-09-06T08:40:59Z

+// RemoveFromIndex removes the node from its predecessors and successors.
+func (m *Memory) RemoveFromIndex(ctx context.Context, node ocispec.Descriptor) error {


It seems that we just call it Remove.

Renamed as Remove.

shizhMSFT · 2023-09-06T08:47:11Z

 }

+// RemoveFromIndex removes the node from its predecessors and successors.
+func (m *Memory) RemoveFromIndex(ctx context.Context, node ocispec.Descriptor) error {


There is a race condition where the same node is indexed and removed at the same time.

For example, what if another goroutine calls Index() when the current goroutine just about to hit the line 132?

northtyphoon · 2023-09-06T14:22:53Z

+)
+
+// 条件：
+// 1. 只要node被index（作为函数的第二个输入），node就在predecessors，successors，indexed中有entry


Can you please translate the comments to English? =)

I will remove it or put it formally in English in later versions. Currently this is a draft PR, and I wrote this comment to remind myself the designs, and the designs may change anytime.

Wwwsylvia · 2023-09-08T06:29:07Z

+type MemoryWithDelete struct {
+	indexed      sync.Map // map[descriptor.Descriptor]any, this variable is only used by IndexAll
+	predecessors map[descriptor.Descriptor]map[descriptor.Descriptor]ocispec.Descriptor
+	successors   map[descriptor.Descriptor]map[descriptor.Descriptor]ocispec.Descriptor


Can this be of type map[descriptor.Descriptor][]ocispec.Descriptor?
See #582 (comment)

Wwwsylvia · 2023-09-08T06:29:42Z

+
+// MemoryWithDelete is a MemoryWithDelete based PredecessorFinder.
+type MemoryWithDelete struct {
+	indexed      sync.Map // map[descriptor.Descriptor]any, this variable is only used by IndexAll


Looks like this can be moved into IndexAll.

I would like to avoid making changes to IndexAll, until I'm sure it's safe to do it. I still have questions about the behavior of IndexAll.

Wwwsylvia · 2023-09-08T06:33:36Z

+	_, exists := m.predecessors[key]
+	if !exists {
+		return nil, nil
+	}
+	var res []ocispec.Descriptor
+	for _, v := range m.predecessors[key] {
+		res = append(res, v)
+	}


nit:

Suggested change

_, exists := m.predecessors[key]

if !exists {

return nil, nil

}

var res []ocispec.Descriptor

for _, v := range m.predecessors[key] {

res = append(res, v)

}

predecessors, exists := m.predecessors[key]

if !exists {

return nil, nil

}

var res []ocispec.Descriptor

for _, v := range predecessors {

res = append(res, v)

}

?

Wwwsylvia · 2023-09-08T06:38:28Z

+
+func (m *MemoryWithDelete) createEntriesInMaps(ctx context.Context, node ocispec.Descriptor) {
+	key := descriptor.FromOCI(node)
+	if _, hasEntry := m.predecessors[key]; !hasEntry {


nit: a simple ok should be good enough.

Wwwsylvia · 2023-09-08T06:41:55Z

+// There is no data consistency issue as long as deletion is not implemented
+// for the underlying storage.
+func (m *MemoryWithDelete) index(ctx context.Context, node ocispec.Descriptor, successors []ocispec.Descriptor) {
+	m.createEntriesInMaps(ctx, node)


I don't think we need createEntriesInMaps and removeEntriesFromMaps as they are used in only one place. Just expanding them may make the caller function more readable?

I think it's better to have these two functions for maintainability and modularity. The exact behaviors of predecessors, successors and other variables at indexing and deleting may change later as we continue to improve our design, and these two functions reduce the chance of errors.

I originally did not have these two functions, but as I keep working on this feature, I've found them being functions quite useful.

Wwwsylvia · 2023-09-08T06:44:46Z

 }

+// loadIndex loads index into memory.
+func loadIndexWithMemoryWithDelete(ctx context.Context, index *ocispec.Index, fetcher content.Fetcher, tagger content.Tagger, graph *graph.MemoryWithDelete) error {


This should be defined in deletableOci.go as it has nothing to do with readonlyoci.go.

Good point, thanks. Moved it to deletableOci.go.

shizhMSFT · 2023-09-12T08:15:06Z

golang file names use underscores like deletable_memory.go

Sorry. Updated the file names to be deletableoci.go and deletablememory.go, to be consistent with other file names in the repo.

Wwwsylvia · 2023-09-12T08:56:43Z

 	return ok
 }
+
+// Delete deletes an item from the set


nit:

Suggested change

// Delete deletes an item from the set

// Delete deletes item from the set.

See https://tip.golang.org/doc/comment#func.

Added the period.

Wwwsylvia · 2023-09-12T08:57:34Z

+}
+
+// Index indexes predecessors for each direct successor of the given node.
+// There is no data consistency issue as long as deletion is not implemented


This comment is no longer valid.

Removed the comment.

Wwwsylvia · 2023-09-18T03:05:23Z

+	m.lock.RLock()
+	defer m.lock.RUnlock()
+	key := descriptor.FromOCI(node)
+	set, exists := m.predecessors[key]


nit: would it be better to call it predecessors instead of set?

Wwwsylvia · 2023-09-18T04:20:29Z

+}
+
+// loadIndexInDeletableMemory loads index into the memory.
+func loadIndexInDeletableMemory(ctx context.Context, index *ocispec.Index, fetcher content.Fetcher, tagger content.Tagger, graph *graph.DeletableMemory) error {


If we want to maintain DeletableStore separately, this function can be renamed to
func (ds *DeletableStore) loadIndex since it is only used by DeletableStore.

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

Part 2/4 of #454 Based on draft PR #582 --------- Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com> Co-authored-by: Terry Howe <tlhowe@amazon.com>

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com> Part 3/4 of #454 Based on draft PR #582 --------- Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com> Part 1/4 of #454 Based on draft PR #582 Current behavior regarding `graph.Memory.Remove(node)`: * `node` entry in `m.successors` and `m.nodes` is removed. * `node` is removed from its successors predecessors list. * `node` entry in `m.predecessors` is NOT removed, **unless all its predecessors no longer exist**. * `node` is NOT removed from its predecessors' `m.successors` list. The `m.successors` is always in accordance with the actual content. Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

wangxiaoxuan273 requested review from SteveLasker, Wwwsylvia, sajayantony and shizhMSFT as code owners September 1, 2023 08:19

wangxiaoxuan273 marked this pull request as draft September 1, 2023 08:19

wangxiaoxuan273 changed the title ~~draft PR to implement OCI delete~~ [WIP] Implement Delete for OCI Layout Sep 1, 2023

shizhMSFT reviewed Sep 1, 2023

View reviewed changes

Wwwsylvia reviewed Sep 4, 2023

View reviewed changes

Comment thread content/oci/deletableOci.go

Wwwsylvia reviewed Sep 6, 2023

View reviewed changes

shizhMSFT reviewed Sep 6, 2023

View reviewed changes

northtyphoon reviewed Sep 6, 2023

View reviewed changes

Wwwsylvia reviewed Sep 8, 2023

View reviewed changes

shizhMSFT reviewed Sep 8, 2023

View reviewed changes

Comment thread internal/graph/memoryWithDelete_test.go Outdated

Comment thread internal/resolver/memory.go

Comment thread internal/graph/memoryWithDelete_test.go Outdated

shizhMSFT reviewed Sep 12, 2023

View reviewed changes

Wwwsylvia reviewed Sep 12, 2023

View reviewed changes

Wwwsylvia reviewed Sep 18, 2023

View reviewed changes

wangxiaoxuan273 added 13 commits September 25, 2023 04:47

implemented draft version 0, need to analyze deadlock

77dc7dd

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

moved the lock up to the DeletableStore level

d4949d7

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

removed the DeletableStorage interface

5cd6043

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

added unit tests

4a0bf32

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

added Resolve

110fb3e

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

removed the RS variable name

daa8dcd

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

added back Tag and Tags

536664b

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

merged the locks and refactored saveIndex

5a8ad61

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

implemented the delete. Need to add extensive tests and refine

b1c621c

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

refined delete and removed the draft test

1163345

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

fixed failed unit test

b27a59c

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

added test

7db91b6

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

added another smaller check

8bb46b6

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

wangxiaoxuan273 added 12 commits September 25, 2023 04:47

created memory with delete

7381e9b

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

added lock, need to change sync map to regular map

589934f

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

changed successors to regular maps, updated tests

ed49d71

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

changed predecessors to regular map

1044252

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

changed the places of lock operations

4c5457d

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

per discussion of yesterday

ed0e652

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

moved loadFile function

76c33d4

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

updated file names

5bc32d2

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

resolved the comments and refined code, need unit tests

466ffd1

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

removed the unit test it's too hard to write

2117a8d

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

refined the code

5d6bede

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

bug fix and basic unit tests

cb8749e

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

This was referenced Sep 25, 2023

feat: support deletion for memory graph #606

Merged

feat: support deletion for memory resolver #607

Merged

feat: support deletion for OCI storage #608

Merged

removed an outdated comment

6a4ade0

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

TerryHowe pushed a commit that referenced this pull request Oct 2, 2023

feat: support deletion for memory resolver (#607)

6456d16

Part 2/4 of #454 Based on draft PR #582 --------- Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com> Co-authored-by: Terry Howe <tlhowe@amazon.com>

TerryHowe pushed a commit that referenced this pull request Oct 7, 2023

feat: support deletion for OCI storage (#608)

7eef77e

Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com> Part 3/4 of #454 Based on draft PR #582 --------- Signed-off-by: Xiaoxuan Wang <wangxiaoxuan119@gmail.com>

wangxiaoxuan273 closed this Oct 13, 2023

wangxiaoxuan273 deleted the draft-oci-delete branch November 27, 2023 07:16

		// There is no data consistency issue as long as deletion is not implemented
		// for the underlying storage.

		// RemoveFromIndex removes the node from its predecessors and successors.
		func (m *Memory) RemoveFromIndex(ctx context.Context, node ocispec.Descriptor) error {

	// Delete deletes an item from the set
	// Delete deletes item from the set.

Conversation

wangxiaoxuan273 commented Sep 1, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

codecov-commenter commented Sep 4, 2023 • edited by codecov Bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

wangxiaoxuan273 Sep 6, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

wangxiaoxuan273 Sep 6, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

wangxiaoxuan273 Sep 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

wangxiaoxuan273 Sep 8, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

wangxiaoxuan273 commented Sep 1, 2023 •

edited

Loading

codecov-commenter commented Sep 4, 2023 •

edited by codecov Bot

Loading

wangxiaoxuan273 Sep 6, 2023 •

edited

Loading

wangxiaoxuan273 Sep 6, 2023 •

edited

Loading

wangxiaoxuan273 Sep 7, 2023 •

edited

Loading

wangxiaoxuan273 Sep 8, 2023 •

edited

Loading

wangxiaoxuan273 Sep 12, 2023 •

edited

Loading

wangxiaoxuan273 Sep 12, 2023 •

edited

Loading