5 ms·

Hi @thesz! The experiment you are referring to is done in main memory with an optimised in-memory B+tree implementation. We didn't plot the performance for lar

Hi @thesz! The experiment you are referring to is done in main memory with an optimised in-memory B+tree implementation. We didn't plot the performance for larger page sizes because in our machine they performed poorly, as you can already see from the configuration with 1024-byte pages. So we're not favouring our approach at all. Note also that next-gen memories have smaller and smaller access granularities. For example, the Intel's Optane DC Persistent Memory accesses blocks of 256 bytes, while the Intel's Optane DC SSD accesses blocks of 4 KB. I guess that data structures with blocks of 16K-256K are disproportionate in these cases. About LSM-trees, nothing prevents you to use a PGM-index (which you can construct during the compaction of levels, thus without scanning data twice) to speed up the search on a long immutable level. Or also, to use a PGM-index on data which is organised into RLE-compressed disk pages ;)

thesz 6y ago
These blocks of 256 bytes most probably are stored in wear-leveling database of some sort hidden inside NVME. These databases are often LSM-tree-based. So, writing larger blocks still has benefits, especially when you use compression. If you think you only need 256 byte pages, average price for 10G hard disk drive is ~$300 [1] and average price for 2G SSD drive is also ~$300 [2]. [1] https://pcpartpicker.com/trends/internal-hard-drive/?__cf_chl_jschl_tk__=eb7d19a0fee0bae06773db51e2c24a49f42029c3-1611596989-0-Adt7I3palOe6T-fvjO6FGFk_pRP00ftthDItecT3JfzPGiQ6CuX-Hfa2JO6g_EKqbCnhalJe3Gt1Pm7IJ7erKPDnlDBr6q_0Ms3wwqQ5DHDSJlIfxr9bn6QkzIZ-aYwpf8MM1M3Vwodn4nHYJLrmhTgQt1Z9-ucN8O_wO1WH1LldGQJHiJczZ2M4hzr8jNn1S2XRQ4VHL7QVc90F5tujaUVKKugPerNYyUJPaF-TdnyuA_WYHBp8BomZy8xwmEPHaAq_cBGxHrISynx9gdIW9Xb2-hxVpy8i3251obIYBMQcFSWihe4NfSUt8b_-6zLzBWfuLMkXpTz_qWS5NT_7r7QoMwf8KoJGYj6zKKYYQUmekyRk6nqTsd-oG6mU47co4GR57lLLjX2hlgVVnz6vGok#storage.hdd350.12000 https://pcpartpicker.com/trends/internal-hard-drive/?__cf_ch... [2] https://pcpartpicker.com/trends/internal-hard-drive/?__cf_chl_jschl_tk__=eb7d19a0fee0bae06773db51e2c24a49f42029c3-1611596989-0-Adt7I3palOe6T-fvjO6FGFk_pRP00ftthDItecT3JfzPGiQ6CuX-Hfa2JO6g_EKqbCnhalJe3Gt1Pm7IJ7erKPDnlDBr6q_0Ms3wwqQ5DHDSJlIfxr9bn6QkzIZ-aYwpf8MM1M3Vwodn4nHYJLrmhTgQt1Z9-ucN8O_wO1WH1LldGQJHiJczZ2M4hzr8jNn1S2XRQ4VHL7QVc90F5tujaUVKKugPerNYyUJPaF-TdnyuA_WYHBp8BomZy8xwmEPHaAq_cBGxHrISynx9gdIW9Xb2-hxVpy8i3251obIYBMQcFSWihe4NfSUt8b_-6zLzBWfuLMkXpTz_qWS5NT_7r7QoMwf8KoJGYj6zKKYYQUmekyRk6nqTsd-oG6mU47co4GR57lLLjX2hlgVVnz6vGok#storage.ssdm2nvme.2000 https://pcpartpicker.com/trends/internal-hard-drive/?__cf_ch... Five times price/Gb difference. If you need large storage, you need hard disks. B-trees are good with hard disks, is PGM index good with them too?
- gvinciguerra 6y ago
  From a Big-Oh point of view, the answer is a big yes. No matter the memory technology or the disk page size, be it 256B or 16KB, the PGM-index can scale as B-trees or even better (see my comment here https://news.ycombinator.com/item?id=25901889 https://news.ycombinator.com/item?id=25901889).
  - thesz 6y ago
    Can you provide us with (preferably drop-in) replacement of LMDB as a proof? Because your big-O looks like big-O of cache-oblivious algorithm and I saw no proof of that.
petergeoghegan 6y ago
Are you aware of any contemporary on-disk or in memory DB system that typically uses a page size of 4KiB or less? And if not, are you expecting that to become a trend in the future?

thesz 6y ago

These blocks of 256 bytes most probably are stored in wear-leveling database of some sort hidden inside NVME. These databases are often LSM-tree-based. So, writing larger blocks still has benefits, especially when you use compression. If you think you only need 256 byte pages, average price for 10G hard disk drive is ~$300 [1] and average price for 2G SSD drive is also ~$300 [2]. [1] https://pcpartpicker.com/trends/internal-hard-drive/?__cf_chl_jschl_tk__=eb7d19a0fee0bae06773db51e2c24a49f42029c3-1611596989-0-Adt7I3palOe6T-fvjO6FGFk_pRP00ftthDItecT3JfzPGiQ6CuX-Hfa2JO6g_EKqbCnhalJe3Gt1Pm7IJ7erKPDnlDBr6q_0Ms3wwqQ5DHDSJlIfxr9bn6QkzIZ-aYwpf8MM1M3Vwodn4nHYJLrmhTgQt1Z9-ucN8O_wO1WH1LldGQJHiJczZ2M4hzr8jNn1S2XRQ4VHL7QVc90F5tujaUVKKugPerNYyUJPaF-TdnyuA_WYHBp8BomZy8xwmEPHaAq_cBGxHrISynx9gdIW9Xb2-hxVpy8i3251obIYBMQcFSWihe4NfSUt8b_-6zLzBWfuLMkXpTz_qWS5NT_7r7QoMwf8KoJGYj6zKKYYQUmekyRk6nqTsd-oG6mU47co4GR57lLLjX2hlgVVnz6vGok#storage.hdd350.12000 https://pcpartpicker.com/trends/internal-hard-drive/?__cf_ch... [2] https://pcpartpicker.com/trends/internal-hard-drive/?__cf_chl_jschl_tk__=eb7d19a0fee0bae06773db51e2c24a49f42029c3-1611596989-0-Adt7I3palOe6T-fvjO6FGFk_pRP00ftthDItecT3JfzPGiQ6CuX-Hfa2JO6g_EKqbCnhalJe3Gt1Pm7IJ7erKPDnlDBr6q_0Ms3wwqQ5DHDSJlIfxr9bn6QkzIZ-aYwpf8MM1M3Vwodn4nHYJLrmhTgQt1Z9-ucN8O_wO1WH1LldGQJHiJczZ2M4hzr8jNn1S2XRQ4VHL7QVc90F5tujaUVKKugPerNYyUJPaF-TdnyuA_WYHBp8BomZy8xwmEPHaAq_cBGxHrISynx9gdIW9Xb2-hxVpy8i3251obIYBMQcFSWihe4NfSUt8b_-6zLzBWfuLMkXpTz_qWS5NT_7r7QoMwf8KoJGYj6zKKYYQUmekyRk6nqTsd-oG6mU47co4GR57lLLjX2hlgVVnz6vGok#storage.ssdm2nvme.2000 https://pcpartpicker.com/trends/internal-hard-drive/?__cf_ch... Five times price/Gb difference. If you need large storage, you need hard disks. B-trees are good with hard disks, is PGM index good with them too?

gvinciguerra 6y ago
From a Big-Oh point of view, the answer is a big yes. No matter the memory technology or the disk page size, be it 256B or 16KB, the PGM-index can scale as B-trees or even better (see my comment here https://news.ycombinator.com/item?id=25901889 https://news.ycombinator.com/item?id=25901889).
- thesz 6y ago
  Can you provide us with (preferably drop-in) replacement of LMDB as a proof? Because your big-O looks like big-O of cache-oblivious algorithm and I saw no proof of that.

petergeoghegan 6y ago

Are you aware of any contemporary on-disk or in memory DB system that typically uses a page size of 4KiB or less? And if not, are you expecting that to become a trend in the future?