Databases with V

The ppcoming talk on CRDTs is scheduled tomorrow. November talk is yet to be scheduled link to the PWL Bangalore - https://hasgeek.com/pwl_bangalore

Visualisation of sorting algorithms with Hungarian folk dance https://youtube.com/playlist?list=PLOmdoKois7_FK-ySGwHBkltzB11snW7KQ&si=tUxRmpIy-GzwJ4AT

This one is full of math, if that's your thing - https://arxiv.org/pdf/1806.10254.pdf

My colleague is a CRDT expert with a whole series of blog posts on them. This is a gold mine! Check out - https://www.bartoszsypytkowski.com/the-state-of-a-state-based-crdts/

Next Papers We Love Bangalore meetup is happening in two days and is about CRDTs. The paper is Keep CALM and CRDT On - https://www.vldb.org/pvldb/vol16/p856-power.pdf I tried to read when the paper came out and didn't understand a thing. Time to get back to it! If my memory serves correctly, the paper requires an understanding of CRDTs and CALM theory. Using CALM, they solve some particular problems of CRDTs, hence the title. (or I could be totally wrong) I asked on Twitter about prerequisite resources and am going through them - https://twitter.com/iavins/status/1713910568116253009

This ♥️

(reposted because the font was too small earlier)

tip: avoid magic in your code - https://dodov.dev/blog/magical-software-sucks

if you are looking for a side project idea - https://news.ycombinator.com/item?id=37897921

I find Telegram/WhatsApp low friction to post anything, so I will probably post more and post here first rather than on Twitter. You get early exclusive database stuff :p The only downside is feedback and Q&A. On Twitter, I get many DMs, and I enjoy the Q&A as I learn a lot from them. So keep the questions coming on Twitter or email.

That's it! This is the five minute summary of the paper. If you'd like to learn more, Andy has a great lecture video on database logging and recovery: Database Logging - https://www.youtube.com/watch?v=5blTGTwKZPI Database Recovery - https://www.youtube.com/watch?v=xoZmZGKxRYM

The conclusion

Here is another count of I/O pages written to disk, in regular and statement logging schemes. (lesser is better)

The results of the experiment. They made the changes in SQLite and measured them against a few typical applications. You can see the reduction in the I/O time (lesser is better). Twitter, for some reason, sees a remarkable decline!

The paper also uses Phase Change Memory, a fancy name for Durable RAM, to store the WAL log statements. So, writes are byte-addressable and crazy fast. https://en.wikipedia.org/wiki/Phase-change_memory

They mention the caveats, too. This approach works for mobile devices where the typical workload is a shory transaction with small changes. The workloads also exhibit strong update locality. Meaning the same recent rows get updated again and again.

I am still reading the paper, and there are some parts I still need to understand fully. But I can share the grand idea. There are three types of logging in Databases. 1. Physical Logging - writing entire pages 2. Logical Logging - writing just the query statements 3. Physiological Logging - a kind of mix of both The SQLite WAL does Physical Logging. In Logical Logging, instead of writing 20 pages, you could write the SQL statement, which changed all rows. The update statement from the previous example is just a few bytes. This suddenly reduces write amplification. But Logical Logging introduces a whole bunch of problems. One is related to the transaction consistent checkpointing and concurrent writes. The paper goes into detail, explaining both. They also explain how to do recovery in case of a crash. Here is what they do, 1. For writes, they write the log statements 2. They keep the changed pages in memory 3. Any new read requests they can be read from the in memory pages 4. At regular checkpoints, these WAL pages are flushed to disk and written to the main DB file 5. In case of a crash, they replay the WAL log of statements and build the pages again