Re: (ITS#8221) getting MDB_PAGE_FULL using mdb_cursor_del

[hyc@symas.com]

sergej.jurecko@gmail.com wrote:
> Full_Name: Sergej Jurečko
> Version: lmdb 0.9.16
> OS: osx
> URL: ftp://ftp.openldap.org/incoming/delerror.zip
> Submission from: (NULL) (193.189.172.218)
>
>
> Code and lmdb file is uploaded to ftp. Code is also here:
> https://gist.github.com/SergejJurecko/68979ff6460806581ad5
>
> If you run the code on the uploaded lmdb file, it will result in MDB_PAGE_FULL
> error out of mdb_cursor_del.
>
> I use dupsorts a lot in my app. Every value in the dupsort has 2 64bit integers
> and 1 u8 in the beginning, which are used in the custom comparison function to
> sort the values.
>
> During normal operation values are added to the end of the dupsort and
> eventually a cleanup operation occurs that deletes unused values.
>
> The example app tries to delete the first value in the dupsort. But it will fail
> the same if it tries to delete the next one instead.

Thanks for the code and data, it shows the problem pretty clearly. 
Unfortunately the solution is less obvious at the moment, still working on it.

The situation is this: deleting the record causes the leaf page to become too 
empty, so it gets merged with a neighboring page - this is no problem. The 
merge causes its parent branch page to also become too empty, so that is also 
merged with a neighboring branch page. This is where the problem arises:

In a branch page, the key for slot 0 is always empty - it's never stored. So 
we have two branch pages, each with two nodes, and node 0 of each is 
essentially zero length. But when merging, we need to store a valid key.
We go from
   page 1, slot 0; page 1, slot 1;  and page 2, slot 0; page 2, slot 1
to
   page 1, slot 0, slot 1, slot 2, slot 3

In this case, we have to retrieve the key corresponding to page 2 slot 0 and 
store it in page 1 slot 2. In this DB this key is very large, and storing it 
leaves no room for the last key in slot 3.





-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/