malbrain/btree-source-code

A working project for High-concurrency B-tree source code in C

Btree-source-code

A working project for High-concurrency B-tree source code in C. You probably want to download the separate database project for the latest version. Most C files compile under both Windows and Linux.

An idea being investigated in the multi-root-node subdirectory removes the locking load on the root node by creating a read-only copy of the latest updated root version. The root is updated out-of-band.

New B-tree page management code using a skiplist instead of sorted arrays for key searching is under development in a sub-directory. This approach removes the need for a latching protocol for page reading and writing.

Note: The most recent running multi-threaded/multi-process B-tree and ARTree code can be found in a separate repository: https://github.com/malbrain/database.

Here are the projects under btree-source-code:

• btree2: Single Threaded/MultiProcess versions that remove keys all the way back to an original empty btree, placing removed nodes on a free list. Operates under either memory mapping or file I/O. Recommended btrees hosted on network file systems.

• threads2: Multi-Threaded with latching implemented by a latch manager with test & set latches in the first few btree pages.

• threadskv: Multi-Threaded/Multi-Process based on threads2i.c that generalizes key/value storage in the btree pages. The page slots are reduced to 16 or 32 bits, and the value byte storage occurs along with the key storage.

btree-source-code's Issues

bit of confused about 'volatile'?

in threads2/threads2h.c

typedef struct {
BtLatch readwr[1]; // read/write page lock
BtLatch access[1]; // Access Intent/Page delete
BtLatch parent[1]; // Posting of fence key in parent
BtSpinLatch busy[1]; // slot is being moved between chains
volatile ushort next; // next entry in hash table chain
volatile ushort prev; // prev entry in hash table chain
volatile ushort pin; // number of outstanding locks
volatile ushort hash; // hash slot entry is under
volatile uid page_no; // latch set page number
} BtLatchSet;

typedef struct {
uid basepage; // mapped base page number
char *map; // mapped memory pointer
ushort slot; // slot index in this array
ushort pin; // mapped page pin counter
void *hashprev; // previous pool entry for the same hash idx
void *hashnext; // next pool entry for the same hash idx
} BtPool;

i believe the above two structs has some similar features, one is for latchset, the other one is for page pool, they are both acquired using hash table, but there is no 'volatile' in BtPool, especially on key word 'hashprev' and 'hashnext', is it because when we pin BtPool, we only write lock the hash table slot, but when we pin BtLatchSet, we first read lock the hash table slot, if not found, then we impose the write on hash table slot?

Why not lock the file in bt_mgr()?

in threads2/threads2h.c, what if two progresses are creating btree manager with the same name at the same time? Shouldn't we lock the file?

How to use the btree2v API for inserts and reads

Hello,

We are trying to integrate your btree2v into our project. We want to use the insert and read APIs, but we are not sure what values to pass to these functions:

extern uid bt_findkey  (BtDb *bt, unsigned char *key, uint len);
extern BTERR  bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod);

As a user of the b-tree, we know the key and value but we are unsure as to how to use this API.
Your help would be much appreciated.

What is the license for this project?

I want to quote your code, please provide the license type, thank you！

WriteLock confusion

Hi malbrain:
I have some confusions about the WriteLock in btree2u.c, here is the code

#define PHID 0x1 // writer phase (0/1)
#define PRES 0x2 // writer present

w = PRES | (tix & PHID);
r = __sync_fetch_and_add (lock->rin, w);

My confusion is that why you use two bits(PRES |(tix & PHID)) in writer, what does the PHASE and PRESENT mean? It seems only one bit can work, because there is only one active writer at the most

Thanks^^

Considering Btree as an option for new SQLite backend muxer

Hello,

Just to let you know that LumoSQL is collecting the very few K-V stores that are broadly compatible into backend storage options for SQLite. We haven't studied this project in detail yet but so far it looks like it is a candidate as much as the others. And as discussed on the SQLite forum some of your design features seem well worth adding to SQLite.

Dan

How do we choose which part of cache tree and main tree to merge?

I have read the LSM Tree paper, but still have some parts that don't understand. If cache tree needs to merge, how do we determine which multi page block in main tree and which part in cache tree to merge? since keys in main tree will overlap if we do not choose carefully? Is it ok that we keep two pointers in cache tree and main tree to help the merge?

Also, do you have some blogs or articles that explain LSM Tree in detail?

confused about atomic operation?

in threadskv/threads7.c

you add atomic operation to btree, basically we acquire a lock using each key's hash value, then we conduct the normal insert routine, why this would make operation atomic and what's the use of this atomic operation?

How come that there will not be two threads modifying same parent?

what if there are two childs modifying the same parent? since each child have a ParentModification lock, they can just lock it and modify their same parent at the same time.

Is LSM tree perform better than btree?

I have just finished implementing concurrent btree, and now i am trying to optimize it, so is LSM tree perform better than btree?
<> by Patrick O'Neil, Edward Cheng. This is the paper that i should start with if i were to implement lsm tree?

Is it ok to remove all 'volatile' key word in threads2/threads2h.c?

does it affect the correct behavior of the program?