Uncaught NotFountError in List.js when notifying row 24 of observable store

[rhpijnacker]

See test program at https://gist.github.com/rhpijnacker/6520965.

The test program loads an OnDemandGrid with some data in an observable Memory store. When I notify that the object displayed at row 24 is updated via the store the following error occurs (in chrome):

Uncaught NotFoundError: An attempt was made to reference a Node in a context where it does not exist. List.js:597

and the row disappears. When I try the same for row 25 the error does not occur, but the row still disappears.

Ronald

[kfranqueiro]

This particular case is the same as the original case reported in #701, which has been fixed. That said, we know there are still Observable-related pains in general and will be exploring options as the opportunity arises.

[kfranqueiro]

To be clear, I can't reproduce the issue in the test case provided in dgrid 0.3.10. It was reproducible in 0.3.9.

[rhpijnacker]

Hi Keith,

Thanks for having a look.
I checked with dgrid 0.3.10 and indeed the problem at row 24 (id 23) seems to be solved.
However, if I use the same test and update rows 25 and 26 in order the problem still occurs for me.
If I only update row 26 the error does not show, but the row disappears.

Could you have another look?

[kfranqueiro]

Yeah, I realize there are still other related problems, which is why we haven't closed #701 yet. Unfortunately these problems are ultimately trying to work around an annoyingly unhelpful behavior in dojo/store/Observable (I dare say it's a bug, but its maintainer seems to disagree with me on that), and every time we try to fix it, it just pops up somewhere else.

[dmartin-gh]

It's absolutely a bug. Given two observed result sets with one overlapping item (the last item in the first array and the first item in the second array), an update to that item causes dojo/store/Observable to notify both result sets with to=-1. They can't both drop the item on the floor, that doesn't make sense. Increasing queryRowOverlap to 2 or 3 allows you to make it through an update or two, but since the result sets change size and allow the overlapping items to be removed one-by-one, eventually the issue resurfaces.

We're using dgrid internally in a very dynamic fashion, with rows being added, updated and removed constantly. We've found that dojo/store/Observable is not stable enough to handle that without significant hacks (which is what we've ended up doing). If the maintainer disagrees, I'm baffled as to their reasoning. Unfortunately this also means that OnDemandList is plagued with constant stability and regression concerns.

The dojo/store API is great and I think a stable Observable wrapper is absolutely possible, but with serious issues sitting stale in the Dojo tracker for a year and a half, I think dgrid's best option at this point is to fork and maintain Observable.js on its own for a while. Maybe after some time and perceived improvement, those changes will be merged back into the dojo core.

We can't mark our internal UIs as stable until this gets resolved, so I'm willing to help as needed. What are your thoughts Ken?

[dmartin-gh]

I've studied dojo/store/Observable a bit more and I believe I know why this hasn't been fixed. From what I can see, there's no easy way (or even a way at all) to fix Observable.js.

dojo/store/Observable problems

Observable tries to be as efficient as possible regarding the amount of data it needs to work with. Each result set is completely separate from others: two result sets with the same query and sort but different paging options do not know about each other. These result sets can be updated in any order, and do not retain any state regarding how other similar result sets maybe have processed a change. It is up to each individual result set to analyze object changes, attempt to place them in their set and make a call as to whether or not the object lies inside of the slice of the world they are aware of. It an item ends up on the boundaries, it has no choice but to assume it should be handled elsewhere. Even if the object was correctly sorted on the boundary of that result set before the update, if the object changed it may be sorted farther in that direction with unknown objects in between. The only cases where it is safe to make a call is if the object sorts at the top of the first result set or the bottom of the last result set, in which case the object can safely be inserted at the edge.

Inserting at the bottom is buggy. It uses an atEnd variable to determine whether or not this result set is viewing the final page of data in the store. This variable is set to true if the cardinality of the set does not equal the number of items requested via options.count. That means that as soon as you add or remove an object to the set, atEnd becomes true for later changes. It also means that if the last page of your data just happens to exactly fill the number of items requested, atEnd will be false when it should have been true.

It is also a problem that result sets do not honor their start/count values as time passes. With items constantly being added or removed, the sets are allowed to grow and shrink accordingly. Some may grow indefinitely if you leave your scroll position still and continue to insert rows. Some may be reduced to empty sets, at which time it is up to the consumer to recognize that state and remove that set from use. This leads to drastically overcomplicated code on the consumer's end as it attempts to handle all possible combinations of set mutations.

We've inserted a counter into our dgrid instances that monitors how many result sets and observers are active for the grid as the user scrolls around and makes data changes. The number stays reasonable at first, but after a short time of use the observer count explodes until you refresh the grid. This is because dgrid is forced to manage a changing set of observers as data is mutated, a complicated endeavor that is easy to get wrong. It should instead be able to query the pages it needs for the given scroll position and be guaranteed that those pages will not change in size or start position as updates are processed.

If the desire is to maintain that each result set is completely independent of others, I do not see a solution to these problems. You can attempt to work around it with fancy tricks implemented in the query's consumer, but this will likely only hold up through a couple updates before breaking down. The only solution I see is a re-work of how queries are processed.

Possible solution

Keep in mind this is just an idea, there may be pitfalls here I haven't foreseen.

For a given query, you already have to process and sort all filtered items before conducting the slice. This is inefficient for rapid queries because you end up doing the query and the large sort for each individual page, even if the data hasn't changed in between the queries. The slicing should be removed from query() and added as a method to the QueryResults object called slice(). The QueryResults object should keep track of all slices taken against its results.

Observable.js should override this and return an ObservableQueryResults object. This object modifies the master results array as objects change. Since this query is not yet sliced, it can easily determine, without any guess-work, what the result position of each object should be. It will then be responsible for notifying each individual slice it has registered of the change. These notifications will tell the slices how to remain stable after the update. This means that even if the object was inserted into a page before this slice, this slice will receive two updates:

1. an insert at the top, shifting the last item from the previous page into this page
2. a remove from the bottom, shifting the last item on this page to the next page (unless this is the end).

Note that atEnd is now managed by the ObservableQueryResults object. The slice itself does not need to know whether or not it is the last page as the parent ObservableQueryResults is instructing it on how to update itself.

In dgrid, this will have the side-effect of causing rows to flow as updates occur outside of the viewport. I believe this is a good thing, as it maintains the stability of the pages you are viewing and removes the need for any user-end collision logic as you attempt to scroll and resolve inconsistencies.

This approach is fine for Memory stores where everything already lives in the browser, but how does this affect JsonRest stores? Does the ObservableQueryResults maintain the list on the server-side or the client-side? Maintaining and updating the list server-side would retain the current advantage of JsonRest stores: we only upload the resulting pages to the client to reduce bandwidth. However, this increases load on the server and requires that it manage data until the client tells it to stop (or stops requesting updates for some amount of time). An alternative is to bring the entire unsliced result set into the browser and manage it there. This reduces the computational load on the server but increases the bandwidth required, making it unfeasible for larger data sets. My suggestion is that we support both and let the user decide.

JsonRest store aside, this approach to slicing and updating would allow users to make solid assumptions regarding the pages they request:

• They cannot change in size (except the last page)
• They will shift to maintain their position

Yes, this means there is now a larger amount of notification noise. However, this is what is necessary to get a stable experience through any sort of heavy updating. The slices no longer need to make guess-work about where updates should be placed. There is instead a middle-man between the store and the slice, the ObservableQueryResults, that has all the information necessary to make correct update notifications.

Thoughts on this? Is there already something similar in the works?

[kfranqueiro]

Thanks for your feedback. In terms of the problems, you've hit the nail on the head pretty much, and I'm kind of relieved to see another person in the community recognize this for what it is - difficulties caused by how Observable works (or doesn't), not by dgrid itself. It just so happens that I think dgrid was the first thing that gave paged results a significant stress-test.

I have discussed some of these problems with Kris Zyp (the owner/author of dojo/store, as well as the original author of dgrid), and there are ongoing efforts to create a better implementation of Observable, as we try to iterate on the implementation of stores in general. I don't know that it necessarily incorporates all of your ideas here, but the notion of Observable tracking the full result set and slicing it is definitely a part of it.

I've pondered about the notion of consistent-sized "sliding windows" as well - I don't know that that idea has presently made it into Kris' plans, but I'll see about bringing it up.

I also agree that unfortunately Observable (and query engines) tends to fall flat in the case of server-based stores like JsonRest, since it doesn't know all of the data, and collecting all of the data client-side up-front is untenable as it would completely defeat the purpose of using a server-based store to begin with.

Unfortunately this leaves dgrid in a difficult position currently - knowing that work is in progress to resolve at least some of these issues, it seems like a bad idea to duplicate this effort in the dgrid repository itself. We'll certainly be interested in migrating to the improved APIs once it is feasible to do so.

In the meantime, one thought I have had - which is really kind of a last-ditch compromise - is to offer an option to react to notify calls directly rather than use observe. On the plus side, you would always know exactly whether an item is being added, updated, or removed. On the other hand, you won't know anything about the correct position of the item.

What I was sort of thinking was that we could have an option to enable a mode where dgrid would always reflect updates in-place, regardless of whether the item's order under the current sort would actually be affected by the change (since I have to imagine that in many cases, it wouldn't). This would still leave a question as to what exactly to do with added items, however, and it could also present inconsistency problems for paging (i.e. an item updated in place, but it actually really belonged a page up - now move up a page and see the item again when that page is rendered).

Unfortunately this would be kind of a weak compromise for the time being. It would also ideally rely on some amount of refactoring that I'm not terribly comfortable shoving into the 0.3 line. I've had some ideas for 0.4 but need to get a chunk of time to really hit the ground running with it.

I had originally closed this to track this issue in #701 since it is really the same issue. Given that this feedback has come in here though, I suppose I'll reopen it.

[kriszyp]

FWIW, these are great suggestions, and for the most part match pretty closely to what we are planning for improvements to observable object stores (with the exception of sliding windows, which I believe incurs unacceptable costs of additional requests for server side stores), in particular the idea of observing a top level result set and slicing off pages so that Observable can coordinate between pages.

BTW, does #488 mitigate this particular issue at all?

[jdawsongit]

Kris, could you elaborate on the additional costs imposed by server-side stores? If there is a server-side store and it already must notify all connected clients when the data changes, it's not obvious to me why dynamically-sized windows are cheaper than sliding windows.

From my point of view, the paramount concern is reliability and correctness.

My company has used Dgrid to build an alert tracker app, so the thousands of alerts that come in per day can be viewed by our support staff, and tracked with workflow (i.e. who owns it right now? has it been dealt with yet? etc.) By the way - thank you! The feature set of Dgrid is incredible, and users love our app.

We have encountered myriad Dgrid and/or Observable bugs, in scenarios like this:

1. Inserting/removing rows at the top of the grid
2. Inserting/removing rows at the bottom of the grid
3. Removing the "overlap" row between two query results
4. Grid transitions from empty to non-empty or vice-versa
5. Making scrolling to the bottom of the grid "sticky" so when new rows get inserted it keeps scrolling down, much like terminal windows do
6. When lots of rows are removed, the store doesn't always re-query, thus resulting in blank white grid space

Some, not all, of these bugs have been resolved by fixes you guys have made to Dojo or Dgrid. I'm willing to spend the time to understand the code, fix a bug, and submit a pull request. But the current data design of Observable is such that it sometimes seems like a finger-pointing game about what part of the code is at fault. A row didn't appear. Who exactly was responsible? What, that was supposed to happen, didn't happen? We've found this determination hard to make, in multiple cases. Consequently, some of the fixes we've created have been questionable hacks, and thus haven't been submitted back to Dojo/Dgrid.

One of the chief virtues of sliding windows is that they establish clear expectations for what the data should look like at any point in time, with easy-to-understand code invariants. For example, I can imagine how much simpler the Dgrid code would be if it could rely on invariants like this:

1. The full query is materialized into what Kris calls a top-level result set. I might call this thing a "materialized view" or maybe a "materialized query", since that's how I've heard it referred to before, in database products and literature. All changes to the store update this materialized query.
2. A materialized query can be sliced into Pages, each with a fixed offset position (start) and max size (count).
3. Each Page is a Javascript array, with other methods/fields to augment it.
4. Each Page array is dynamically sized: it can shrink to zero elements (if start is at or after the current size of the materialized query results), and can grow up to a max size of count.
5. Pages may be observed, so a callback function is called when the data in any page's data region changes.
6. If an object is inserted or removed in the materialized query, this will be visible independently in each Page, by between 0 and 2 add/update/remove callback invocations.
7. Each Dgrid instance keeps a list of Pages, which have contiguous, non-overlapping rows, and all with the same count.

It seems like with this as a foundation, the code to handle any kind of data store update would be straightforward. Having invariants like this can simplify adding and removing rows at any point:

1. When the last Page we're observing fills up, add another Page, so new rows can always have a non-empty Page to arrive in
2. When removing a row, keep the invariant that we never have more than one fully-empty Page. If we have lots of pages in our viewport, but start deleting rows, the Pages do get removed in an orderly, predictable way

If, on the other hand, we had a situation like we have right now, where Dgrid has queries that overlap by one row, and we auto-size the query results, it's hard to predict how the data will look at any point in time, and it's hard to cover all the edge cases. I feel like if this were a reasonable model to program in, the bugs where rows vanish and/or move around unpredictably would have been fixed by now, given all the eyeballs that have been looking at it.

[kfranqueiro]

Kris has done a great job implementing logic to counteract the dropping of items at boundaries by dojo/store/Observable. We should be able to remove this logic in a future version of dgrid when we update to use the next generation of stores.

[rhpijnacker]

Hi guys,

Thanks for the hard work.
I've been testing the solution today, and unfortunately I'm still seeing some issues. For example: sometimes when the store gets notified rows disappear. In other cases the rows are not re-rendered. In all these cases refresing the grid resolves the issues, but that is a bit unsafisfactory as a final solution.

I will try to come up with a test program that reproduces these problems and let you know.

Thanks again,

Ronald

[rhpijnacker]

I updated the test program at https://gist.github.com/rhpijnacker/6520965 to demonstrate the problem. At the end there are a number of 'notify()' calls. Depending on the number of times it is called more (or less) rows disappear.
The expected result is that the 'id' column always contains entries from 0 to 99 (increasing).

Ronald

[aothms]

We encountered similar issues similar to the snippet provided above. We had to revert back to v0.3.11 to circumvent the issues. Is there another workaround or an indication when this will be addressed?

Thanks,
Thomas

[kfranqueiro]

I believe there were a couple of commits after @rhpijnacker's comment, which may have addressed the further issues noticed at that time. I'm not able to see any missing indices with his test page now.

@aothms, can you provide a test case that demonstrates the issue you're seeing? Does it happen to be the same issue as #859?

[aothms]

Hi Kenneth, I can't tell whether this is a duplicate, opened a new issue here: #862 to be sure.

Thanks,
Thomas

[kfranqueiro]

Not really a duplicate, but certainly a regression. I'll continue tracking that there, and close this. Thanks.