Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Build a Database in 3000 Lines with 0 Dependencies

build-your-own.org

Post reply on HN
Print view View original

11–20 of 59 posts

Re: Build a Database in 3000 Lines with 0 Dependencies

#11

Post by cryptonector »

Re: copy-on-write (CoW) B-tree vs append-only log + non-CoW B-tree, why not both?

I.e., just write one file (or several) as a B-tree + a log, appending to log, and once in a while merging log entries into the B-tree in a CoW manner. Essentially that's what ZFS does, except it's optional when it really shouldn't be. The whole point of the log is to amortize the cost of the copy-on-write B-tree updates because CoW B-tree updates incur a great deal of write magnification due to having to write all new interior blocks for all leaf node writes. If you wait to accumulate a bunch of transactions then when you finally merge them into the tree you will be able to share many new interior nodes for all those leaf nodes. So just make the log a first-class part of the database.

Also, the log can include small indices of log entries since the last B-tree merge, and then you can accumulate even more transactions in the log before having to merge into the B-tree, thus further amortizing all that write magnification. This approaches an LSM, but with a B-tree at the oldest layer.

Re: Build a Database in 3000 Lines with 0 Dependencies

#12

Post by cryptonector »

andai wrote: post #5

I looked into this at one point, I was typing out entire codebases for didactic purposes: SQLite 3 was 120,000 lines of code, but SQLite 2 was 12,000. So for a bit more effort you get a battle tested real world thing!

The proprietary test suite for SQLite3 is much much larger still. The battle-testedness comes in great part from that.

Re: Build a Database in 3000 Lines with 0 Dependencies

#13

Post by andai »

ianmcgowan wrote: post #10
andai wrote: post #5

I looked into this at one point, I was typing out entire codebases for didactic purposes: SQLite 3 was 120,000 lines of code, but SQLite 2 was 12,000. So for a bit more effort you get a battle tested real world thing!

Really puts the auto- in didact! Very curious to hear how this worked for you; it’s almost directly the opposite of the copilot approach. I learned assembler by typing in listings from magazines and hand dis-assembling and debugging on paper. Your approach seems similar in spirit, but who has the times these days?

I learned this from Zed Shaw's Learn X The Hard Way books. He says this approach is mainstream in other disciplines, like music, languages, or martial arts.

I also heard the philosopher Ken Wilber spent a few years (in what kids today call Monk Mode) writing out great books by hand.

The main effect I noticed is that I rapidly gain muscle memory in a new programming language, library or codebase.

The other effect is that I'm forced to round-trip every token through my brain, which is very helpful as my eyes tend to glaze over — often I'll be looking right at an obvious bug without seeing it.

Re: Build a Database in 3000 Lines with 0 Dependencies

#14

Post by andai »

esmy wrote: post #8
andai wrote: post #5

I looked into this at one point, I was typing out entire codebases for didactic purposes: SQLite 3 was 120,000 lines of code, but SQLite 2 was 12,000. So for a bit more effort you get a battle tested real world thing!

Wait you took a repo and started typing it into the IDE? Could you please expand on what benefits you noticed and how it affected your understanding of the language? It sounds like a fascinating way to force attention to the code simply reading it wouldn't.

Yeah I just open two panes in Sublime Text, with the source on the right and then I type it out verbatim on the right.

I make an effort to keep the line numbers synced. Sometimes I skip long repetitive blocks or comments. But I do type out like 80% of the actual characters in the file.

It's about 500 lines per hour fot me, so I can estimate reasonably well how long it'll take.

It's not necessarily an efficient thing to do — you'd get way more bang for your buck just poking around, asking questions, trying to make small changes. But for reasonably small projects, you can type it out in a few hours, or a day or two. Then you've "round-tripped" every single token through your brain (though sadly not with a meaningful amount of conscious reflection) -- unless you pause and ask questions along the way.

See also my other comment above.

Re: Build a Database in 3000 Lines with 0 Dependencies

#15

Post by qianli_cs »

I've read a similar series from Phil back in 2020: "Writing a SQL database from scratch in Go" https://notes.eatonphil.com/database-basics.html

The code is available on GitHub: https://github.com/eatonphil/gosql (it's specifically a PostgreSQL implementation in Go).

It's cool to build a database in 3000 lines, but for a real production-ready database you'll need testing. Would love to see some coverage on correctness and reliability tests. For example, SQLite has about 590 times more test code than the library itself. (https://www.sqlite.org/testing.html)

Re: Build a Database in 3000 Lines with 0 Dependencies

#16

Post by sitkack »

andai wrote: post #14
esmy wrote: post #8

Earlier quoted context omitted.

Wait you took a repo and started typing it into the IDE? Could you please expand on what benefits you noticed and how it affected your understanding of the language? It sounds like a fascinating way to force attention to the code simply reading it wouldn't.

Yeah I just open two panes in Sublime Text, with the source on the right and then I type it out verbatim on the right. I make an effort to keep the line numbers synced. Sometimes I skip long repetitive blocks or comments. But I do type out like 80% of the actual characters in the file. It's about 500 lines per hour fot me, so I can estimate reasonably well how long it'll take. It's not necessarily an efficient thing…

Instead of a book club, have a code typing club, DuoTypo

It would be funny to type it until it builds, and then type it until the tests pass.

Re: Build a Database in 3000 Lines with 0 Dependencies

#17

Post by chickenzzzzu »

andai wrote: post #14
esmy wrote: post #8

Earlier quoted context omitted.

Wait you took a repo and started typing it into the IDE? Could you please expand on what benefits you noticed and how it affected your understanding of the language? It sounds like a fascinating way to force attention to the code simply reading it wouldn't.

Yeah I just open two panes in Sublime Text, with the source on the right and then I type it out verbatim on the right. I make an effort to keep the line numbers synced. Sometimes I skip long repetitive blocks or comments. But I do type out like 80% of the actual characters in the file. It's about 500 lines per hour fot me, so I can estimate reasonably well how long it'll take. It's not necessarily an efficient thing…

Not to offend you, and you've already pointed out the better way to do it, but I don't think there is too much to gain from this approach. When I was learning Vulkan for example, the only thing this helped me learn was which functions they were calling from the API. Their variable names and ifdefs and wrapper functions were completely useless to me. I was able to get their 5000 lines down to just 1000-- and that was for a single untextured cube with direct memory management and simple surface handling. Imagine if it had been more complex? 20,000 lines of typing for little reason. My neck aches thinking about it :)
Post reply on HN