5 ms·

Are you suggesting that spotify is somewherre using a hash-table without a collision resolution method (like a linked list). Is that something that is done in

Are you suggesting that spotify is somewherre using a hash-table without a collision resolution method (like a linked list). Is that something that is done in some industries? Hash collisions to me has always been a performance problem not a correctness one.

nkozyra 8y ago
I could be wrong but the suggestion seems to be that plays are hashed before storage and the tracks exploit the hash algorithm in use. That, to me, seems far less likely than simple account compromise. Hash collisions have always been a security threat vector.
bostik 8y ago
Goodness me, no. They could be fetching all values for a given key (for performance reasons, since the seek for a read is surprisingly expensive). Depending on how they then use that data, these short and plentiful tracks can end up being included instead of dropped.
- Illniyar 8y ago
  Sorry if I'm being obtuse but why would they be using a hash as a key instead of a uuid? I've never heard of any distributed system (or any system) that use hash as a key. Or are you saying there is somekind of auxiliary hash table in use for performance somewhere?
  - kingosticks 8y ago
    Is it not fair to say that git is a distributed system using a hash as a key?
    - Illniyar 8y ago
      I suppose it is. Though it's not the sort of systems I meant in my reply. Never even crossed my mind. P2P networks (like torrents) could probably also count as ones.
  - bostik 8y ago
    Git was already mentioned as an example, but there is a more generic answer to your question. Look up https://en.wikipedia.org/wiki/Content-addressable_storage https://en.wikipedia.org/wiki/Content-addressable_storage ; the design is basically a DHT. Key collisions are standard feature in any hash table. In any hash table, collisions are unavoidable. In a distributed KV store, the collision resolution might be done at a higher level, so any lookup reads all the values for a given key. The reason is simple: opportunistic caching. Sometimes you get lucky and are asked for two or more items that hash to the same key within cache expiration window. If you can avoid a read just 0.1% of the time, that's an improvement on tail latency AND it just left capacity available for other clients to do their reads. We are all aware Spotify stores a lot of media. I know nothing about their internal architecture, but they might use hash of the track metadata as its content key. If assumptions (or "happy optimisations") about their size distribution don't hold, some extra tracks could end up getting through.

nkozyra 8y ago

I could be wrong but the suggestion seems to be that plays are hashed before storage and the tracks exploit the hash algorithm in use. That, to me, seems far less likely than simple account compromise. Hash collisions have always been a security threat vector.

bostik 8y ago

Goodness me, no. They could be fetching all values for a given key (for performance reasons, since the seek for a read is surprisingly expensive). Depending on how they then use that data, these short and plentiful tracks can end up being included instead of dropped.

Illniyar 8y ago
Sorry if I'm being obtuse but why would they be using a hash as a key instead of a uuid? I've never heard of any distributed system (or any system) that use hash as a key. Or are you saying there is somekind of auxiliary hash table in use for performance somewhere?
- kingosticks 8y ago
  Is it not fair to say that git is a distributed system using a hash as a key?
  - Illniyar 8y ago
    I suppose it is. Though it's not the sort of systems I meant in my reply. Never even crossed my mind. P2P networks (like torrents) could probably also count as ones.
- bostik 8y ago
  Git was already mentioned as an example, but there is a more generic answer to your question. Look up https://en.wikipedia.org/wiki/Content-addressable_storage https://en.wikipedia.org/wiki/Content-addressable_storage ; the design is basically a DHT. Key collisions are standard feature in any hash table. In any hash table, collisions are unavoidable. In a distributed KV store, the collision resolution might be done at a higher level, so any lookup reads all the values for a given key. The reason is simple: opportunistic caching. Sometimes you get lucky and are asked for two or more items that hash to the same key within cache expiration window. If you can avoid a read just 0.1% of the time, that's an improvement on tail latency AND it just left capacity available for other clients to do their reads. We are all aware Spotify stores a lot of media. I know nothing about their internal architecture, but they might use hash of the track metadata as its content key. If assumptions (or "happy optimisations") about their size distribution don't hold, some extra tracks could end up getting through.