Hi John, Thank you! Question on the comment, where should I add the default implementation? I guess that needs to be added in the Proposal Section of the kIP.
Thanks! Sagar. On Sat, Jul 4, 2020 at 11:46 PM John Roesler <vvcep...@apache.org> wrote: > Thanks Sagar, > > That looks good to me! The only minor comment I’d make is that I think the > method declaration should have a default implementation that throws an > UnsupportedOperationException, for source compatibility with existing state > stores. > > Otherwise, as far as I’m concerned, I’m ready to vote. > > Thanks, > John > > On Sat, Jul 4, 2020, at 12:19, Sagar wrote: > > Hi John, > > > > I have updated the KIP with all the new changes we discussed in this > > discussion thread. > > > > > https://cwiki.apache.org/confluence/display/KAFKA/KIP-614%3A+Add+Prefix+Scan+support+for+State+Stores > > > > Request you to go through the same. > > > > Thanks! > > Sagar. > > > > On Tue, Jun 30, 2020 at 8:09 AM John Roesler <vvcep...@apache.org> > wrote: > > > > > Hi Sagar, > > > > > > That’s a good observation; yes, it should go in the > ReadOnlyKeyValueStore > > > interface. > > > > > > Thanks again for the great work, > > > John > > > > > > On Sun, Jun 28, 2020, at 23:54, Sagar wrote: > > > > Hi John, > > > > > > > > Thank you for the positive feedback! The meaningful discussions we > had on > > > > the mailing list helped me understand what needed to be done. > > > > > > > > I am definitely open to any further suggestions on this. > > > > > > > > Before I updated the KIP, I just had one question, is it fine to > have it > > > > for KeyValueStore or should I move it to ReadOnlyKeyValueStore where > even > > > > the range query resides? > > > > > > > > Regarding the 2 notes on UnsupportedOperationException and changing > the > > > > name to prefixScan, i will incorporate both of them into the KIP. > > > > > > > > Thanks! > > > > Sagar. > > > > > > > > On Sun, Jun 28, 2020 at 11:55 PM John Roesler <vvcep...@apache.org> > > > wrote: > > > > > > > > > Woah, this is great, Sagar! > > > > > > > > > > I think this API looks really good. I'm curious if anyone else has > > > > > any concern. For my part, I think this will work just fine. People > > > > > might face tricky bugs getting their key serde and their prefix > > > > > serde "aligned", but I think the API makes it pretty obvious what > > > > > has to happen to make this work. As long as the API isn't going > > > > > to "trick" anyone by trying to abstract away things that can't be > > > > > abstracted, this is the best we can do. In other words, I think > > > > > your approach is ideal here. > > > > > > > > > > I also really appreciate that you took the time to do a full POC > > > > > with end-to-end tests to show that the proposal is actually > > > > > going to work. > > > > > > > > > > A couple of notes as you update the KIP: > > > > > > > > > > 1. I think that for "optional" state store features like this, we > > > > > should add a default implementation to the interface that > > > > > throws UnsupportedOperationException. That way, > > > > > any existing store implementations won't fail to compile > > > > > on the new version. And any store that just can't support > > > > > a prefix scan would simply not override the method. > > > > > > > > > > 2. I think you meant "prefixScan", not "prefixSeek", since > > > > > we're actually getting an iterator that only returns prefix- > > > > > matching keys, as opposed to just seeking to that prefix. > > > > > > > > > > Thanks again for the work you've put into this. I look > > > > > forward to reviewing the updated KIP. > > > > > > > > > > Thanks, > > > > > -John > > > > > > > > > > > > > > > On Sun, Jun 28, 2020, at 12:17, Sagar wrote: > > > > > > Hi John, > > > > > > > > > > > > I took some time out and as we discussed, looked to implement > these > > > > > > changes. Most of these changes are for demonstrative purposes > but I > > > > > thought > > > > > > I will share. > > > > > > > > > > > > I added the new prefixSeek method at the KeyValueStore interface > > > level: > > > > > > > > > > > > > > > > > > > > > https://github.com/confluentinc/kafka/pull/242/files#diff-5e92747b506c868db3948323478e1b07R74-R83 > > > > > > > > > > > > As you had pointed out, the prefix type can be different from > the key > > > > > type. > > > > > > That's why this method takes 2 parameters. the key type and it's > > > > > serializer. > > > > > > > > > > > > Then I added the implementation of this method in a couple of > Stores. > > > > > > RocksDBStore: > > > > > > > > > > > > > > > > > > > > > https://github.com/confluentinc/kafka/pull/242/commits#diff-046ca566243518c88e007b7499ec9f51R308-R320 > > > > > > and > > > > > > InMemoryKVStore: > > > > > > > > > > > > > > > > > > > > > https://github.com/confluentinc/kafka/pull/242/commits#diff-4c685a32e765eab60bcb60097768104eR108-R120 > > > > > > > > > > > > I modified the older test cases for RocksDBStore. You can find > them > > > here: > > > > > > > > > > > > > > > > > > > > > https://github.com/confluentinc/kafka/pull/242/commits#diff-051439f56f0d6a12334d7e8cc4f66bf8R304-R415 > > > > > > > > > > > > > > > > > > I have added a test case where the keys are of type UUID while > the > > > prefix > > > > > > is of type string. This seems to be working because the code is > able > > > to > > > > > > pull in UUIDs with the provided prefix, even though their types > are > > > > > > different. > > > > > > > > > > > > To address one of the gaps from my previous implementation, I > have > > > also > > > > > > added a test case for the end to end flow using the state store > > > supplier. > > > > > > you can find it here: > > > > > > > > > > > > > > > > > > > > > https://github.com/confluentinc/kafka/pull/242/commits#diff-a94de5b2ec72d09ebac7183c31d7c906R269-R305 > > > > > > > > > > > > Note that for this to work, i needed to update MeteredKVstore and > > > > > > ChangeLoggingKVStore. > > > > > > > > > > > > Lastly, barring the 4 stores mentioned above, rest of the > > > implementers of > > > > > > KVStore have the prefixSeek override as null. As I said, this is > > > mainly > > > > > for > > > > > > demonstrative purposes and hence done this way. > > > > > > If you get the chance, it would be great if you can provide some > > > feedback > > > > > > on this. > > > > > > > > > > > > Thanks! > > > > > > Sagar. > > > > > > > > > > > > > > > > > > On Wed, Jun 10, 2020 at 9:21 AM Sagar <sagarmeansoc...@gmail.com > > > > > wrote: > > > > > > > > > > > > > Hi John, > > > > > > > > > > > > > > You rightly pointed out, the devil is in the detail :). I will > > > start > > > > > with > > > > > > > the implementation to get a sense. > > > > > > > > > > > > > > Here are my thoughts on the core challenge that you pointed > out. > > > The > > > > > key > > > > > > > value store abstractions that have been exposed via the state > > > store DSL > > > > > > > APIs, make it possible for the end user to define generic key > > > types. > > > > > > > However, the Serdes are the one which convert those generic > > > keys/values > > > > > > > into the format in which the state store stores them- which > for all > > > > > > > practical purposes are byte-arrays. I think with the prefix > type > > > > > serde, if > > > > > > > it converts the prefix to the same internal storage type (byte > > > array) > > > > > as > > > > > > > that of the Keys, then we should be able to do a prefix scan. > > > > > > > > > > > > > > Regarding other databases, I have worked a bit with Redis which > > > also > > > > > > > provides a scan operator using the glob style pattern > match(it's > > > more > > > > > > > evolved than prefix scan but can be converted easily): > > > > > > > > > > > > > > https://redis.io/commands/scan#the-match-option > > > > > > > > > > > > > > Typically Redis works with Binary Safe strings so the prefix > key > > > type > > > > > and > > > > > > > the actual keys are of the same type. > > > > > > > > > > > > > > Thanks! > > > > > > > Sagar. > > > > > > > > > > > > > > > > > > > > > > > > > > > > On Wed, Jun 10, 2020 at 1:41 AM John Roesler < > vvcep...@apache.org> > > > > > wrote: > > > > > > > > > > > > > >> Hi Sagar, > > > > > > >> > > > > > > >> Thanks for the reply. I agree that your UUID example > illustrates > > > the > > > > > > >> problem I was pointing out. > > > > > > >> > > > > > > >> Yes, I think that experimenting with the API in the PR is > > > probably the > > > > > > >> best way to make progress (as opposed to just thinking in > terms of > > > > > > >> design on the wiki) because with this kind of thing, the > devil is > > > > > often > > > > > > >> in the details. > > > > > > >> > > > > > > >> To clarify what I meant by that last statement, I see the core > > > > > challenge > > > > > > >> here as deriving from the fact that we have a key/value store > with > > > > > > >> generically typed keys, with a separate component (the serde) > that > > > > > > >> turns those typed keys into bytes for storage. In contrast, > > > RocksDB > > > > > > >> can easily offer a "prefix scan" operation because they key > type > > > is > > > > > > >> always just a byte array, so "prefix" is a very natural > concept to > > > > > offer > > > > > > >> in the API. Other key/value stores force the keys to always be > > > > > strings, > > > > > > >> which also makes it easy to define a prefix scan. > > > > > > >> > > > > > > >> My question is whether there are other databases that offer > both: > > > > > > >> 1. generically typed keys (as opposed to just bytes, just > strings, > > > > > etc) > > > > > > >> 2. prefix scans > > > > > > >> And, if so, what the API looks like. > > > > > > >> > > > > > > >> Thanks, > > > > > > >> -John > > > > > > >> > > > > > > >> On Tue, Jun 9, 2020, at 11:51, Sagar wrote: > > > > > > >> > Hi John, > > > > > > >> > > > > > > > >> > Thanks for the response. For starters, for our use case, we > > > tweaked > > > > > our > > > > > > >> > keys etc to avoid prefix scans. So, we are good there. > > > > > > >> > > > > > > > >> > Regarding the KIP, I see what you mean when you say that the > > > same > > > > > key > > > > > > >> type > > > > > > >> > for prefix won't work. For example, continuing with the UUID > > > example > > > > > > >> that > > > > > > >> > you gave, let's say one of the UUIDs > > > > > > >> > is 123e4567-e89b-12d3-a456-426614174000, and with a prefix > scan > > > we > > > > > want > > > > > > >> to > > > > > > >> > fetch all keys starting with 123. There's already a > UUIDSerde > > > so if > > > > > the > > > > > > >> > keys have been stored with that, then using UUIDSerde for > > > prefixes > > > > > won't > > > > > > >> > help- I am not sure if the UUIDSerializer would even work > for > > > 123. > > > > > > >> > > > > > > > >> > So, that indicates that we will need to provide a new > prefix key > > > > > type > > > > > > >> > serializer. Having said that, how it will be stitched > together > > > and > > > > > > >> finally > > > > > > >> > exposed using the APIs is something that is up for > questioning. > > > > > This is > > > > > > >> > something you have also brought up in the earlier emails. > If it > > > > > > >> > makes sense, I can modify my PR to go along these lines. > Please > > > let > > > > > me > > > > > > >> know > > > > > > >> > what you think. > > > > > > >> > > > > > > > >> > Lastly, I didn't understand this line of yours: *It might > help > > > if > > > > > there > > > > > > >> are > > > > > > >> > other typed key/value stores to compare APIs with.* > > > > > > >> > > > > > > > >> > Thanks! > > > > > > >> > Sagar. > > > > > > >> > > > > > > > >> > > > > > > > >> > On Thu, Jun 4, 2020 at 6:03 AM John Roesler < > > > vvcep...@apache.org> > > > > > > >> wrote: > > > > > > >> > > > > > > > >> > > Hi Sagar, > > > > > > >> > > > > > > > > >> > > Thanks for the question, and sorry for muddying the water. > > > > > > >> > > > > > > > > >> > > I meant the Bytes/byte[] thing as advice for how you all > can > > > solve > > > > > > >> your > > > > > > >> > > problem in the mean time, while we work through this KIP. > I > > > don’t > > > > > > >> think > > > > > > >> > > it’s relevant for the KIP itself. > > > > > > >> > > > > > > > > >> > > I think the big issue here is what the type of the prefix > > > should > > > > > be > > > > > > >> in the > > > > > > >> > > method signature. Using the same type as the key makes > sense > > > some > > > > > > >> times, > > > > > > >> > > but not other times. I’m not sure what the best way around > > > this > > > > > might > > > > > > >> be. > > > > > > >> > > It might help if there are other typed key/value stores to > > > compare > > > > > > >> APIs > > > > > > >> > > with. > > > > > > >> > > > > > > > > >> > > Thanks, > > > > > > >> > > John > > > > > > >> > > > > > > > > >> > > On Mon, Jun 1, 2020, at 09:58, Sagar wrote: > > > > > > >> > > > Hi John, > > > > > > >> > > > > > > > > > >> > > > Just to add to my previous email(and sorry for the > spam), > > > if we > > > > > > >> consider > > > > > > >> > > > using Bytes/byte[] and manually invoke the serdes, if > you > > > could > > > > > > >> provide > > > > > > >> > > > examples where the same Serde for keys won't work for > the > > > prefix > > > > > > >> types. > > > > > > >> > > As > > > > > > >> > > > far as my understanding goes, the prefix seek would > depend > > > upon > > > > > > >> ordering > > > > > > >> > > of > > > > > > >> > > > the keys like lexicographic. As long as the binary > format is > > > > > > >> consistent > > > > > > >> > > for > > > > > > >> > > > both the keys and the prefixes would it not ensure the > > > ability > > > > > to > > > > > > >> search > > > > > > >> > > in > > > > > > >> > > > that same ordering space? This is from my limited > > > understanding > > > > > so > > > > > > >> any > > > > > > >> > > > concrete examples would be helpful... > > > > > > >> > > > > > > > > > >> > > > Also, you mentioned about the creation of dummy values > to > > > > > indicate > > > > > > >> prefix > > > > > > >> > > > values, do you mean this line: > > > > > > >> > > > > > > > > > >> > > > > > > > > > >> > > > > > > > > >> > > > > > > > > > https://github.com/apache/kafka/blob/trunk/streams/src/main/java/org/apache/kafka/streams/kstream/internals/foreignkeyjoin/ForeignJoinSubscriptionProcessorSupplier.java#L91 > > > > > > >> > > > This > > > > > > >> > > > is where the prefix key is built and used for searching > . > > > > > > >> > > > > > > > > > >> > > > Thanks! > > > > > > >> > > > Sagar. > > > > > > >> > > > > > > > > > >> > > > On Mon, Jun 1, 2020 at 11:42 AM Sagar < > > > > > sagarmeansoc...@gmail.com> > > > > > > >> wrote: > > > > > > >> > > > > > > > > > >> > > > > Hi John, > > > > > > >> > > > > > > > > > > >> > > > > Thank you. I think it makes sense to modify the KIP to > > > add the > > > > > > >> > > > > prefixScan() as part of the existing interfaces and > add > > > the > > > > > new > > > > > > >> mixin > > > > > > >> > > > > behaviour as Rejected alternatives. I am not very > aware of > > > > > other > > > > > > >> stores > > > > > > >> > > > > apart from keyValueStore so is it fine if I keep it > there > > > for > > > > > now? > > > > > > >> > > > > > > > > > > >> > > > > Regarding the type definition of types I will try and > > > think > > > > > about > > > > > > >> some > > > > > > >> > > > > alternatives and share if I get any. > > > > > > >> > > > > > > > > > > >> > > > > Thanks! > > > > > > >> > > > > Sagar. > > > > > > >> > > > > > > > > > > >> > > > > > > > > > > >> > > > > On Sun, May 31, 2020 at 1:55 AM John Roesler < > > > > > vvcep...@apache.org > > > > > > >> > > > > > > > >> > > wrote: > > > > > > >> > > > > > > > > > > >> > > > >> Hi Sagar, > > > > > > >> > > > >> > > > > > > >> > > > >> Thanks for the response. Your use case makes sense to > > > me; I > > > > > > >> figured it > > > > > > >> > > > >> must be something like that. > > > > > > >> > > > >> > > > > > > >> > > > >> On a pragmatic level, in the near term, you might > > > consider > > > > > > >> basically > > > > > > >> > > > >> doing the same thing we did in KIP-213. If you swap > out > > > the > > > > > store > > > > > > >> > > types for > > > > > > >> > > > >> Byte/byte[] and “manually” invoke the serdes in your > own > > > > > logic, > > > > > > >> then > > > > > > >> > > you > > > > > > >> > > > >> can use the same algorithm we did to derive the range > > > scan > > > > > > >> boundaries > > > > > > >> > > from > > > > > > >> > > > >> your desired prefix. > > > > > > >> > > > >> > > > > > > >> > > > >> For the actual KIP, it seems like we would need > > > significant > > > > > > >> design > > > > > > >> > > > >> improvements to be able to do any mixins, so I think > we > > > > > should > > > > > > >> favor > > > > > > >> > > > >> proposing either to just add to the existing > interfaces > > > or to > > > > > > >> create > > > > > > >> > > brand > > > > > > >> > > > >> new interfaces, as appropriate, for now. Given that > > > prefix > > > > > can be > > > > > > >> > > converted > > > > > > >> > > > >> to a range query at a low level, I think we can > probably > > > > > explore > > > > > > >> > > adding > > > > > > >> > > > >> prefix to the existing interfaces with a default > > > > > implementation. > > > > > > >> > > > >> > > > > > > >> > > > >> It seems like that just leaves the question of how to > > > define > > > > > the > > > > > > >> type > > > > > > >> > > of > > > > > > >> > > > >> the prefix. To be honest, I don’t have any great > ideas > > > here. > > > > > Are > > > > > > >> you > > > > > > >> > > able > > > > > > >> > > > >> to generate some creative solutions, Sagar? > > > > > > >> > > > >> > > > > > > >> > > > >> Thanks, > > > > > > >> > > > >> John > > > > > > >> > > > >> > > > > > > >> > > > >> On Tue, May 26, 2020, at 06:42, Sagar wrote: > > > > > > >> > > > >> > Hi John, > > > > > > >> > > > >> > > > > > > > >> > > > >> > Thanks for the detailed reply. I was a bit crammed > with > > > > > work > > > > > > >> last > > > > > > >> > > week > > > > > > >> > > > >> so > > > > > > >> > > > >> > couldn't respond earlier so apologies for that. > > > > > > >> > > > >> > > > > > > > >> > > > >> > First of all, thanks for the context that both you > and > > > Adam > > > > > > >> have > > > > > > >> > > > >> > provided me on the issues faced previously. As I > can > > > > > clearly > > > > > > >> see, > > > > > > >> > > while > > > > > > >> > > > >> I > > > > > > >> > > > >> > was able to cut some corners while writing some > test > > > cases > > > > > or > > > > > > >> > > > >> benchmarks, > > > > > > >> > > > >> > to be able to stitch together a store with prefix > scan > > > > > into an > > > > > > >> > > actual > > > > > > >> > > > >> > topology needs more work. I am sorry for the half > baked > > > > > tests > > > > > > >> that I > > > > > > >> > > > >> wrote > > > > > > >> > > > >> > without realising and you have rightly put it when > you > > > said > > > > > > >> these > > > > > > >> > > > >> > challenges aren't obvious up front. > > > > > > >> > > > >> > > > > > > > >> > > > >> > Now, coming back to the other points, I spent some > time > > > > > going > > > > > > >> > > through > > > > > > >> > > > >> the > > > > > > >> > > > >> > KIP-213 and also some of the code snippets that are > > > talked > > > > > > >> about in > > > > > > >> > > that > > > > > > >> > > > >> > KIP. With the detailed explanation that you > provided, > > > it > > > > > is now > > > > > > >> > > obvious > > > > > > >> > > > >> to > > > > > > >> > > > >> > me that keeping a generic type for keys like K > won't > > > work > > > > > oob > > > > > > >> and > > > > > > >> > > hence > > > > > > >> > > > >> a > > > > > > >> > > > >> > decision was made to use Bytes as the key type. > > > > > > >> > > > >> > > > > > > > >> > > > >> > I just had another thought on this though. I > looked at > > > the > > > > > > >> range > > > > > > >> > > > >> function > > > > > > >> > > > >> > that was added in the ReadOnlyKeyValueStore. While > the > > > Key > > > > > and > > > > > > >> the > > > > > > >> > > Value > > > > > > >> > > > >> > mentioned in that method is generic, internally > almost > > > all > > > > > > >> queries > > > > > > >> > > end > > > > > > >> > > > >> up > > > > > > >> > > > >> > querying using Bytes in some or the other form. I > > > looked at > > > > > > >> not just > > > > > > >> > > > >> > RocksDb Store but other stores like InMemory store > or > > > > > > >> MemoryLRU and > > > > > > >> > > this > > > > > > >> > > > >> > seems to be the pattern. I think this stems from > the > > > fact > > > > > that > > > > > > >> these > > > > > > >> > > > >> stores > > > > > > >> > > > >> > while implementing KeyValueStore pass Bytes, > byte[] as > > > the > > > > > K > > > > > > >> and V > > > > > > >> > > > >> values. > > > > > > >> > > > >> > Classes like MeteredKeyValueStore which don't do > this, > > > > > still > > > > > > >> use > > > > > > >> > > > >> Bytes.wrap > > > > > > >> > > > >> > to wrap the passed keys and values and invoke the > range > > > > > method. > > > > > > >> > > > >> > > > > > > > >> > > > >> > So, the point I am trying to make is, with the same > > > > > behaviour > > > > > > >> - and > > > > > > >> > > > >> > ignoring for a moment that it's a separate > interface > > > which > > > > > I am > > > > > > >> > > trying > > > > > > >> > > > >> to > > > > > > >> > > > >> > "mix-in"- the issues with the key types could be > > > resolved. > > > > > I > > > > > > >> may be > > > > > > >> > > > >> wrong > > > > > > >> > > > >> > though so would like to know your thoughts on this. > > > Infact > > > > > > >> > > unknowingly > > > > > > >> > > > >> the > > > > > > >> > > > >> > interface implementation of PrefixSeekableType in > > > > > > >> RockDBStateStore > > > > > > >> > > also > > > > > > >> > > > >> > passes Bytes and bytes[] as K and V. > > > > > > >> > > > >> > > > > > > > >> > > > >> > The second part of exposing it via the publically > > > > > accessible > > > > > > >> > > interfaces > > > > > > >> > > > >> to > > > > > > >> > > > >> > which we downcast while building the topology (like > > > > > > >> KeyValueStore), > > > > > > >> > > I > > > > > > >> > > > >> can > > > > > > >> > > > >> > clearly see now that mixing-in the way I tried to > won't > > > > > work. > > > > > > >> My > > > > > > >> > > > >> intention > > > > > > >> > > > >> > all along was not to hamper the flow of those > stores > > > which > > > > > > >> don't > > > > > > >> > > support > > > > > > >> > > > >> > prefix scan as yet and hence the separate > interface. > > > But, I > > > > > > >> agree > > > > > > >> > > that > > > > > > >> > > > >> for > > > > > > >> > > > >> > this to work, it needs to be part of some > pre-defined > > > store > > > > > > >> types > > > > > > >> > > like > > > > > > >> > > > >> > KVStore etc. Right now, I don't have an answer to > this > > > but > > > > > > >> mostly it > > > > > > >> > > > >> would > > > > > > >> > > > >> > have to be moved there and implemented across all > > > > > stores(if we > > > > > > >> see > > > > > > >> > > the > > > > > > >> > > > >> > worth in prefix scans :) ) > > > > > > >> > > > >> > > > > > > > >> > > > >> > Regarding the motivation, I am sorry if I wasn't > clear. > > > > > This > > > > > > >> > > originated > > > > > > >> > > > >> > from one of my own use cases with kafka streams > where i > > > > > needed > > > > > > >> to > > > > > > >> > > find > > > > > > >> > > > >> some > > > > > > >> > > > >> > keys based upon certain prefix. Infact it's > similar to > > > the > > > > > > >> > > > >> > RangeScanCombinedKeyUsage diagram in KIP-213 where > the > > > > > > >> otherTable > > > > > > >> > > tries > > > > > > >> > > > >> to > > > > > > >> > > > >> > find entries in the state store based upon the FK. > I > > > was > > > > > using > > > > > > >> > > > >> > KevValueStore to be precise. I also remember > having a > > > slack > > > > > > >> > > > >> conversation on > > > > > > >> > > > >> > this, and I was told that this isn't supported > right > > > now, > > > > > but > > > > > > >> some > > > > > > >> > > other > > > > > > >> > > > >> > users shared their experiences on how with some > hacks > > > they > > > > > are > > > > > > >> able > > > > > > >> > > to > > > > > > >> > > > >> > perform prefix scans even though their use case > fits > > > the > > > > > bill > > > > > > >> for a > > > > > > >> > > > >> prefix > > > > > > >> > > > >> > scan. That kind of motivated me to take a stab at > it. > > > > > > >> > > Unfortunately, I > > > > > > >> > > > >> have > > > > > > >> > > > >> > lost the slack chat because of some cleanup at the > > > slack > > > > > > >> channel > > > > > > >> > > level. > > > > > > >> > > > >> I > > > > > > >> > > > >> > will try and update the ambiguous motivation > statement > > > in > > > > > the > > > > > > >> near > > > > > > >> > > > >> future. > > > > > > >> > > > >> > > > > > > > >> > > > >> > Lastly, I would like to point out, that your > response > > > was > > > > > not > > > > > > >> at all > > > > > > >> > > > >> > discouraging. On the contrary it was really > insightful > > > and > > > > > it's > > > > > > >> > > always > > > > > > >> > > > >> good > > > > > > >> > > > >> > to learn/discover new things :) > > > > > > >> > > > >> > > > > > > > >> > > > >> > Thanks! > > > > > > >> > > > >> > Sagar. > > > > > > >> > > > >> > > > > > > > >> > > > >> > On Fri, May 15, 2020 at 7:37 AM John Roesler < > > > > > > >> vvcep...@apache.org> > > > > > > >> > > > >> wrote: > > > > > > >> > > > >> > > > > > > > >> > > > >> > > Hi, Sagar! > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > Thanks for this KIP. I'm sorry it took me so > long to > > > > > reply. > > > > > > >> I'll > > > > > > >> > > > >> number my > > > > > > >> > > > >> > > points differently to avoid confusion. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > I can provide some additional context on the > > > > > difficulties we > > > > > > >> > > > >> previously > > > > > > >> > > > >> > > faced in KIP-213 (which you and Adam have already > > > > > discussed). > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > J1) In your KIP, you propose the following > interface: > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > public interface PrefixSeekableStore<K, V> { > > > > > > >> > > > >> > > KeyValueIterator<K, V> prefixSeek(K prefix); > > > > > > >> > > > >> > > } > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > This is roughly the same thing that Adam and I > were > > > > > > >> considering > > > > > > >> > > > >> > > before. It has a hidden problem, that it assumes > that > > > > > > >> prefixes of > > > > > > >> > > > >> > > keys in the key space are also in the key space. > In > > > other > > > > > > >> words, > > > > > > >> > > this > > > > > > >> > > > >> > > is a store with key type K, and the API assumes > that > > > > > > >> prefixes are > > > > > > >> > > also > > > > > > >> > > > >> > > of type K. This is true for some key types, like > > > String > > > > > or > > > > > > >> Bytes, > > > > > > >> > > but > > > > > > >> > > > >> not > > > > > > >> > > > >> > > for others. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > For example, if the keys are UUIDs, then no > prefix is > > > > > also a > > > > > > >> > > UUID. If > > > > > > >> > > > >> the > > > > > > >> > > > >> > > key is a complex data type, like Windowed<K> in > our > > > own > > > > > DSL, > > > > > > >> then > > > > > > >> > > > >> > > we would absolutely want to query all keys with > the > > > same > > > > > > >> record > > > > > > >> > > key > > > > > > >> > > > >> > > (the K part), or the same window start time, but > in > > > > > neither > > > > > > >> case > > > > > > >> > > is > > > > > > >> > > > >> the > > > > > > >> > > > >> > > prefix actually a Windowed<K>. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > You can skirt the issue by defining a third type > > > > > parameter, > > > > > > >> maybe > > > > > > >> > > KP, > > > > > > >> > > > >> that > > > > > > >> > > > >> > > is the "prefix" type, but this would also be > awkward > > > for > > > > > many > > > > > > >> > > usages. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > J2) There is a related problem with > serialization. > > > > > Whether > > > > > > >> > > something > > > > > > >> > > > >> > > is a prefix or not depends not on the Java key > (K), > > > but > > > > > on > > > > > > >> the > > > > > > >> > > binary > > > > > > >> > > > >> > > format that is produced when you use a serde on > the > > > key. > > > > > > >> Whether > > > > > > >> > > > >> > > we say that the prefix must also be a K or > whether it > > > > > gets > > > > > > >> its own > > > > > > >> > > > >> type, > > > > > > >> > > > >> > > KP, there are problems. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > In the latter case, we must additionally require > a > > > second > > > > > > >> set of > > > > > > >> > > > >> serdes > > > > > > >> > > > >> > > for the prefixes, but there's no obvious way to > > > > > incorporate > > > > > > >> this > > > > > > >> > > in > > > > > > >> > > > >> the > > > > > > >> > > > >> > > API, especially not in the DSL. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > In either case, for the API to actually work, we > > > need to > > > > > know > > > > > > >> > > ahead > > > > > > >> > > > >> > > of time that the Serde will produce a binary key > that > > > > > starts > > > > > > >> with > > > > > > >> > > the > > > > > > >> > > > >> > > part that we wish to use as a prefix. For > example, > > > what > > > > > we > > > > > > >> were > > > > > > >> > > doing > > > > > > >> > > > >> > > briefly in KIP-213 (where we had complex keys, > > > similar to > > > > > > >> > > Windowed<K>) > > > > > > >> > > > >> > > was to define "dummy" values that indicate that a > > > > > > >> Windowed<K> is > > > > > > >> > > > >> actually > > > > > > >> > > > >> > > just a prefix key, not a real key. Maybe the > window > > > start > > > > > > >> time > > > > > > >> > > would > > > > > > >> > > > >> be > > > > > > >> > > > >> > > null or the key part would be null. But we also > had > > > to > > > > > > >> define a > > > > > > >> > > serde > > > > > > >> > > > >> > > that would very specifically anticipate which > > > component > > > > > of > > > > > > >> the > > > > > > >> > > complex > > > > > > >> > > > >> > > key would need to be used in a prefix key. > Having to > > > > > bring > > > > > > >> all > > > > > > >> > > these > > > > > > >> > > > >> > > parts together in a reliable, easy-to-debug, > fashion > > > > > gives > > > > > > >> me some > > > > > > >> > > > >> doubt > > > > > > >> > > > >> > > that people would actually be able to use this > > > feature in > > > > > > >> > > complicated > > > > > > >> > > > >> > > programs without driving themselves crazy. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > J3) Thanks so much for including benchmarks and > > > tests! > > > > > > >> > > Unfortunately, > > > > > > >> > > > >> > > these don't include everything you need to really > > > plug > > > > > into > > > > > > >> the > > > > > > >> > > > >> Streams > > > > > > >> > > > >> > > API. I think when you push it a little farther, > > > you'll > > > > > > >> realize > > > > > > >> > > what > > > > > > >> > > > >> Adam > > > > > > >> > > > >> > > was talking about wrt the interface difficulties. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > In your benchmark and tests, you directly > construct > > > the > > > > > > >> store and > > > > > > >> > > then > > > > > > >> > > > >> > > use it, but in a real Streams application, you > can > > > only > > > > > > >> provide > > > > > > >> > > your > > > > > > >> > > > >> > > implementation in a StoreSupplier, for example > via > > > the > > > > > > >> > > Materialized > > > > > > >> > > > >> > > parameter. Then, to use the store from inside a > > > > > Processor, > > > > > > >> you'd > > > > > > >> > > have > > > > > > >> > > > >> > > to get it by name from the ProcessorContext, and > then > > > > > cast > > > > > > >> it to > > > > > > >> > > one > > > > > > >> > > > >> of > > > > > > >> > > > >> > > the pre-defined store types, KeyValueStore, > > > > > WindowedStore, or > > > > > > >> > > > >> > > SessionStore. It won't work to "mix in" your > > > interface > > > > > > >> because the > > > > > > >> > > > >> > > processor gets a store that's wrapped in layers > that > > > > > handle > > > > > > >> > > > >> serialization, > > > > > > >> > > > >> > > change-logging, recording metrics, and caching. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > To use the store through IQ, you have to provide > a > > > > > > >> > > QueriableStoreType > > > > > > >> > > > >> > > to KafkaStreams#store, and you get back a > similarly > > > > > wrapped > > > > > > >> store. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > I think our only choices to add an interface like > > > yours > > > > > is > > > > > > >> either > > > > > > >> > > to > > > > > > >> > > > >> add > > > > > > >> > > > >> > > it to one of the existing store types, like > > > > > KeyValueStore or > > > > > > >> > > > >> > > WindowedStore, or to define a completely new > store > > > > > hierarchy, > > > > > > >> > > meaning > > > > > > >> > > > >> > > you have to duplicate all the "wrapper" layers in > > > > > Streams. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > I think if you write an "end-to-end" test, where > you > > > > > write a > > > > > > >> > > Streams > > > > > > >> > > > >> app, > > > > > > >> > > > >> > > provide your store, and then use it in a > Processor > > > and > > > > > > >> through IQ, > > > > > > >> > > > >> > > you'll see what I'm talking about. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > IIRC, those three points were the ones that > > > ultimately > > > > > led > > > > > > >> us to > > > > > > >> > > > >> abandon > > > > > > >> > > > >> > > the whole idea last time and just register the > stores > > > > > with > > > > > > >> key > > > > > > >> > > type > > > > > > >> > > > >> Bytes. > > > > > > >> > > > >> > > I think some creative solutions may yet be > possible, > > > but > > > > > > >> it'll > > > > > > >> > > take > > > > > > >> > > > >> some > > > > > > >> > > > >> > > more design work to get there. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > Can I ask what your motivation is, exactly, for > > > proposing > > > > > > >> this > > > > > > >> > > > >> feature? > > > > > > >> > > > >> > > The motivation just says "some users may want to > do > > > it", > > > > > > >> which has > > > > > > >> > > > >> > > the advantage that it's impossible to disagree > with, > > > but > > > > > > >> doesn't > > > > > > >> > > > >> provide > > > > > > >> > > > >> > > a lot of concrete detail ;) > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > Specifically, what I'm wondering is whether you > > > wanted > > > > > to use > > > > > > >> > > this as > > > > > > >> > > > >> > > part of a KayValue store, which might be a > > > challenge, or > > > > > > >> whether > > > > > > >> > > you > > > > > > >> > > > >> > > wanted to use it for more efficient scans in a > > > > > > >> WindowedStore, like > > > > > > >> > > > >> > > Guozhang. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > Thanks again for the KIP! I hope my response > isn't > > > too > > > > > > >> > > discouraging; > > > > > > >> > > > >> > > I just wanted to convey the challenges we faced > last > > > > > time, > > > > > > >> since > > > > > > >> > > they > > > > > > >> > > > >> > > are all not obvious up front. > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > Best regards, > > > > > > >> > > > >> > > -John > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > On Thu, May 14, 2020, at 16:17, Sophie > Blee-Goldman > > > > > wrote: > > > > > > >> > > > >> > > > Whoops, I guess I didn't finish reading the KIP > > > all the > > > > > > >> way to > > > > > > >> > > the > > > > > > >> > > > >> end > > > > > > >> > > > >> > > > earlier. Thanks > > > > > > >> > > > >> > > > for including the link to the RocksDB PR in the > > > KIP! > > > > > > >> > > > >> > > > > > > > > > >> > > > >> > > > I have one additional question about the > proposal: > > > do > > > > > you > > > > > > >> plan > > > > > > >> > > to > > > > > > >> > > > >> also > > > > > > >> > > > >> > > add > > > > > > >> > > > >> > > > this > > > > > > >> > > > >> > > > prefix seek API to the dual column family > > > iterators? > > > > > These > > > > > > >> are > > > > > > >> > > used > > > > > > >> > > > >> by > > > > > > >> > > > >> > > > RocksDBTimestampedStore (which extends > > > RocksDBStore), > > > > > for > > > > > > >> > > example > > > > > > >> > > > >> the > > > > > > >> > > > >> > > > *RocksDBDualCFRangeIterator* > > > > > > >> > > > >> > > > > > > > > > >> > > > >> > > > Thanks for the KIP! > > > > > > >> > > > >> > > > > > > > > > >> > > > >> > > > On Thu, May 14, 2020 at 10:50 AM Sagar < > > > > > > >> > > sagarmeansoc...@gmail.com> > > > > > > >> > > > >> > > wrote: > > > > > > >> > > > >> > > > > > > > > > >> > > > >> > > > > Hey @Adam, > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > Thanks for sharing your experience with using > > > prefix > > > > > > >> seek. I > > > > > > >> > > did > > > > > > >> > > > >> look > > > > > > >> > > > >> > > at > > > > > > >> > > > >> > > > > your code for RocksDBPrefixIterator, infact I > > > have > > > > > > >> repurposed > > > > > > >> > > that > > > > > > >> > > > >> > > class > > > > > > >> > > > >> > > > > itself since it wasn't being used else where. > > > > > Regarding > > > > > > >> how I > > > > > > >> > > > >> plan to > > > > > > >> > > > >> > > > > expose them through-out the state stores, > what I > > > have > > > > > > >> tried > > > > > > >> > > to do > > > > > > >> > > > >> is > > > > > > >> > > > >> > > add it > > > > > > >> > > > >> > > > > as a separate interface. So, basically, it is > > > not at > > > > > the > > > > > > >> same > > > > > > >> > > > >> level as > > > > > > >> > > > >> > > the > > > > > > >> > > > >> > > > > *range function so to speak. The reason I did > > > that is > > > > > > >> > > currently I > > > > > > >> > > > >> feel > > > > > > >> > > > >> > > not > > > > > > >> > > > >> > > > > all state stores are a natural fit for prefix > > > seek. > > > > > As I > > > > > > >> > > > >> mentioned in > > > > > > >> > > > >> > > the > > > > > > >> > > > >> > > > > KIP as well, the current equivalent to it > could > > > be > > > > > > >> > > > >> > > BulkLoadingStore(not in > > > > > > >> > > > >> > > > > terms of functionality but in terms of how > it is > > > > > also not > > > > > > >> > > > >> implemented > > > > > > >> > > > >> > > by > > > > > > >> > > > >> > > > > all of them). So, that ways I am not needing > to > > > stub > > > > > them > > > > > > >> > > across > > > > > > >> > > > >> all > > > > > > >> > > > >> > > the > > > > > > >> > > > >> > > > > state-stores and we can implement it only > where > > > > > needed. > > > > > > >> For > > > > > > >> > > > >> example, > > > > > > >> > > > >> > > in the > > > > > > >> > > > >> > > > > PR that I have put for reference in the KIP, > you > > > can > > > > > see > > > > > > >> that > > > > > > >> > > I > > > > > > >> > > > >> have it > > > > > > >> > > > >> > > > > implemented only for RocksDB. > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > @Guozhang, > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > Thanks for the feedback. Those are very > > > interesting > > > > > > >> questions > > > > > > >> > > and > > > > > > >> > > > >> I > > > > > > >> > > > >> > > will > > > > > > >> > > > >> > > > > try my best to answer based upon whatever > limited > > > > > > >> > > understanding I > > > > > > >> > > > >> have > > > > > > >> > > > >> > > > > developed so far :) > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > 1) Regarding the usage of > > > > > useFixedLengthPrefixExtractor, > > > > > > >> > > > >> honestly, I > > > > > > >> > > > >> > > hadn't > > > > > > >> > > > >> > > > > looked at that config. I did look it up > after you > > > > > > >> pointed it > > > > > > >> > > out > > > > > > >> > > > >> and > > > > > > >> > > > >> > > seems > > > > > > >> > > > >> > > > > it's more for hash-based memtables? I may be > > > wrong > > > > > > >> though. But > > > > > > >> > > > >> what I > > > > > > >> > > > >> > > would > > > > > > >> > > > >> > > > > say is that, the changes I had made were not > > > exactly > > > > > > >> from a > > > > > > >> > > > >> correctness > > > > > > >> > > > >> > > > > stand point but more from trying to showcase > how > > > we > > > > > can > > > > > > >> > > implement > > > > > > >> > > > >> these > > > > > > >> > > > >> > > > > changes. The idea was that once we see the > merit > > > in > > > > > this > > > > > > >> > > approach > > > > > > >> > > > >> then > > > > > > >> > > > >> > > we > > > > > > >> > > > >> > > > > can add some of the tunings( and I would need > > > your > > > > > team's > > > > > > >> > > > >> assistance > > > > > > >> > > > >> > > there > > > > > > >> > > > >> > > > > :D). > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > 2) Regarding the similarity of > > > > > `RocksDBPrefixIterator` > > > > > > >> and > > > > > > >> > > > >> > > > > `RocksDBRangeIterator`, yes the > implementations > > > look > > > > > > >> more or > > > > > > >> > > less > > > > > > >> > > > >> > > similar. > > > > > > >> > > > >> > > > > So, in terms of performance, they might be > > > similar. > > > > > But > > > > > > >> > > > >> semantically, > > > > > > >> > > > >> > > they > > > > > > >> > > > >> > > > > can solve 2 different use-cases. The range > seek > > > is > > > > > useful > > > > > > >> > > when we > > > > > > >> > > > >> know > > > > > > >> > > > >> > > both > > > > > > >> > > > >> > > > > from and to. But if we consider use-cases > where > > > we > > > > > want > > > > > > >> to > > > > > > >> > > find > > > > > > >> > > > >> keys > > > > > > >> > > > >> > > with a > > > > > > >> > > > >> > > > > certain prefix, but we don't know if what > it's > > > start > > > > > and > > > > > > >> end > > > > > > >> > > is, > > > > > > >> > > > >> then > > > > > > >> > > > >> > > > > prefix seek would come in more handy. The > point > > > that > > > > > I am > > > > > > >> > > trying > > > > > > >> > > > >> to > > > > > > >> > > > >> > > make is > > > > > > >> > > > >> > > > > that it can extend the scope of state stores > from > > > > > just > > > > > > >> point > > > > > > >> > > > >> lookups to > > > > > > >> > > > >> > > > > somewhat being able to speculative queries > where > > > by > > > > > > >> users can > > > > > > >> > > > >> search > > > > > > >> > > > >> > > if a > > > > > > >> > > > >> > > > > certain pattern exists. I can vouch for this > > > > > personally > > > > > > >> > > because I > > > > > > >> > > > >> > > wanted to > > > > > > >> > > > >> > > > > use state stores for one such use case and > since > > > this > > > > > > >> option > > > > > > >> > > > >> wasn't > > > > > > >> > > > >> > > there, > > > > > > >> > > > >> > > > > I had to do some other things. An equivalent > to > > > this > > > > > > >> could be > > > > > > >> > > SCAN > > > > > > >> > > > >> > > operator > > > > > > >> > > > >> > > > > in Redis. (Not trying to compare the Redis > and > > > state > > > > > > >> stores > > > > > > >> > > but > > > > > > >> > > > >> trying > > > > > > >> > > > >> > > to > > > > > > >> > > > >> > > > > give some context). > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > Regarding the point on bloom filter, I think > > > there > > > > > are > > > > > > >> certain > > > > > > >> > > > >> > > > > optimisations that are being talked about in > > > case of > > > > > > >> prefix > > > > > > >> > > seek > > > > > > >> > > > >> here: > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > > > > > >> > > > > > > > > >> > > > > > > > > > https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter#prefix-vs-whole-key > > > > > > >> > > > >> > > > > Again > > > > > > >> > > > >> > > > > this isn't something that I have explored > fully. > > > > > Also, > > > > > > >> on the > > > > > > >> > > > >> prefix > > > > > > >> > > > >> > > seek > > > > > > >> > > > >> > > > > page on RocksDB they mention that there's a > > > prefix > > > > > > >> iterating > > > > > > >> > > > >> technique > > > > > > >> > > > >> > > > > called Prefix Bloom Filter. > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > 3) Regarding the question on length of bytes > for > > > > > seek v/s > > > > > > >> > > prefix > > > > > > >> > > > >> seek, > > > > > > >> > > > >> > > I am > > > > > > >> > > > >> > > > > not entirely sure about that scenario. What I > > > have > > > > > > >> understood > > > > > > >> > > is > > > > > > >> > > > >> that > > > > > > >> > > > >> > > > > at-least for Rocks DB, it is more performant > for > > > > > short > > > > > > >> > > iterator > > > > > > >> > > > >> queries > > > > > > >> > > > >> > > > > that longer ones. > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > 4) Regarding the last question on placing it > > > within > > > > > > >> Segment, > > > > > > >> > > the > > > > > > >> > > > >> > > reason I > > > > > > >> > > > >> > > > > didn't do that way, is that I thought we > > > shouldn't > > > > > tie > > > > > > >> this > > > > > > >> > > > >> feature > > > > > > >> > > > >> > > only to > > > > > > >> > > > >> > > > > RocksDB. I agree that I got this idea while > > > > > > >> looking/reading > > > > > > >> > > about > > > > > > >> > > > >> > > RocksDB > > > > > > >> > > > >> > > > > but if we keep it outside the purview of > RocksDB > > > and > > > > > > >> keep it > > > > > > >> > > as a > > > > > > >> > > > >> > > pluggable > > > > > > >> > > > >> > > > > entity, then a) it remains generic by not > being > > > tied > > > > > to > > > > > > >> any > > > > > > >> > > > >> specific > > > > > > >> > > > >> > > store > > > > > > >> > > > >> > > > > and b) no change is needed at all for any of > the > > > > > other > > > > > > >> stores > > > > > > >> > > > >> which > > > > > > >> > > > >> > > haven't > > > > > > >> > > > >> > > > > implemented it. > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > I am not sure of any of the above points make > > > sense > > > > > but > > > > > > >> as I > > > > > > >> > > said, > > > > > > >> > > > >> > > this is > > > > > > >> > > > >> > > > > based out of my limited understanding of the > > > > > codebase. > > > > > > >> So, > > > > > > >> > > pardon > > > > > > >> > > > >> any > > > > > > >> > > > >> > > > > incorrect/illogical statements plz! > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > @Sophie, > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > Thanks for bringing that point up! I have > > > mentioned > > > > > about > > > > > > >> > > that PR > > > > > > >> > > > >> in > > > > > > >> > > > >> > > the > > > > > > >> > > > >> > > > > KIP under a section called Other > considerations. > > > > > > >> Nonetheless, > > > > > > >> > > > >> thanks > > > > > > >> > > > >> > > for > > > > > > >> > > > >> > > > > pointing it out! > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > Thanks! > > > > > > >> > > > >> > > > > Sagar. > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > On Thu, May 14, 2020 at 5:17 AM Sophie > > > Blee-Goldman < > > > > > > >> > > > >> > > sop...@confluent.io> > > > > > > >> > > > >> > > > > wrote: > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > > Not to derail this KIP discussion, but to > > > leave a > > > > > few > > > > > > >> notes > > > > > > >> > > on > > > > > > >> > > > >> some > > > > > > >> > > > >> > > of > > > > > > >> > > > >> > > > > the > > > > > > >> > > > >> > > > > > RocksDB points that have come up: > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > Someone actually merged some long overdue > > > > > performance > > > > > > >> > > > >> improvements to > > > > > > >> > > > >> > > > > > the RocksJava implementation (the PR was > opened > > > > > back in > > > > > > >> > > 2017! > > > > > > >> > > > >> yikes). > > > > > > >> > > > >> > > > > > I haven't looked into the prefix seek API > > > closely > > > > > > >> enough to > > > > > > >> > > > >> know how > > > > > > >> > > > >> > > > > > relevant > > > > > > >> > > > >> > > > > > this particular change is, and they are > still > > > > > improving > > > > > > >> > > things, > > > > > > >> > > > >> but > > > > > > >> > > > >> > > it > > > > > > >> > > > >> > > > > > gives me some > > > > > > >> > > > >> > > > > > faith. > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > There are some pretty promising results > > > reported on > > > > > > >> the PR: > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > > >> > > > https://github.com/facebook/rocksdb/pull/2283#issuecomment-561563037 > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > Regarding the custom comparator, they also > > > recently > > > > > > >> merged > > > > > > >> > > this > > > > > > >> > > > >> > > > > performance > > > > > > >> > > > >> > > > > > < > https://github.com/facebook/rocksdb/pull/6252 > > > > > > > > > > >> > > > >> > > > > > improvement < > > > > > > >> https://github.com/facebook/rocksdb/pull/6252 > > > > > > >> > > >. > > > > > > >> > > > >> The > > > > > > >> > > > >> > > tl;dr > > > > > > >> > > > >> > > > > is > > > > > > >> > > > >> > > > > > they reduced the slowdown of a custom > > > comparator in > > > > > > >> Java > > > > > > >> > > > >> > > > > > (relative to the native C++) from ~7x to > ~5.2x > > > at > > > > > best. > > > > > > >> > > Which is > > > > > > >> > > > >> > > still > > > > > > >> > > > >> > > > > not > > > > > > >> > > > >> > > > > > great, but it > > > > > > >> > > > >> > > > > > would be interesting to run our own > benchmarks > > > and > > > > > see > > > > > > >> how > > > > > > >> > > this > > > > > > >> > > > >> > > stacks > > > > > > >> > > > >> > > > > up. > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > Of course, these are all new changes and as > > > such > > > > > will > > > > > > >> > > require > > > > > > >> > > > >> us to > > > > > > >> > > > >> > > > > upgrade > > > > > > >> > > > >> > > > > > rocks to 6.x which means they have to wait > for > > > us > > > > > to > > > > > > >> > > release a > > > > > > >> > > > >> 3.0. > > > > > > >> > > > >> > > But > > > > > > >> > > > >> > > > > > there's > > > > > > >> > > > >> > > > > > some talk about 3.0 coming in the next few > > > > > releases so > > > > > > >> > > consider > > > > > > >> > > > >> it > > > > > > >> > > > >> > > food > > > > > > >> > > > >> > > > > for > > > > > > >> > > > >> > > > > > not-so-future thought > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > On Tue, May 12, 2020 at 5:02 PM Adam > Bellemare > > > < > > > > > > >> > > > >> > > adam.bellem...@gmail.com > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > wrote: > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > > Hi Guozhang > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > For clarity, the issues I was running > into > > > was > > > > > not > > > > > > >> about > > > > > > >> > > the > > > > > > >> > > > >> actual > > > > > > >> > > > >> > > > > > > *prefixSeek* function itself, but about > > > exposing > > > > > it > > > > > > >> to the > > > > > > >> > > > >> same > > > > > > >> > > > >> > > level > > > > > > >> > > > >> > > > > of > > > > > > >> > > > >> > > > > > > access as the *range* function throughout > > > Kafka > > > > > > >> Streams. > > > > > > >> > > It > > > > > > >> > > > >> > > required a > > > > > > >> > > > >> > > > > > lot > > > > > > >> > > > >> > > > > > > of changes, and also required that most > state > > > > > stores > > > > > > >> stub > > > > > > >> > > it > > > > > > >> > > > >> out > > > > > > >> > > > >> > > since > > > > > > >> > > > >> > > > > it > > > > > > >> > > > >> > > > > > > wasn't clear how they would implement > it. It > > > was > > > > > > >> > > basically an > > > > > > >> > > > >> > > > > > overreaching > > > > > > >> > > > >> > > > > > > API change that was easily solved (for > the > > > > > specific > > > > > > >> > > > >> prefix-scan in > > > > > > >> > > > >> > > FKJ) > > > > > > >> > > > >> > > > > > by > > > > > > >> > > > >> > > > > > > simply using *range*. So to be clear, the > > > > > blockers > > > > > > >> were > > > > > > >> > > > >> > > predominantly > > > > > > >> > > > >> > > > > > > around correctly handling the API > changes, > > > > > nothing > > > > > > >> to do > > > > > > >> > > with > > > > > > >> > > > >> the > > > > > > >> > > > >> > > > > > > mechanisms of the RocksDB prefix > scanning. > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > As for KAFKA-5285 I'll look into it more > to > > > see > > > > > if I > > > > > > >> can > > > > > > >> > > get a > > > > > > >> > > > >> > > better > > > > > > >> > > > >> > > > > > > handle on the problem! > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > Hope this helps clear it up. > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > Adam > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > On Tue, May 12, 2020 at 7:16 PM Guozhang > > > Wang < > > > > > > >> > > > >> wangg...@gmail.com> > > > > > > >> > > > >> > > > > > wrote: > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > > Hello Adam, > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > I'm wondering if you can provide a bit > more > > > > > > >> context on > > > > > > >> > > the > > > > > > >> > > > >> > > blockers > > > > > > >> > > > >> > > > > of > > > > > > >> > > > >> > > > > > > > using prefixSeek of RocksDB (I saw you > > > have a > > > > > > >> > > > >> > > RocksDBPrefixIterator > > > > > > >> > > > >> > > > > > class > > > > > > >> > > > >> > > > > > > > but not used anywhere yet)? I'm > currently > > > > > looking > > > > > > >> at > > > > > > >> > > ways to > > > > > > >> > > > >> > > allow > > > > > > >> > > > >> > > > > some > > > > > > >> > > > >> > > > > > > > secondary indices with rocksDB > following > > > some > > > > > > >> existing > > > > > > >> > > > >> approaches > > > > > > >> > > > >> > > > > > > > from CockroachDB etc so I'm very > curious to > > > > > learn > > > > > > >> your > > > > > > >> > > > >> > > experience. > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > 1) Before considering any secondary > > > indices, a > > > > > > >> quick > > > > > > >> > > > >> thought is > > > > > > >> > > > >> > > that > > > > > > >> > > > >> > > > > > for > > > > > > >> > > > >> > > > > > > > (key, timeFrom, timeTo) queries, we can > > > easily > > > > > > >> replace > > > > > > >> > > the > > > > > > >> > > > >> > > current > > > > > > >> > > > >> > > > > > > > `range()` impl with a `prefixRange()` > impl > > > via > > > > > a > > > > > > >> prefix > > > > > > >> > > > >> iterator; > > > > > > >> > > > >> > > > > > though > > > > > > >> > > > >> > > > > > > > for (keyFrom, keyTo, timeFrom, timeTo) > it > > > is > > > > > much > > > > > > >> more > > > > > > >> > > > >> > > complicated > > > > > > >> > > > >> > > > > > indeed > > > > > > >> > > > >> > > > > > > > and hence existing `range()` impl may > > > still be > > > > > > >> used. > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > 2) Another related issue I've been > > > pondering > > > > > for a > > > > > > >> > > while is > > > > > > >> > > > >> > > > > > > > around KAFKA-5285: with the default > > > > > lexicograpic > > > > > > >> byte > > > > > > >> > > > >> comparator, > > > > > > >> > > > >> > > > > since > > > > > > >> > > > >> > > > > > > the > > > > > > >> > > > >> > > > > > > > key length varies, the combo (key, > window) > > > > > would > > > > > > >> have > > > > > > >> > > > >> > > interleaving > > > > > > >> > > > >> > > > > byte > > > > > > >> > > > >> > > > > > > > layouts like: > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > AAA0001 (key AAA, timestamp > 0001) > > > > > > >> > > > >> > > > > > > > AAA00011 (key AAA0, timestamp > 0011) > > > > > > >> > > > >> > > > > > > > AAA0002 (key AAA, timestamp > 0002) > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > which is challenging for prefix seeks > to > > > work > > > > > > >> > > efficiently. > > > > > > >> > > > >> > > Although > > > > > > >> > > > >> > > > > we > > > > > > >> > > > >> > > > > > > can > > > > > > >> > > > >> > > > > > > > overwrite the byte-comparator in JNI > it is > > > very > > > > > > >> > > expensive > > > > > > >> > > > >> and the > > > > > > >> > > > >> > > > > cost > > > > > > >> > > > >> > > > > > of > > > > > > >> > > > >> > > > > > > > JNI overwhelms its benefits. If you've > got > > > some > > > > > > >> ideas > > > > > > >> > > > >> around it > > > > > > >> > > > >> > > > > please > > > > > > >> > > > >> > > > > > > lmk > > > > > > >> > > > >> > > > > > > > as well. > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > Guozhang > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > On Tue, May 12, 2020 at 6:26 AM Adam > > > Bellemare > > > > > < > > > > > > >> > > > >> > > > > > adam.bellem...@gmail.com > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > wrote: > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > > Hi Sagar > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > I implemented a very similar > interface > > > for > > > > > > >> KIP-213, > > > > > > >> > > the > > > > > > >> > > > >> > > foreign-key > > > > > > >> > > > >> > > > > > > > joiner. > > > > > > >> > > > >> > > > > > > > > We pulled it out of the final > > > implementation > > > > > and > > > > > > >> > > instead > > > > > > >> > > > >> used > > > > > > >> > > > >> > > > > RocksDB > > > > > > >> > > > >> > > > > > > > range > > > > > > >> > > > >> > > > > > > > > instead. You can see the particular > code > > > > > where > > > > > > >> we use > > > > > > >> > > > >> > > > > > > RocksDB.range(...) > > > > > > >> > > > >> > > > > > > > to > > > > > > >> > > > >> > > > > > > > > get the same iterator result. > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > > > > > >> > > > > > > > > >> > > > > > > > > > https://github.com/apache/kafka/blob/trunk/streams/src/main/java/org/apache/kafka/streams/kstream/internals/foreignkeyjoin/ForeignJoinSubscriptionProcessorSupplier.java#L95 > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > We pulled it out because there were > > > numerous > > > > > > >> awkward > > > > > > >> > > > >> > > acrobatics to > > > > > > >> > > > >> > > > > > > > > integrate *prefixSeek()* function > into > > > the > > > > > Kafka > > > > > > >> > > Streams > > > > > > >> > > > >> code. > > > > > > >> > > > >> > > > > > > > Basically, I > > > > > > >> > > > >> > > > > > > > > wanted to be able to access > > > *prefixSeek()* > > > > > the > > > > > > >> same > > > > > > >> > > way I > > > > > > >> > > > >> can > > > > > > >> > > > >> > > > > access > > > > > > >> > > > >> > > > > > > > > *range()* for any state store, and in > > > > > particular > > > > > > >> use > > > > > > >> > > it > > > > > > >> > > > >> for > > > > > > >> > > > >> > > storing > > > > > > >> > > > >> > > > > > > data > > > > > > >> > > > >> > > > > > > > > with a particular foreign key (as > per the > > > > > > >> previous > > > > > > >> > > URL). > > > > > > >> > > > >> > > However, I > > > > > > >> > > > >> > > > > > > found > > > > > > >> > > > >> > > > > > > > > out that it required way too many > > > changes to > > > > > > >> expose > > > > > > >> > > the > > > > > > >> > > > >> > > > > > *prefixSeek()* > > > > > > >> > > > >> > > > > > > > > functionality while still being able > to > > > > > leverage > > > > > > >> all > > > > > > >> > > the > > > > > > >> > > > >> nice > > > > > > >> > > > >> > > Kafka > > > > > > >> > > > >> > > > > > > > Streams > > > > > > >> > > > >> > > > > > > > > state management + supplier > > > functionality, > > > > > so we > > > > > > >> made > > > > > > >> > > a > > > > > > >> > > > >> > > decision > > > > > > >> > > > >> > > > > just > > > > > > >> > > > >> > > > > > > to > > > > > > >> > > > >> > > > > > > > > stick with *range()* and pull > everything > > > else > > > > > > >> out. > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > I guess my question here is, how do > you > > > > > > >> anticipate > > > > > > >> > > using > > > > > > >> > > > >> > > > > > *prefixSeek()* > > > > > > >> > > > >> > > > > > > > > within the framework of Kafka > Streams, > > > or the > > > > > > >> > > Processor > > > > > > >> > > > >> API? > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > Adam > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > On Tue, May 12, 2020 at 2:52 AM > Sagar < > > > > > > >> > > > >> > > sagarmeansoc...@gmail.com> > > > > > > >> > > > >> > > > > > > wrote: > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > Hi All, > > > > > > >> > > > >> > > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > I would like to start a discussion > on > > > the > > > > > KIP > > > > > > >> that I > > > > > > >> > > > >> created > > > > > > >> > > > >> > > > > below > > > > > > >> > > > >> > > > > > to > > > > > > >> > > > >> > > > > > > > add > > > > > > >> > > > >> > > > > > > > > > prefix scan support in State > Stores: > > > > > > >> > > > >> > > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > > > > > >> > > > > > > > > >> > > > > > > > > > https://cwiki.apache.org/confluence/display/KAFKA/KIP-614%3A+Add+Prefix+Scan+support+for+State+Stores > > > > > > >> > > > >> > > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > Thanks! > > > > > > >> > > > >> > > > > > > > > > Sagar. > > > > > > >> > > > >> > > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > -- > > > > > > >> > > > >> > > > > > > > -- Guozhang > > > > > > >> > > > >> > > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > > >> > > > >> > > > > > > > > > > > >> > > > >> > > > > > > > > > > >> > > > >> > > > > > > > > > >> > > > >> > > > > > > > > >> > > > >> > > > > > > > >> > > > >> > > > > > > >> > > > > > > > > > > >> > > > > > > > > > >> > > > > > > > > >> > > > > > > > >> > > > > > > > > > > > > > > > > > > > > > > > > > > > >