`STACKREFLEN` is not aware of the deletion of key

[NOS-AE]

I'm not sure the expected behavior of the STACKREF type, a ref behaves like a soft link to the key, that is, stackreflen report the correct len after trying to access a deleted key, which may be confusing.

How to reproduce

m3/macos 14.2 go run main.go based on commit 34d5fa5

127.0.0.1:7379> set s1 1
OK
127.0.0.1:7379> stackrefpush st1 s1
(integer) 1
127.0.0.1:7379> stackreflen st1
(integer) 1
127.0.0.1:7379> del s1
(integer) 1
127.0.0.1:7379> stackreflen st1
(integer) 1
127.0.0.1:7379> stackrefpop st1
(nil)
127.0.0.1:7379> stackreflen st1
(integer) 0

Expected behavior

127.0.0.1:7379> set s1 1
OK
127.0.0.1:7379> stackrefpush st1 s1
(integer) 1
127.0.0.1:7379> stackreflen st1
(integer) 1
127.0.0.1:7379> del s1
(integer) 1
127.0.0.1:7379> stackreflen st1
(integer) 0
127.0.0.1:7379> stackrefpop st1
(nil)
127.0.0.1:7379> stackreflen st1
(integer) 0

[JyotinderSingh]

Thank you for reporting this bug, must have overlooked this case.

[AshwinKul28]

@JyotinderSingh For this, while pushing onto the stack, shall we also add a reference? https://github.com/DiceDB/dice/blob/master/core/eval.go#L978

[22liyi]

java 可以用这个db么？

[kushal0511-not]

@JyotinderSingh if nobody is working on this , can i take this one? cc @AshwinKul28

[JyotinderSingh]

@JyotinderSingh if nobody is working on this , can i take this one?

Assigned

[kushal0511-not]

@JyotinderSingh I am thinking of adding cleanup method in stackref.go

// Cleanup removes expired or deleted keys from the stack.
func (s *StackRef) Cleanup() {
	var validElements []int64

	for {
		val, err := s.si.Pop()
		if err != nil {
			break // Break the loop if the stack is empty
		}

		key := *((*string)(unsafe.Pointer(uintptr(val))))
		obj := Get(key)
		if obj != nil {
			validElements = append(validElements, val)
		}
	}

	for i := len(validElements) - 1; i >= 0; i-- {
		s.si.Push(validElements[i])
	}
}

and will use it before returning the length. The reason behind is that the keys which are expired or deleted can be anywhere in stack.

I thought of map but we cannot handle expired keys in that case. or should we count expired keys also in STACKREFLEN?

Do you have any other optimal way to do this? Or any suggestion?

[NOS-AE]

@JyotinderSingh I am thinking of adding cleanup method in stackref.go

// Cleanup removes expired or deleted keys from the stack.
func (s *StackRef) Cleanup() {
	var validElements []int64

	for {
		val, err := s.si.Pop()
		if err != nil {
			break // Break the loop if the stack is empty
		}

		key := *((*string)(unsafe.Pointer(uintptr(val))))
		obj := Get(key)
		if obj != nil {
			validElements = append(validElements, val)
		}
	}

	for i := len(validElements) - 1; i >= 0; i-- {
		s.si.Push(validElements[i])
	}
}

and will use it before returning the length. The reason behind is that the keys which are expired or deleted can be anywhere in stack.

I thought of map but we cannot handle expired keys in that case. or should we count expired keys also in STACKREFLEN?

Do you have any other optimal way to do this? Or any suggestion?

To make things look consistent, we could do one of these refactorations: returning nil when STACKREFPOP a deleted key or returning the number of keys that haven't been deleted or expired when executing STACKREFLEN . The former one may be easier to realize.

[kushal0511-not]

@NOS-AE Thanks for suggestions.

returning nil when STACKREFPOP a deleted key

This will change current behavior of Pop(), that is popping until existing non-expired key.

@JyotinderSingh which approach should we follow from above two?

[JyotinderSingh]

@NOS-AE @kushal0511-not thanks for the discussion.

Let's not change the pop() behaviour.

We have two options For STACKREFLEN.

1. We can do something similar to pop. We can try to do a best effort accuracy for the length information. Pop until we see the first non expired key (but don't pop the non expired key) and then return the length. This may mean that the result is not completely accurate.
2. We can use the cleanup method before every call to len - which may be a performance hit but more accurate.

What are your thoughts?

[kushal0511-not]

@JyotinderSingh In worst case for 1st approach could be like many (suppose 10000 ) expired key and 2-3 non-expired key. then STACKREFLEN return a number which will far from real number.

Performance wise 2nd approach is not good.

if we don't have any other option we can go with 1st approach.

Also one thing to notice the comment is not referring to correct implementation of Pop()

// Pop pops the reference from the stack s.
// returns nil if key does not exist in the store any more
// if the expired key is popped from the stack, we continue to pop until
// until we find one non-expired key
// TODO: test for expired keys
func (s *StackRef) Pop() (*StackElement, error) {

comment says that function returns nil if key does not exists but actually it pops the key and check for next key in stack (it behaves same as expired key).

cc @NOS-AE

[JyotinderSingh]

@JyotinderSingh

In worst case for 1st approach could be like many (suppose 10000 ) expired key and 2-3 non-expired key.

then STACKREFLEN return a number which will far from real number.

Performance wise 2nd approach is not good.

if we don't have any other option we can go with 1st approach.

Also one thing to notice the comment is not referring to correct implementation of Pop()

// Pop pops the reference from the stack s.

// returns nil if key does not exist in the store any more

// if the expired key is popped from the stack, we continue to pop until

// until we find one non-expired key

// TODO: test for expired keys

func (s *StackRef) Pop() (*StackElement, error) {

comment says that function returns nil if key does not exists but actually it pops the key and check for next key in stack (it behaves same as expired key).

cc @NOS-AE

Yeah the second line of the comment doesn't clearly explain the behavior. We can fix it as a part of the PR for this issue.

I'm tempted to go with option 2 (perform cleanup).

@soumya-codes what do you think?

[NOS-AE]

@JyotinderSingh In worst case for 1st approach could be like many (suppose 10000 ) expired key and 2-3 non-expired key.

Performance wise 2nd approach is not good.

if we don't have any other option we can go with 1st approach.

Also one thing to notice the comment is not referring to correct implementation of Pop()

// Pop pops the reference from the stack s.
// returns nil if key does not exist in the store any more
// if the expired key is popped from the stack, we continue to pop until
// until we find one non-expired key
// TODO: test for expired keys
func (s *StackRef) Pop() (*StackElement, error) {

comment says that function returns nil if key does not exists but actually it pops the key and check for next key in stack (it behaves same as expired key).

cc @NOS-AE

Prefer the consistency rather than an approximate probe. If so, leaving a statement/comment in document/code about the worst time complexity of STACKREFLEN would be great for whoever want to use it.

[JyotinderSingh]

@JyotinderSingh In worst case for 1st approach could be like many (suppose 10000 ) expired key and 2-3 non-expired key.在最坏的情况下，第一种方法可能是许多（假设 10000 个）过期密钥和 2-3 个未过期密钥。 then STACKREFLEN return a number which will far from real number.然后 STACKREFLEN 返回一个远离实数的数字。

Performance wise 2nd approach is not good.性能方面，第二种方法不好。

if we don't have any other option we can go with 1st approach.如果我们没有其他选择，我们可以采用第一种方法。

Also one thing to notice the comment is not referring to correct implementation of Pop()另外需要注意的一件事是，该注释并未提及 Pop() 的正确实现

// Pop pops the reference from the stack s.

// returns nil if key does not exist in the store any more

// if the expired key is popped from the stack, we continue to pop until

// until we find one non-expired key

// TODO: test for expired keys

func (s *StackRef) Pop() (*StackElement, error) {

comment says that function returns nil if key does not exists but actually it pops the key and check for next key in stack (it behaves same as expired key).注释说如果键不存在，函数将返回 nil，但实际上它会弹出键并检查堆栈中的下一个键（其行为与过期键相同）。

cc @NOS-AE

Prefer the consistency rather than an approximate probe. If so, leaving a statement/comment in document/code about the worst time complexity of STACKREFLEN would be great for whoever want to use it.

Agreed. Let's go with the performance tradeoff in this case.

[kushal0511-not]

Going with the cleanup method.

[soumya-codes]

@kushal0511-not, given the current context i agree with @JyotinderSingh that we should go for consistency over approximation and take the second approach.

However in the medium term we can handle this more effectively by addressing the two concerns stack-length and stack-operations separately.

1. We handle updating stack length of each of the stacks synchronously as and when a key is deleted or it expires. We can discuss how we can handle this with minimal overhead.
2. The handling of removing/dealing with deleted/expired keys can be done lazily during stack push/pop operations as we do today.

Let me know what you both think, if you agree with this approach we can discuss about the implementation.

[soumya-codes]

returns nil if key does not exist in the store any more

So will we be updating the comment to reflect the current behaviour?

[AshwinKul28]

The cleanup method looks good. @kushal0511-not (just an overhead of popping and again pushing almost full array everytime)

Also, I agree with what @soumya-codes says, stack-length and actual stack operations can be separated, I just have once concern that there at any point in time will there be any inconsistencies between length and actual operation just because we are doing it lazily.

[soumya-codes]

@AshwinKul28 when I say lazily, I meant we can keep the implementation as it is today i.e. handling the deleted/expired key during POP operation. Only issue I see with the current approach is that the stack size can be ever increasing if we have in-frequent POP operations.

[kushal0511-not]

Let me know what you both think, if you agree with this approach we can discuss about the implementation.

@soumya-codes Sure we can discuss. I have doubt about how we can handle expired keys because at the time of expiration key can be any where in stack.

So will we be updating the comment to reflect the current behavior?

yes

just an overhead of popping and again pushing almost full array every time.

@AshwinKul28 yeah

[NOS-AE]

The process of deleting a key from the store can be sync or async. If we decide to delete all references once the key is deleted, which will increasingly become complex to make it happen, as it may involve mechanism like pub-sub to notify all refs get deleted, not just STACKREF, maybe QUEUEREF, XXREF as well. Also, synchronously clean all the refs of a key when the key is deleted will bring uncertainty of the time complexity to synchronous command like DEL.

In addition, assume that we are able to get notified the deletion/expiration of a key easily, and are about to remove it from the stack, but it's a stack after all, we still need to pop all the elements at the top, even if we have some techniques like memmove to achieve it more efficiently.

[kushal0511-not]

@soumya-codes and I discussed this issue and we've reached the following conclusions:

1. There is no reference in redis of QREF or STCKREF from which we can get to know implementation and time and space complexity of command. Is this new add-on in DiceDB like which we are offering different from redis?

2. As of Now , We don't have any notification mechanism so that we know that key got expired (at the moment of expiration). We need to fix that before implementing STACKREFLEN.

Given these points, we've decided that we should temporarily remove support for STACKREFLEN until these issues are resolved.

CC: @JyotinderSingh @arpitbbhayani

[JyotinderSingh]

@soumya-codes and I discussed this issue and we've reached the following conclusions:

1. There is no reference in redis of QREF or STCKREF from which we can get to know implementation and time and space complexity of command.

Is this new add-on in DiceDB like which we are offering different from redis?

2. As of Now , We don't have any notification mechanism so that we know that key got expired (at the moment of expiration). We need to fix that before implementing STACKREFLEN.

Given these points, we've decided that we should temporarily remove support for STACKREFLEN until these issues are resolved.

CC: @JyotinderSingh @arpitbbhayani

STACKREF is a novel data structure in dice. I am okay with removing the STACKREFLEF command. Alternatively we could maintain the command with the performance penalty of clearing up the stack. I am okay with whatever the general consensus is.

[soumya-codes]

STACKREF is a novel data structure in dice. I am okay with removing the STACKREFLEF command. Alternatively we could maintain the command with the performance penalty of clearing up the stack. I am okay with whatever the general consensus is.

Since it is a unique proposition from DiceDB, we can add few limitations to ensure novelty while limiting the performance penalty:

1. Limit the stack size. For example to 10000 entries.
2. Limit the number of stacks. For example to 100.

@kushal0511-not @JyotinderSingh wdyt?

[JyotinderSingh]

STACKREF is a novel data structure in dice. I am okay with removing the STACKREFLEF command. Alternatively we could maintain the command with the performance penalty of clearing up the stack. I am okay with whatever the general consensus is.

Since it is a unique proposition from DiceDB, we can add few limitations to ensure novelty while limiting the performance penalty:

1. Limit the stack size. For example to 10000 entries.

2. Limit the number of stacks. For example to 100.

@kushal0511-not @JyotinderSingh wdyt?

Sounds good to me

[JyotinderSingh]

We probably want to do something similar for QueueRef

[kushal0511-not]

STACKREF is a novel data structure in dice. I am okay with removing the STACKREFLEF command. Alternatively we could maintain the command with the performance penalty of clearing up the stack. I am okay with whatever the general consensus is.

Since it is a unique proposition from DiceDB, we can add few limitations to ensure novelty while limiting the performance penalty:

1. Limit the stack size. For example to 10000 entries.
2. Limit the number of stacks. For example to 100.

@kushal0511-not @JyotinderSingh wdyt?

Yeah thats good idea.

We probably want to do something similar for QueueRef

Yes @JyotinderSingh Can i do changes for that also in the same PR which i will raise for this issue? If that is okay

[JyotinderSingh]

STACKREF is a novel data structure in dice. I am okay with removing the STACKREFLEF command. Alternatively we could maintain the command with the performance penalty of clearing up the stack. I am okay with whatever the general consensus is.

Since it is a unique proposition from DiceDB, we can add few limitations to ensure novelty while limiting the performance penalty:

1. Limit the stack size. For example to 10000 entries.

2. Limit the number of stacks. For example to 100.

@kushal0511-not @JyotinderSingh wdyt?

Yeah thats good idea.

We probably want to do something similar for QueueRef

Yes

@JyotinderSingh

Can i do changes for that also in the same PR which i will raise for this issue? If that is okay

Sure, sounds good