Repository navigation
The new MDB_UNSIGNEDKEY DbiFlag should probably be the default behaviour #249
Description
This issue relates to this PR #199 (which addressed this issue #198) and the subsequent PR #237 that added MDB_UNSIGNED_KEY.
We have recently upgraded to 0.9.1 (thanks for this release and the fixes in it) and found that a number of our tests are failing due to cursor start/stop key comparisons. Adding the MDB_UNSIGNEDKEY DbiFlag fixes them however it feels like the old compareBuff comparator ought to be the default rather than ByteBuffer.compareTo.
While I appreciate it is preferable to use methods from the JDK rather than hand rolled comparators, this is only the case IF the JDK methods behave in the same way as the existing code, which they don't. As @benalexau pointed out in the PR, ByteBuffer.compareTo is signed while compareBuff is unsigned. The latter matches the way LMDB orders its entries while the former does not.
It is hard to see a case where you would want to use a comparator for the cursor start/stop keys that does not match that used for the iteration order imposed by LMDB's default comparator. Maybe if you are only dealing with positive signed numbers they would match, but in that case, you would be better using MDB_INTEGER_kEY for the better performance. There is always the option to use no stop key and to instead use your own code to determine when to break out of the cursor iteration.
This problem is not just limited to numbers. As an example, if your key was a UTF16 string and you had keys:
0x00 0x00 // a null char
0xFF 0xFD // a � char
They would appear in the DB in that order, but the ByteBuffer.compareTo would treat 0xFF 0xFD as being the lower of the two.
If MDB_UNSIGNEDKEY is not set then it can lead to strange behaviour when using cursors that is highly value dependant, and thus tricky to fix. A crude performance test between the two ByteBuffer comparators suggests that the JDK is only marginally quicker.
It may be preferable to return compareBuff to being the default (when no callback comparator is used) but to use the JDK comparators by setting a flag, essentially the opposite of what is in 0.9.1. I.e. the developer is making an explicit choice to get the slight performance gain of the JDK method with the understanding that it comes with risks. If they know their data fits within the constraints then it is ok.
One other option is not to use a java based comparator for the cursor start/stop keys and instead call down to this method on LMDB so that you are sure the comparison is being done in the same way as the DB is storing its entries. I suspect that it would be more costly do make this call but you would at least be sure the comparison matched LMDB's.
int mdb_cmp (
MDB_txn * txn,
MDB_dbi dbi,
const MDB_val * a,
const MDB_val * b
)
Compare two data items according to a particular database.
This returns a comparison as if the two data items were keys in the specified database.
Parameters
[in] txn A transaction handle returned by mdb_txn_begin()
[in] dbi A database handle returned by mdb_dbi_open()
[in] a The first item to compare
[in] b The second item to compare
Returns
< 0 if a < b, 0 if a == b, > 0 if a > b
Happy to raise a PR address any changes that are agreed.
Activity
bp-alex commentedon Mar 6, 2025
Thanks for the detailed description and exploration of the alternatives.
Agreed. This is one reason we currently store the comparator in the
Dbiand apply it to allCursorIterableinstances for thatDbi. This change was made two years ago and I do not recall any tickets where users needed a different comparator for each cursor.Stepping back a little, the only situations we use a comparator are:
Dbiin the highly unusual situation that a user wants LMDB to call back into a Java-side comparatorCursorIterableso it can make Java-side decisions on iterationGiven these very narrow use cases, I wonder if the simplest approach might be to:
BufferProxyimplementations public so end users can directly access whichever comparator is most appropriate for their keys and they actually wish to make that decision for better Java-side performance duringCursorIterableoperationsDbistorenullfor the comparator if not provided by the user, noting the user can easily provide the now-public comparator of their choice viaEnv.openDbi(String, Comparator, DbiFlags...)if desiredDbicreates aCursorIterablewith anullcomparator, theCursorIterablewill delegate tomdb_cmp(a feasible approach given theCursorIterableis already bound to aTxnandDbi)This would seem to provide flexibility and a "no surprises" approach that is decoupled from
DbiFlags.Do you think this seems reasonable?
at055612 commentedon Mar 6, 2025
Tagging @danielcranford (who raised the original comparator issue) and @cdprete (who did the MDB_UNSIGNED_KEY PR) in case they have a view.
lmdbjavagh-249 Remove MDB_UNSIGNEDKEY, let CursorIterable call mdb_cmp
lmdbjavagh-249 Remove non-J8 features, use indent size 2
lmdbjavagh-249 Fix indents
cdprete commentedon Mar 6, 2025
It was also my personal preference to have it as the default behavior (see #230 (comment)), but then it would have been a breaking change in comparison to 0.9.0.
cdprete commentedon Mar 6, 2025
Having the comparators public is nice in terms of flexibility, but it wouldn't solve the main issue regarding the fact that the comparator needs to specified (the same "issue" as the new Dbi flag).
Moreover, if the LMDB comparator gets used as default, it may have quite some performance implications especially in low latency applications.
Therefore, instead of transparently default to it, I would raise an error and allow such a fallback only if some specific system property is set.
In this way, users updating to the version will really realize that something needs to be specified (either the sys prop or a comparator).
at055612 commentedon Mar 6, 2025
@cdprete In the PR is a performance test of the three comparator approaches (java, lmdb and callback). This inserts entries (both sequential and random order), then iterates over all of them with a stop key, thus exercising the stop key comparator. When run for 10mil entries in a single thread, after two warmup rounds we get this:
Random
Sequential
The overhead of calling the LMDB comparator is minimal, but ensures that the iterator is using the same comparison logic as LMDBs insertion order. Also, this overhead will only be when iterating with a CursorIterable that has a stop key to test. If your cursor is only iterating over 10s/100s of entries then it is negligible. It also ensures that any DBIFlags that alter the comparator on the LMDB side are a non-issue.
lmdbjavagh-249 Tidy code and refactor RangeComparator impls
lmdbjavagh-249 Remove commented code
cdprete commentedon Mar 6, 2025
I'm handling something like 30 million (in average) messages per second where I work, that's why performances are a concern for me.
By the way, I use a full key range as well, therefore the start key should also be taken into account (aka: it has to jump fast to the first matching key as well).
I'm not against removing the Dbi flag, but I'm just suggesting to make the user aware of the situation rather then applying under the hood some defaults which are, as well, difficult to debug and spot if you start to have performance issues.
lmdbjavagh-249 Add CursorIterableIntegerKeyTest
danielcranford commentedon Mar 7, 2025
Whew, I haven't looked at this since my original PR to use the intrinsic-ified JDK comparators. What a mess. I would have never made the suggestion if I knew the JDK provided comparators were doing signed comparisons. I presumed a "lexographic" comparison of arbitrary byte-strings was always unsigned. If a lexographic comparison is unsigned, the comparison algorithm is agnostic to the comparison chunk size, bit, nibble, byte, word, it's all the same.
Conversely, a signed lexographic comparison implies the size of the comparison chunk is part of the algorithm, which means it matters if your blob is a "sequence of bytes" vs a "sequence of int32".
bp-alex commentedon Mar 8, 2025
Thank you @at055612 for such a comprehensive PR #250 and ongoing discussion, along with @cdprete and @danielcranford for your comments and suggestions.
It is useful to see the performance degradation of delegating to
mdb_cmpis not particularly substantial, but unsurprisingly it does consistently exist in comparison with the Java comparator. @cdprete expressed concern with a new release of LmdbJava transparently defaulting to this less performant version, and I can understand this reservation for high volume use cases. In my applications I use LmdbJava for financial market data processing and it would similarly concern me if they suddenly slowed down without warning.Generally users are encouraged to review the Change Log before updating and of course this change would be mentioned there. However, I concede that in the real world most people are busy and experience library update fatigue and accordingly just bump the version of most libraries to see if they still work. As it would still work - just work more slowly - it is likely to be missed by a majority of users.
@cdprete proposed a system property to opt-in to this behaviour. There is reasonable given we already use system properties in various places, such as specifying which LMDB library to load.
Another way to do this would be to expose a
ComparatorPolicy<T>on theEnvmethods to replace the currentComparator<T>andnativeCbapproach. This would improve ergonomics as it would replace two method parameters with a single one, and prevent incompatible combinations (eg you cannot specify anativeCbwithout providing a Java comparator etc). TheComparatorPolicywould provide a variant for each legal possibility, ie delegate tomdb_cmp, use a Java comparator but without callback from LMDB, or use a Java comparator with callback from LMDB. ExistingDbimethods would default tomdb_cmpfor assured accuracy, with theComparatorPolicyrecording that it was transparently instantiated byEnvdue to this default behaviour. If the user later invokesCursorIterableusing the defaultmdb_cmpComparatorPolicy, it would raise an immediate exception. This in effect requires that a user opt into a specificComparatorPolicyin order to useCursorIterable, however users can do that simply explicitly selecting themdb_cmp(or any other)ComparatorPolicy, rather than relying on theEnv-selected default. Those users who do not use aCursorIterablewill never notice and can continue to rely on the defaults indefinitely. They'll only need to make a decision if and when they useCursorIterable. We would delete (or at least deprecate) the existingEnvmethods which accept aComparatorand/ornativeCb, as users passing those parameters probably have special reasons for doing so and making a decision to use an explicitComparatorPolicyis a simple and reasonable upgrade step.This is just one approach. If others have more ergonomic suggestions please feel free to chime in.
cdprete commentedon Mar 8, 2025
@benalexau we have the same use case then. :)
I agree, in general, but it depends on which version scheme is used. With SemVer, for example, I would expect that updating from 0.8.3 to 0.9 should introduce no breaking changes.
Also, in that specific example, "Refactor Comparator handling" in the changelog doesn't really say much on what has been changed and what the implications are.
I proposed it exactly because there is something like this already in place, so consistently would be maintained.
It doesn't sound bad to me.
Maybe, more than a policy it's actually a strategy, but the naming is the least of the problems here.
at055612 commentedon Mar 11, 2025
@cdprete
I think it is fair to say that none of us noticed that PR #199 would break things as it is value dependant (so the tests passed) and not obvious from looking at the
ByteBuffer.compareTojavadoc.@benalexau
An alternative to
ComparatorPolicy<T>would be to deprecate the existing openDbi methods and add in a set of staged builder classes that force the mandatory elements, e.g.i.e the first builder stage only allows the setting of the name, the second requires you to pick one of the three comparator methods and the last allows for optional setting of flags and/or opening. I think builders are preferable to heavily overloaded methods, especially if they control what methods the caller can use at each stage. It does however force the caller to pick an
xxxxComparator(method even if they are not doing anything with CursorIterable, but I don't think this is a big issue.Deprecating the existing
openDbimethods would not break things for people (in this release), but the IDE and changelog will show that something has changed and with sufficient javadoc they can pick thexxxxComparatormethod on the builder that fits their use case.On a semi related note, I noticed that
iteratorOp()is testing the cursor key against the start key on every iteration even after it has found/passed the start key. On a large iteration range this is a lot of unnecessary work. I have a PR that is work in progress to address this, but it depends on PR #250 and the discussed changes above so I will wait for them to be resolved before submitting. The main purpose of my PR was to add in the ability to make aKeyRangefor a key prefix. We use a lot of fixed length compound keys so having the ability to iterate over all keys with the same prefix is really useful and saves the caller having to work out the start/stop keys. It also means it can make use of the fasterequals()method on ByteBuffer slices. Whether this should have the option to delegate comparison of buffer slices to mdb_cmp is debatable is it is just doing simple equality.at055612/lmdbjava@mdb_cmp...at055612:lmdbjava:key-prefix
bp-alex commentedon Mar 11, 2025
@at055612 I prefer your builder idea. Would you be happy to add it into #250 (or a different PR) and I'll merge it?
at055612 commentedon Mar 12, 2025
@benalexau
Sure, no problem. Might be a few days as I need to find the time to fit it in.
cdprete commentedon Mar 14, 2025
I like the idea of the builder as well. +1
lmdbjavagh-249 Remove MaskedFlag.isPropagatedToLmdb, add DbiBuilder WIP
at055612 commentedon Nov 5, 2025
After a very long period of inactivity I am back on the case with this PR. Before I do a lot of refactoring of tests to use the builder, I wanted to check there were no major objections. The work in progress PR changes are here https://github.com/lmdbjava/lmdbjava/pull/276/files
The builder for the Dbi is a multi-stage one so we can ensure certain mandatory options are set.
Calling
env.createDbi()gives you the first stage with the following methodsThe next stage gives you these options.
The next stage gives you these options.
So in its simplest form
More typical cases would be
or
or
It does mean you will have to call
.withDefaultComparator()in 99% of cases, but Dbi creation is not something you do a lot in code and it makes the cursor behaviour nice and explicit.As part of this PR I have introduced the following
FlatSetimpls:DbiFlagSet,EnvFlagSet,PutFlagSet,TxnFlagSetandCopyFlagSet, and added new method overloads to accept these instead ofXxxFlags.... The reason for this is to pre-compute the combined maskintvalue for the set of flags, which avoids high frequency methods likeput()having to convert the varargs array of flags into a combined mask on each call. Users are unlikely to use many different combinations of flags, so theseXxxFlagSetinstances can be held statically and passed in to methods. The performance benefit is unlikely to be useful for low frequency things like EnvFlags and DbiFlags, but it makes things nice and consistent.Various existing methods that take
XxxFlags...have been deprecated to encourage users to switch, e.g.Each
XxxFlagsenum implements the correspondingXxxFlagSetso a single enum can be used in place of a XxxFlagSet, e.g.,PutFlags.MDB_APPENDcan be passed to a method that accepts PutFlagSet. Therefor you should only see deprecation warnings if you are passing 2 or more flags to a method.I have also deprecated most of the overloaded
open()methods onEnvandEnv.Builder, as it seems sensible for the existing builder to be used to capture the different combinations of settings. The preferredEnv.Builder.open(path)now takes aPathrather than aFile. e.g.ByteBufferProxy,DirectBufferProxyandByteBufProxyall now have two comparators each (for use as the default cursor iterator comparators). The comparator is chosen based on theDbiFlagsset on the Dbi. IfMDB_INTEGERKEYorMDB_INTEGERDUPis set, it will use a new dedicated integer key comparator else it will use the existing one. The new integer key comparator assumes the two buffers being compared have identical bytes remaining and are both in native order (which is how LMDB stores INTEGERKEY keys. These integer key comparators are slightly faster than our standard ones.Env.Buildernow has a newsetMapSize(final long mapSize, final ByteUnit byteUnit)method to make it easier to work with units other than bytes, e.g. KB, MB, etc.I've added tests to check that the new integer key comparators all behave the same as Long.compare and Integer.compare for many longs/ints.
Merge branch 'gh-267_plus_new_comparators' into gh-249-remove-unsigne…
Merge branch 'gh-249-remove-unsignedkey' of github.com:lmdbjava/lmdbj…
Merge branch 'gh-249-remove-unsignedkey' of github.com:lmdbjava/lmdbj…
cdprete commentedon Nov 13, 2025
Fine for me. Indeed, it's not an operation you do all the time.
Merge pull request #276 from lmdbjava/gh-249-remove-unsignedkey