14 ms·

It was the primary key index in a database using MVCC. It stored various flags and a version (transaction timestamp) and data pointer. It also stored something

by eloff 6y ago

It was the primary key index in a database using MVCC. It stored various flags and a version (transaction timestamp) and data pointer. It also stored something else that I don't recall, maybe a previous version record pointer. All packed into 128 bits. Adding a new record version required cmpxchg16b, but reading it or just updating a flag was tricky because the 64bit words only had meaning together so I had to detect torn writes and retry the read with appropriate memory barriers.

CyberDildonics 6y ago
This means though, that you were somehow synchronizing a larger record using this technique. Maybe you were writing it in one thread, then atomically changing your 128 bit struct to make it available to other threads. Whatever else was part of your 128 bit struct could probably be part of the record instead. You could use a 64 bit address and a 64 bit version number. Looking up could be done by atomically reading the 64 bit version number only. Writing a new record would then require the compare and swap.
- eloff 6y ago
  Yes, that's correct, that's actually the obvious way to write it. I think the logic behind putting it in the index was to be able to check the transaction timestamp without the extra indirection and cache miss, and to have that information there if the data is on disk, and there is no record loaded in memory. Not having the indirection was a big deal for the cache eviction algorithm which sampled many records and then evicted the coldest %, weighted for frequency of access and size. There are other ways of doing that though, I'm not sure the trade off was the best one in the end.
  - CyberDildonics 6y ago
    Right, so it isn't about lots of algorithms being prevented, it is actually a pretty reasonable constraint and not a huge deal. If you were worried about cache and indirection, the indices could be aligned to the start of a 64 byte or 128 byte boundary, since 64 bytes is the cache line size but (Intel) cpus will load two cache lines at a time. Because of this, loading in your 64 bit/8 byte index should mean that the 120 bytes after it are going to be cached.

by eloff 6y ago

CyberDildonics 6y ago

This means though, that you were somehow synchronizing a larger record using this technique. Maybe you were writing it in one thread, then atomically changing your 128 bit struct to make it available to other threads. Whatever else was part of your 128 bit struct could probably be part of the record instead. You could use a 64 bit address and a 64 bit version number. Looking up could be done by atomically reading the 64 bit version number only. Writing a new record would then require the compare and swap.

eloff 6y ago
Yes, that's correct, that's actually the obvious way to write it. I think the logic behind putting it in the index was to be able to check the transaction timestamp without the extra indirection and cache miss, and to have that information there if the data is on disk, and there is no record loaded in memory. Not having the indirection was a big deal for the cache eviction algorithm which sampled many records and then evicted the coldest %, weighted for frequency of access and size. There are other ways of doing that though, I'm not sure the trade off was the best one in the end.
- CyberDildonics 6y ago
  Right, so it isn't about lots of algorithms being prevented, it is actually a pretty reasonable constraint and not a huge deal. If you were worried about cache and indirection, the indices could be aligned to the start of a 64 byte or 128 byte boundary, since 64 bytes is the cache line size but (Intel) cpus will load two cache lines at a time. Because of this, loading in your 64 bit/8 byte index should mean that the 120 bytes after it are going to be cached.