ITS#8038 (syncrepl hanging onto its presentlist) only came to my attention due to the amount of memory involved. On a refresh of a DB with 2.8M entries I saw the consumer using about 320MB just for the presentlist. This list consists solely of 16 byte entryUUIDs; 2.8M items should have used no more than 48MB. An AVL node itself is 28 bytes on 64-bit platform, plus 16 bytes for the struct berval wrapped around the UUID. I'm looking into adding an in-memory B+tree library to liblutil. For the type of fixed-size records we're usually storing in AVL trees, a Btree will be much more compact and higher performance since it will need rebalancing far less frequently.

Emmanuel Lécharny wrote: > Le 29/01/15 04:20, Howard Chu a écrit : >> ITS#8038 (syncrepl hanging onto its presentlist) only came to my >> attention due to the amount of memory involved. On a refresh of a DB >> with 2.8M entries I saw the consumer using about 320MB just for the >> presentlist. This list consists solely of 16 byte entryUUIDs; 2.8M >> items should have used no more than 48MB. An AVL node itself is 28 >> bytes on 64-bit platform, plus 16 bytes for the struct berval wrapped >> around the UUID. >> >> I'm looking into adding an in-memory B+tree library to liblutil. For >> the type of fixed-size records we're usually storing in AVL trees, a >> Btree will be much more compact and higher performance since it will >> need rebalancing far less frequently. >> > Why using a B+tree ? A hash map wouldn't be a more appropriate data > structure ? EntryUUID ordering seems overkilling... I'm not fond of hashes, they're always cache-unfriendly and most of them have very poor dynamic growth behavior. Since we don't know in advance how many IDs are being stored, growth/resizing is a major concern. Tree structures are generally preferred because they have very good incremental growth performance, and B+trees have the best CPU cache behavior.