Storage.Find returns items out of order

[ixje]

Say we store the following values

Storage.Put(Storage.CurrentContext, "AA_1", "1");
Storage.Put(Storage.CurrentContext, "AA_2", "2");
Storage.Put(Storage.CurrentContext, "AA_3", "3");

The following code

Iterator<string, byte[]> si = Storage.Find(Storage.CurrentContext, "AA_");
Runtime.Notify("Starting");
while (si.Next())
{
   Runtime.Notify(si.Key);
}
Runtime.Notify("Done");

returns AA_1, AA_2, AA_3 as expected.

Now add a Storage_Get before the Find call, like so:

Storage.Get(Storage.CurrentContext, "AA_1");
Iterator<string, byte[]> si = Storage.Find(Storage.CurrentContext, "AA_");

and the iterator now returns: AA_2, AA_3, AA_1

This is caused by line 126 of

neo/neo/IO/Caching/DataCache.cs

Lines 121 to 132 in 00f9c27

	public IEnumerable<KeyValuePair<TKey, TValue>> Find(byte[] key_prefix = null)
	{
	lock (dictionary)
	{
	foreach (var pair in FindInternal(key_prefix ?? new byte[0]))
	if (!dictionary.ContainsKey(pair.Key))
	yield return pair;
	foreach (var pair in dictionary)
	if (pair.Value.State != TrackState.Deleted && (key_prefix == null || pair.Key.ToArray().Take(key_prefix.Length).SequenceEqual(key_prefix)))
	yield return new KeyValuePair<TKey, TValue>(pair.Key, pair.Value.Item);
	}
	}

When the key is already found in its cache it actually skips it for the time being instead of immediate processing (checking if DELETED).

I think this is unexpected behaviour. I do not think that possible data caching needs to be taken into account by the smart contract programmer. Any opinions?

[shargon]

this could be a problem in other implementations (neo-python)

[vncoelho]

@ixje, maybe it is as Shargon said, I will double check asap.

In general, I have been in seen in other communities that tags do not go in the tittle.
In this sense, It would be better to keep the tittle more clear.

[vncoelho]

I just double checked my output from the previous thread and it was out of order as you said, @ixje.

Should this be adjusted or modified for Neo2X, @shargon and @igormcoelho?
For Neo3 we are going to have a manager for that anyway, right?

In fact, sometime ago I remember this discussion with @igormcoelho.

[igormcoelho]

Order should be fully deterministic, otherwise it's hard (or impossible) to reproduce the results.
I see two possibilities:

1. preserve insertion order (must see how to do this with current caching)
2. sort results, but we must see how this affects Find with thousand keys.

I prefer option (2), if feasible, because key order is not easy to track in MPT or other data structures. So, sorting becomes the simplest solution I can see, at possibly big performance costs.

[lock9]

@igormcoelho I prefer option 2 too. Can't we store it ordered and just retrieve it? I think it makes more sense to sort it when we update it. What do you think?

[shargon]

I prefer sorted