BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage • Hacker News Board

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#21

Post by nneonneo » Sat, Oct 13, 2018, 2:39 PM UTC

heavenlyhash wrote: post #8

This is really interesting... ... so I'm really a bit bewildered and sad by some of the engineering choices they made along the way, like requiring a modified kernel : https://github.com/oscarlab/betrfs/blob/master/README.md#com... The reasons are detailed just above that link target, but are somewhat absurd IMHO: they modified the kernel's `struct task_struct` to pass error values, rather than fixing one of their li…

All the reasons given boil down to “we didn’t want to mess with TokuDB”. The build process (requiring specific GCC versions, CMake, and a bunch of packages including Valgrind), the errno patch to task_struct, and the half dozen libc stub functions are all there because TokuDB expects userspace libc.

I don’t know whether the authors ever attempted to patch TokuDB itself (or streamline it down to the essentials for the kernel). Instead they appear to have just taken the entire userspace-designed library and hacked the kernel until it fit. It’s a halfway-decent strategy if your goal is to get the thing off the ground as quickly as possible, but obviously a real implementation would have to ship a modified TokuDB instead (it’s OSS, so it should be hackable!)

This is pretty common in academia, sadly. As an academic who has released some academic OSS code myself, I can say that often there’s just not enough time or motivation to fix a blob of code into a generally usable format. Often it’s released just so that we can say “hey we open-sourced it so other researchers can build on it/replicate our results”. This may be one of the reasons why academic ideas don’t make it out to the real world that quickly.

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#22

Post by ramses0 » Sat, Oct 13, 2018, 2:52 PM UTC

nneonneo wrote: post #21

heavenlyhash wrote: post #8

This is really interesting... ... so I'm really a bit bewildered and sad by some of the engineering choices they made along the way, like requiring a modified kernel : https://github.com/oscarlab/betrfs/blob/master/README.md#com... The reasons are detailed just above that link target, but are somewhat absurd IMHO: they modified the kernel's `struct task_struct` to pass error values, rather than fixing one of their li…

All the reasons given boil down to “we didn’t want to mess with TokuDB”. The build process (requiring specific GCC versions, CMake, and a bunch of packages including Valgrind), the errno patch to task_struct, and the half dozen libc stub functions are all there because TokuDB expects userspace libc. I don’t know whether the authors ever attempted to patch TokuDB itself (or streamline it down to the essentials for the…

It makes sense, V1 is the hack (speed) and if it gets traction then you push for a V2 with different constraints and more market information (leverage).

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#23

Post by bradleykuszmaul » Sat, Oct 13, 2018, 2:54 PM UTC

mirekrusin wrote: post #9

What's the story with patent/license on fractal tree by tokutek (now percona)? Can you use it for personal use only? Ie. you can't use it at work without a license? What about Bε-trees - are there patent free implementations?

Tokutek licensed the fractal tree under GPLv2 with an explicit patent license to make clear that anyone could use the fractal tree code. I don't know what Percona did after the aquisiton.

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#24

Post by espeed » Sat, Oct 13, 2018, 2:54 PM UTC

nneonneo wrote: post #21

heavenlyhash wrote: post #8

This is really interesting... ... so I'm really a bit bewildered and sad by some of the engineering choices they made along the way, like requiring a modified kernel : https://github.com/oscarlab/betrfs/blob/master/README.md#com... The reasons are detailed just above that link target, but are somewhat absurd IMHO: they modified the kernel's `struct task_struct` to pass error values, rather than fixing one of their li…

All the reasons given boil down to “we didn’t want to mess with TokuDB”. The build process (requiring specific GCC versions, CMake, and a bunch of packages including Valgrind), the errno patch to task_struct, and the half dozen libc stub functions are all there because TokuDB expects userspace libc. I don’t know whether the authors ever attempted to patch TokuDB itself (or streamline it down to the essentials for the…

Note that some of the people involved are also the original authors of TokuDB [0], including Bradley Kuszmaul [1] , Michael Bender [2], and Martin Farach-Colton [3] who were the founders of Tokutek (acquired by Percona in 2015).

Previous discussion with the authors: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing https://news.ycombinator.com/item?id=9248298

[0] TokuDB Fractal Tree Index https://github.com/Tokutek/ft-index TokuDB Engine https://github.com/percona/tokudb-engine

[1] Bradley Kuszmaul http://people.csail.mit.edu/bradley/startups.html

[2] Michael Bender https://www3.cs.stonybrook.edu/~bender/

[3] Martin Farach-Colton https://www.cs.rutgers.edu/~farach/

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#25

Post by tobias3 » Sat, Oct 13, 2018, 3:50 PM UTC

nneonneo wrote: post #21

heavenlyhash wrote: post #8

This is really interesting... ... so I'm really a bit bewildered and sad by some of the engineering choices they made along the way, like requiring a modified kernel : https://github.com/oscarlab/betrfs/blob/master/README.md#com... The reasons are detailed just above that link target, but are somewhat absurd IMHO: they modified the kernel's `struct task_struct` to pass error values, rather than fixing one of their li…

All the reasons given boil down to “we didn’t want to mess with TokuDB”. The build process (requiring specific GCC versions, CMake, and a bunch of packages including Valgrind), the errno patch to task_struct, and the half dozen libc stub functions are all there because TokuDB expects userspace libc. I don’t know whether the authors ever attempted to patch TokuDB itself (or streamline it down to the essentials for the…

TokuDB seems to be written in C++. It's neat that they managed to make that work in-kernel.

Also there are patent notices in the TokuDB files.

So probability of it being in Linux at some point approaches zero. And with the patents they even made the whole technique unviable for any Linux fs (haven't looked at them in detail obviously).

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#26

Post by yjftsjthsd-h » Sat, Oct 13, 2018, 4:18 PM UTC

wazoox wrote: post #20

yjftsjthsd-h wrote: post #13

Earlier quoted context omitted.

I wouldn't actually apply such an invasive patch on any system I ever cared about anyway, but I wonder if it would work on the RHEL/CentOS kernel, which has a supposed version of 3.10?

It has very little to do with a 3.10, for instance it includes XFS v5 which was introduced in kernel 3.16.

Hence "supposed version"; it's my impression that they backported a non-trivial amount from as far forward as the 4.x series.

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#27

Post by espeed » Sat, Oct 13, 2018, 4:28 PM UTC

tobias3 wrote: post #25

nneonneo wrote: post #21

Earlier quoted context omitted.

All the reasons given boil down to “we didn’t want to mess with TokuDB”. The build process (requiring specific GCC versions, CMake, and a bunch of packages including Valgrind), the errno patch to task_struct, and the half dozen libc stub functions are all there because TokuDB expects userspace libc. I don’t know whether the authors ever attempted to patch TokuDB itself (or streamline it down to the essentials for the…

TokuDB seems to be written in C++. It's neat that they managed to make that work in-kernel. Also there are patent notices in the TokuDB files. So probability of it being in Linux at some point approaches zero. And with the patents they even made the whole technique unviable for any Linux fs (haven't looked at them in detail obviously).

See Bradley's comment wrt to licensing the fractal tree code as GPLv2 w/ a patent provision https://news.ycombinator.com/item?id=18208209

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#28

Post by chx » Sat, Oct 13, 2018, 4:41 PM UTC

y4mi wrote: post #2

Btrfs vs betrfs... This is going to cause so much confusion Ah, but the project isn't new, so I guess it's not a new problem

AAAAAAAH

I always wondered why on earth they named a filesystem after Soviet armored personal carriers. But no, it's "betterfs" without the vowels. Got it.

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#29

Post by loeg » Sat, Oct 13, 2018, 4:50 PM UTC

y4mi wrote: post #2

Btrfs vs betrfs... This is going to cause so much confusion Ah, but the project isn't new, so I guess it's not a new problem

I had guessed they replaced btrfs' B-trees with Bε-trees. Anyway, I don't think there is much concern -- this seems like academic/corporate abandonwaware more as a proof of concept than anything else.

Re: BetrFS: An in-kernel file system that uses Bε trees to organize on-disk storage

#30

Post by loeg » Sat, Oct 13, 2018, 4:50 PM UTC

bradleykuszmaul wrote: post #23

mirekrusin wrote: post #9

What's the story with patent/license on fractal tree by tokutek (now percona)? Can you use it for personal use only? Ie. you can't use it at work without a license? What about Bε-trees - are there patent free implementations?

Tokutek licensed the fractal tree under GPLv2 with an explicit patent license to make clear that anyone could use the fractal tree code. I don't know what Percona did after the aquisiton.

Any idea what year the patent clock times out?