Keys iterator of the store::UnorderedMap has a huge performance drop after removing elements

[fadeevab]

Problem

1. Create store::UnorderedMap
2. Insert 1000 elements.
3. Remove 900 elements.
4. Now, iteration through 100 keys takes O(1000) time instead of O(100) expected.

Trying to take just a constant number of keys gives an inconsistent performance with increasing gas consumption 3TGas -> 10 TGas -> 20 TGas ->....., while removing bunches of elements from the map.

Cause

FreeList is now used for the keys in the store::UnorderedMap, there is an iterator that goes through the "holes" in the vector of keys which never shrinks when elements are removed.

Example

Here, iterating through 100 keys after removals gives 0.5 TGas consumption instead of 0.04 TGas if 100 elements were just inserted.

    pub fn test(&mut self) {
        let mut map = UnorderedMap::new(b'a');
        for i in 0..1000 {
            map.insert(i, i);
        }

        // Keep only 100 elements.
        for i in 0..900 {
            map.remove(&i);
        }

        let gas = env::used_gas();
        let _ = map.keys().collect::<Vec<_>>();
        let gas = (env::used_gas() - gas).0 as f32 / Gas::ONE_TERA.0 as f32;

        env::log_str(&format!("used gas: {:?}", gas));  // 0.5 TGas
    }

0.5 TGas - 100 keys, after removals.
0.04 TGas - 100 keys, no removals, just inserts.
x10 performance drop.
It's worse when there are thousands of elements.

[fadeevab]

Another problem is that skip is not cheap (FreeList::Iterator::skip) because it's not lazy, it reads every value while moving to the nth position to figure out whether a slot is occupied or not. And it's another issue. E.g. even in a case with no removals, skipping over a couple of thousand elements may not be possible because gas will be consumed earlier.

UPD: created an issue #1135 to track it there.
UPD.2: Seems like, implementing laziness would be enough, so collect/skip/other wouldn't be severely impacted while running through empty slots.

[fadeevab]

I found an enhancement ticket outlining the same issue: #990.

There, defrag method was introduced to fight the fragmentation of the FreeList via removing the "holes" in it: https://github.com/near/near-sdk-rs/pull/1023/files#diff-793a8b595e5ccce11a932ce7a41e0ea3a313790edc40bc4ff0ad5943a112a673R230

However, the problem lies in the fact that running through the FreeList slots is not cheap itself (see another ticket I created #1135), and iterating through the UnorderedMap/FreeList is limited to 2-3000 first elements: skip/defrag/next/everything is limited to 300 TGas. Defragmentation can defragment just the head of the data structure.

UnorderedMap is unreachable higher than ~2000 elements via its Iterator.

[frol]

@fadeevab From what I can tell, the old near_sdk::collections::UnorderedMap does not suffer from this issue since it is based on Vector instead of FreeList, and Vector's Iterator is optimised for efficient seeking using nth.

@austinabell Could you help to shed some light on the motivation for using FreeList over Vector for new store collections? Did you have any solution for dealing with iteration/slicing efficiently?

[austinabell]

It's a tradeoff, yes sth like skip iteration will be worse, but for removals for example, the old implementation does a lot of reads and writes to have to update all new indices for any element removed. (Note you can minimize the amount of reads/writes of this old implementation slightly, but all comes at the cost of breaking changes, which I wouldn't recommend)

There's no perfect solution, and decisions were made to optimize the most commonly used patterns. Possible those are incorrect or prohibitive in real world cases.

Also unclear why skip iteration is an important pattern for an unordered map, the ordering isn't stable. You just want to load values out of the maps in chunks or something?

[fadeevab]

@frol Indeed, collections::UnorderedMap's iterator works as expected, I've already verified it.

@austinabell

Also unclear why skip iteration is an important pattern for an unordered map, the ordering isn't stable. You just want to load values out of the maps in chunks or something?

1. One scenario is storing and iterating many data entries in chunks. Say, having 10k entries it's possible to iterate them by 1-2k per 1 call with collections::UnorderedMap and it's impossible with store::UnorderedMap which can never skip a few thousand entries because it's not lazy.

2. Another scenario: getting a random element in UnorderedMap - now, because of this issue, it became impossible within a big map, because nth(5000) element is not reachable because nth is not lazy and consumes too much gas jumping to the nth element.

Anyways, UnorderedMap provides an iterator that should meet Iterator API expectations. I can use LookupMap when I don't need iteration.

[frol]

Also unclear why skip iteration is an important pattern for an unordered map, the ordering isn't stable. You just want to load values out of the maps in chunks or something?

Well, the order is stable if one makes several requests at the same block height and the most common scenario is to fetch the data in pages, and it seems that the current implementation degrades the performance significantly turning it into a storage-inefficient LookupMap.

[frol]

@fadeevab What would be the ideal solution? I don't have the capacity to dive into it, do you?

[frol]

The challenges I see:

• Performance issue itself
• Migration plan for the existing contracts (or maybe give up and mark these collections as #[deprecated] with a clear message that iteration over these collections can be slow)

[ruseinov]

The challenges I see:

• Performance issue itself
• Migration plan for the existing contracts (or maybe give up and mark these collections as #[deprecated] with a clear message that iteration over these collections can be slow)

This seems like not too bad of a solution:

1. Add a defrag method for migrations.
2. Add a remove_defrag method for everything going forward. Or be opinionated and pack this functionality into remove.

What do you think @frol ?

[frol]

@ruseinov The issue is that self.unordered_map.iter().skip(100000).take(3) attempts to query at least 100003 keys even when FreeList is defragmented since there is no efficient .nth method implemented and so it just calls next() 100000 times for no good reason.

Quick ugly solution - implement .nth and if FreeList is defragmented, make it efficient, otherwise fallback to slow version. But I fear that there might be situation when defrag won't be able to complete within the gas limit and then what? And still, it sounds like a major footgun and you need to know how to heal it...

[ruseinov]

@ruseinov The issue is that self.unordered_map.iter().skip(100000).take(3) attempts to query at least 100003 keys even when FreeList is defragmented since there is no efficient .nth method implemented and so it just calls next() 100000 times for no good reason.

Quick ugly solution - implement .nth and if FreeList is defragmented, make it efficient, otherwise fallback to slow version. But I fear that there might be situation when defrag won't be able to complete within the gas limit and then what? And still, it sounds like a major footgun and you need to know how to heal it...

Yeah, I hear you. We could implement an alternative solution to defrag, but that'd require a migration that spans several blocks, which is a pain for several reasons. Though that in combination with the new logic would eventually lead to better performance for old contracts and good performance on fresh ones out of the box.

We could also make sure that the collection is using the old logic unless it's been defragmented, then a migration will be a soft requirement.
Another thing I thought about is that we could allow for partial defrag to limit gas used, but I need to see the current layout and the code to figure out if it's even possible. It does not seem like the migration mechanism supports a multi-block migration, though I'm not very familiar with it yet. Any solutions to keep calling defrag till it's finished, reserving some GAS on each block? We could easily implement a defrag(max_gas) to limit the amount of defrag that can be made per iteration. And add a fragmented: bool flag to the collection state. This way we could track the situation pretty good. This same flag would allow for executing different codepaths.

What are the alternatives.

1. @frol When you are talking about deprecating collections - which ones do you mean? store::UnorderedMap and FreeList? In which case we'll need to replace them with something new and those names would be forever lost. But that can be fixed by versioning or changing namespace, e.g. store::v2::UnorderedMap.
2. .. not sure what else could be done here.

[fadeevab]

Seems like the whole point of the redesigned store::UnorderedMap (with FreeList) was optimizing the removal operation making removal super fast.

@frol I imagine someone may need such a map for small collections: quick removals, periodic defrags in a single block, etc. From my perspective, the ideal solution would be renaming the store::UnorderedMap into DefragMap/SmallMap/etc. just for repurposing (with tons of disclaimers). (@ruseinov it basically goes with what you propose as an alternative).

On a side note, I found a nice improvement to the collections::UnordredMap which could be added: a pop operation - despite it sounds weird but if you need to clean the map randomly, it's faster by removing from that tail, ~O(1) :) (because it doesn't need rearranging the key indexes map).

[ruseinov]

On a side note, I found a nice improvement to the collections::UnordredMap which could be added: a pop operation - despite it sounds weird but if you need to clean the map randomly, it's faster by removing from that tail, ~O(1) :) (because it doesn't need rearranging the key indexes map).

I'm not sure what the purpose of this would be, if you'd want to clean the map randomly - might as well clear it, right? Because it means that data it stores does not matter, unless I'm missing the point here.

Seems like the whole point of the redesigned store::UnorderedMap (with FreeList) was optimizing the removal operation making removal super fast.

We might need to revisit this to see exactly how much faster it ends up being and what purpose it serves. I reckon if we're talking small collections - there are other collections that could be used. If the collection is big and it becomes fragmented due to removes - then what's the point of this optimisation?

Let's imagine some scenarios:

1. There is a big collection that has it's elements removed on occasion and gets fragmented. Sounds like a waste. Could be periodically defragged, but that's extra magic that should be hidden somewhere.
2. There is a big collection that pretty much never gets stuff removed from it. Why not disable the method and have another one that marks records as expired or something similar.
3. There is a small collection, we don't need to use a scalable UnorderedMap for this scenario at all.

Correct me if I'm wrong about the above.
I'd like to see the use-cases that prove we need such optimisations in the first place. A trade-off that leaves the collection infinitely growing does not sound like a sustainable one.

@frol I imagine someone may need such a map for small collections: quick removals, periodic defrags in a single block, etc. From my perspective, the ideal solution would be renaming the store::UnorderedMap into DefragMap/SmallMap/etc. just for repurposing (with tons of disclaimers). (@ruseinov it basically goes with what you propose as an alternative).

Could be done, but then that means that for older contracts they'd need to re-integrate and rename + still do a migration of some sort. Plus if we want to use the same name/namespace for the new collection - some of that stuff could get lost in translation and things won't get migrated at all, potentially causing the data to be either corrupt or fragmented.

There's another truth, all the contracts that currently use UnorderedMap could be upgraded to a new one that would start defragmenting itself upon removal, so they would stop growing unnecessarily. But we still need to provide the migration option.

[fadeevab]

I'm not sure what the purpose of this would be, if you'd want to clean the map randomly - might as well clear it, right? Because it means that data it stores does not matter, unless I'm missing the point here.

@ruseinov You miss the point that it can't clear more than ~2-3k elements per block. The same problem as with defrag which can't defrag the entire collection with 10k elements. clean will desperately fail exceeding the gas limit.

[ruseinov]

@ruseinov You miss the point that it can't clear more than ~2-3k elements per block. The same problem as with defrag which can't defrag the entire collection with 10k elements. clean will desperately fail exceeding the gas limit.

I have mentioned about defrag that it can be limited to max consumed gas and do partial defrag.

Is it not possible to just drop the whole data structure without actually having to delete each element? In theory that should be cheaper, depending on how those are stored.

[fadeevab]

@ruseinov Then we miss the following real use case: I want to select 1k random elements, process them and drop. clear can be optimized the way you mentioned in any case.

Let's not discuss popproposal too much here, because it doesn't solve this particular issue/ticket :) I rather have to create another feature requests.

[ruseinov]

@ruseinov Then we miss the following real use case: I want to select 1k random elements, process them and drop. clear can be optimized the way you mentioned in any case.

Let's not discuss popproposal too much here, because it doesn't solve this particular issue/ticket :) I rather have to create another feature requests.

Yes, let's not do this here. Please create an issue for that. Though using a collection like that as a queue with random reads makes very little sense to me, I can't think of a case where it's useful. Unless the queue is guaranteed to be exhausted, then it's probably small enough to use a different collection altogether.

Let's get back on track and figure out how to fix the original issue.

[ruseinov]

I've been thinking about this more, I guess we should go with defrag the element on remove approach. Here's why:

1. If a collection is rarely removed from, then why should we care much about performance?
2. If a collection is removed from often - then it makes even less sense, because it will consume more and more unjustified storage.

I still have to investigate performance implications of that though. And there's still a question of defrag migrations, I'd like to hear from somebody who has migration experience to see if there is a way to do a multi-block/partial migration trick.

[fadeevab]

@ruseinov The fastest "defrag on remove" approach is "swap remove" which is already implemented in collections::UnorderedMap for removals.

I believe that either someone really needed often fast removals (though you think it makes no sense) and we have to keep the current structure under another name (as I mentioned here #1134 (comment)), or it was unfortunate optimisation attempt which led to more optimizations like defrag which led to this ticket and it means the map should be deprecated (as @frol mentioned here #1134 (comment)).

[ruseinov]

@ruseinov The fastest "defrag on remove" approach is "swap remove" which is already implemented in collections::UnorderedMap for removals.

I believe that either someone really needed often fast removals (though you think it makes no sense) and we have to keep the current structure under another name (as I mentioned here #1134 (comment)), or it was unfortunate optimisation attempt which led to more optimizations like defrag which led to this ticket and it means the map should be deprecated (as @frol mentioned here #1134 (comment)).

Indeed, I didn't realize that defrag has already been implemented. Looking at all of this now I'd say it's probably easier to deprecate this altogether (store::{UnorderedSet, UnorderedMap}) or indeed rename it. At the very least these collections have to have a different name, otherwise it's confusing, especially considering implementation and performance differences.

If we opt for a rename - it's probably useful to mention trade-offs directly in module documentation. It is mentioned in the comment to remove method, but that seems easy to overlook.

[ruseinov]

If we opt for a rename - it's probably useful to mention trade-offs directly in module documentation. It is mentioned in the comment to remove method, but that seems easy to overlook.

I'll raise a draft PR with a rename an additional comments.

[frol]

@ruseinov @fadeevab I feel that store::Unordered* collections do not match the use-case they were designed for:

near-sdk-rs/near-sdk/src/store/unordered_map/mod.rs

Lines 19 to 21 in e78e06a

	/// A lazily loaded storage map that stores its content directly on the storage trie.
	/// This structure is similar to [`near_sdk::store::LookupMap`](crate::store::LookupMap), except
	/// that it stores the keys so that [`UnorderedMap`] can be iterable.

If you cannot iterate after a certain size, it is pointless to use the collection, and LookupMap is more storage efficient if you don't need iteration.

So I see it in the following way:

1. Old contracts that use store::Unordered* collections are unlucky and their devs will have to plan their migration manually, if necessary
2. New contracts will benefit from having a correct store::Unordered* collections

We should provide Unordered* collections that provide a reliable iteration feature. We can avoid breaking changes by implementing versioning for the collection header, so a custom borsh deserializer will try to deserialize the new version first and fallback to the old version (and that will define if FreeList or the new implementation should be used). YET, I don't think the effort is worth it. Yet, I don't see a chance to reclaim store::Unordered* name, so even if we rename it in 5.0 release, I won't be comfortable introducing a new implementation with the same name store::UnorderedMap since it is too easy to miss the release or use some intermediate crate (such as near-contract-standards) that could use store::UnorderedMap and you would suddenly hit the state inconsistency after SDK upgrade.

That said, I suggest we just mark the store::Unordered* collections with #[deprecated] and clear message what is the issue there, and implement properly working Unordered collections with new names, e.g. store_v2::UnorderedMap or store::UnorderedMapV2 (other suggestions for naming are welcome!)

[ruseinov]

That said, I suggest we just mark the store::Unordered* collections with #[deprecated] and clear message what is the issue there, and implement properly working Unordered collections with new names, e.g. store_v2::UnorderedMap or store::UnorderedMapV2 (other suggestions for naming are welcome!)

Right, I would probably go for versioning the module name. It's really a pity that we can't type alias our way through it.

[fadeevab]

@frol

That said, I suggest we just mark the store::Unordered* collections with #[deprecated] and clear message what is the issue there, and implement properly working Unordered collections with new names, e.g. store_v2::UnorderedMap or store::UnorderedMapV2 (other suggestions for naming are welcome!)

I agree, and it's a pity that it happened.

By the way, UnorderedSet has also been affected. And TreeMap seems not affected, although it's experimental (FreeList seems used there as a "LookupMap with len()").

@ruseinov

I would probably go for versioning the module name.

Sad to lose the good package name, I would consider renaming the types, e.g. into IterableMap and IterableSet, I'm just not in favor of "v2" pattern in the symbol names. Overall, I'm 50/50, whatever.

[ruseinov]

@frol

That said, I suggest we just mark the store::Unordered* collections with #[deprecated] and clear message what is the issue there, and implement properly working Unordered collections with new names, e.g. store_v2::UnorderedMap or store::UnorderedMapV2 (other suggestions for naming are welcome!)

I agree, and it's a pity that it happened.

By the way, UnorderedSet has also been affected. And TreeMap seems not affected, although it's experimental (FreeList seems used there as a "LookupMap with len()").

@ruseinov

I would probably go for versioning the module name.

Sad to lose the good package name, I would consider renaming the types, e.g. into IterableMap and IterableSet, I'm just not in favor of "v2" pattern in the symbol names. Overall, I'm 50/50, whatever.

It's a matter of taste, I'd prefer a concise name for the struct and a version in module path (e.g. store::v2::UnorderedMap) than an ambiguous name.

[fadeevab]

@ruseinov store::v2:: looks fine.

[frol]

@fadeevab There are definitely pros and cons to various naming:

• versioned modules (store_v2:: or store::v2::) has a downside that after you import it, it is harder to spot if your code uses old or v2 version of the structs, also, it is not clear which module is actually newer store or store::v2 (as v2 might have been an old version and store is the re-export of the most recent version)
• versioned structs (UnorderedMapV2) is just ugly, and while it is more explicit, it is still not clear if it is an old one v2 or it is actually the latest one
• new name (IterableMap) adds even more naming to the plate in addition to collections::UnorderedMap, store::UnorderedMap which might be confusing, yet, I actually like the explicitness of the naming. Technically, UnorderedMap works according to its name, but looking at it now, I think that might have actually contributed to the fact that it is not really good for iterations

I like IterableMap the best out of all the above options.

[fadeevab]

I like IterableMap the best out of all the above options

@frol Cool, I'm keen to vote for this naming because it was my idea and because I made a room for myself to change my mind 😄

I'm just not in favor of "v2" pattern in the symbol names. Overall, I'm 50/50, whatever.

[ruseinov]

There is an alternative, we could move the old UnorderedMap into a v1 path and make it a breaking change.
Besides, since it's deprecated - it will throw errors anyway.

The issue I see with IterableMap is that it tells us pretty much nothing. Most of the map implementations are iterable, even the UnorderedMap that has performance issues. It's kinda generic.

Perhaps it's a good idea to think about a different name altogether. But then it would be great to rename the collections::UnorderedMap too. Or keep the naming as is and version it.

[ruseinov]

I'm assuming that we want to take this further and implement an actual map that will be optimised for iteration. Should a separate issue be created for that?

It would be nice to flesh out how exactly this should work though. FreeList does not seem like a good option since we've just deprecated both collections backed by it.

[fadeevab]

The issue I see with IterableMap is that it tells us pretty much nothing.

@ruseinov well, it tells us what we literally overlooked last time: iterableness. And it's a map.

[ruseinov]

The issue I see with IterableMap is that it tells us pretty much nothing.

@ruseinov well, it tells us what we literally overlooked last time: iterableness. And it's a map.

Nope, all that it tells us is that the map is iterable, as in could be iterated upon.

Frangible* tells us that a collection gets fragmented, that's informative. Why? Because all the others aren't.
When you call one collection an IterableMap and the other one is called UnorderedMap, and both can be iterated upon - it's not really informative.
The issue here is the fact that Iterable and Iterator are widely used terms and most collections implement means of iteration upon them.

That's my personal opinion though, feel free to ignore it.

What's more important is what are the next steps here. Naming is difficult and can be improved upon going forward. Let's flesh out the logic for a new map if it's at all needed. We already have a collections::UnorderedMap and it would be nice to understand what would be the difference between that and a potential new collection, if any.

[frol]

We already have a collections::UnorderedMap and it would be nice to understand what would be the difference between that and a potential new collection, if any.

The whole idea of store over collections was the attempt to avoid the footgun:

struct {
  accounts: UnorderedMap<AccountId, UnorderedMap<TokenId, Balance>>
}

fn update(&mut self) {
    let account_tokens = self.accounts.get("frol.near").unwrap();
    account_tokens.insert("tkn", 10);
    // WARNING: Unless you do the following line, you get your state in a broken state since the key-value in account_tokens is updated, but the length is not updated
    self.accounts.insert("frol.near", account_tokens);
}

store API resolves this issue by implementing commit/flush on drop.

[frol]

When you call one collection an IterableMap and the other one is called UnorderedMap, and both can be iterated upon - it's not really informative.

1. I would deprecate UnorderedMaps after we extensively test new collections.
2. I would compare IterableMap not with UnorderedMap, but with LookupMap, which is not iterable, so when you contrast LookupMap with IterableMap it makes sense, at least to me.

[ruseinov]

The whole idea of store over collections was the attempt to avoid the footgun:

I'm going to throw some questions here as I'm trying to understand the current situation.

Any reason those collections (collections) have not been deprecated or modified? I fail to understand what's the point of having both store and collections, there might be something I don't know though.

How should the users know to avoid this footgun if both collections store their data on a trie and don't explicitly mention these differences?

I'm happy to take a stab at IterableMap, once we get rid of Unordered* and indeed compare it to LookupMap it will start making sense.

[frol]

Any reason those collections (collections) have not been deprecated or modified?

It is just a lack of testing for store types. The goal was to deprecate old collections once store is tested. It would be awesome if you can take a lead here!

[fadeevab]

Also, methods of store:: types are compatible with std HashMap methods, while collections:: maps are not, such compatibility should not be lost...

[ruseinov]

@fadeevab @frol
Let's recap what we want to achieve here to be able to estimate this better:

1. keep this compatible with HashMap.
2. provide "the best of two worlds" functionality here - commits similar to store::UnorderedMap, but iteration similar to collections::UnorderedMap.
3. good coverage, similar to collections::UnorderedMap.

Something else I'm missing?

[fadeevab]

@ruseinov yes, looks good...

[frol]

@ruseinov Looks good to me

[robert-zaremba]

Yeah, I encountered similar problem 1.5 year ago when I started to use the "new" near_sdk::store in place of the "old" near_sdk::collections. Moreover, the store version tries to cache the data, and it's way more complicated.
I use and recommend near_sdk::collections everywhere.

[robert-zaremba]

I really thing we should take an advantage of the fact that we are using a tree for store and enable prefix scan rather adding limitations and making our life harder. I proposed this in: near/NEPs#515

In fact every DB is using a kind of a tree, so even if we will do commitment with a different structure, the DB will allow us to do prefix scan. TBH, all good DBs provide prefix scan feature.

[ruseinov]

I really thing we should take an advantage of the fact that we are using a tree for store and enable prefix scan rather adding limitations and making our life harder. I proposed this in: near/NEPs#515

In fact every DB is using a kind of a tree, so even if we will do commitment with a different structure, the DB will allow us to do prefix scan. TBH, all good DBs provide prefix scan feature.

It does not seem relevant to the current task, however a separate issue can be created.

@fadeevab @frol I've been looking into "migrating" collections::UnorderedMap to allow for flush functionality. It seems reasonable to use store::Vector for this. Or rather migrating store::UnorderedMap to a new key storage.

[frol]

@fadeevab Please, review and play with #1164