kafka-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From radai <radai.rosenbl...@gmail.com>
Subject Re: Different key with the same digest in log compaction
Date Fri, 06 Jan 2017 19:48:53 GMT
i just noticed my link didnt parse correctly. the formula for probability
of collision is explained by googling "birthday paradox".
if anything, we could further optimize this code to use a trivial hash map
for cases where sizeOf(hash) > sizeOf(key)

On Fri, Jan 6, 2017 at 10:00 AM, Colin McCabe <cmccabe@apache.org> wrote:

> That's a fair point.  The calls to Arrays.equals are comparing just the
> hashes, not the keys.
>
> Colin
>
> On Tue, Jan 3, 2017, at 17:15, radai wrote:
> > looking at the code (SkimpyOffsetMap.get/put) they both start with
> > hashInto(key, hash1) and then ignore key from that point on - so we're
> > not
> > using the key unless im missing something?
> >
> > as for the probability of collision - it depends on the hash algo and the
> > number of keys. if you configure it to use something like sha-512 the
> > probability is truly negligible.
> >
> > for example, the probability of collision on a topic with 4 billion
> > entries
> > using MD5 is ~ 10^-20 (math -
> > http://www.wolframalpha.com/input/?i=n+%3D+2
> > ^32,+d+%3D+2^128,+1+-+%28%28d-1%29%2Fd%29+^+%28n%28n-1%29%2F2%29)
> >
> > On Tue, Jan 3, 2017 at 4:37 PM, Colin McCabe <cmccabe@apache.org> wrote:
> >
> > > Can you be a little bit clearer on why you think that different keys
> > > with the same digest value will be treated as the same key?
> > > SkimpyOffsetMap#get and SkimpyOffsetMap#put compare the key, not just
> > > the hash digest of the key.
> > >
> > > best,
> > > Colin
> > >
> > >
> > > On Wed, Dec 21, 2016, at 23:27, Renkai Ge wrote:
> > > > Hi,all:
> > > >  I am just learning the kafka codebase, as what I saw in
> > > > https://github.com/apache/kafka/blob/6ed3e6b1cb8a73b1f5f78926ccb247
> > > a8953a554c/core/src/main/scala/kafka/log/OffsetMap.scala#L43-L43
> > > >
> > > > if different log keys have the same digest value, they will be
> treated as
> > > > the same key in log compaction.Though the risk of such things
> happens is
> > > > very small, I still want it to be avoided.If what I thought is wrong
> > > > please
> > > > let me know, and I hope to know the thoughts of who created or
> > > > is maintaining the code.
> > >
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message