spudd86 / stasis Goto Github PK

Currently there is one redblack tree to store dirty pages, and it's protected 
by a single mutex. Rusty's suggestion is to partition the tree into multiple 
internal trees, each protected by its own mutex. Then we can benchmark it and 
see if it helps increase concurrency. 

--Michi

What steps will reproduce the problem?
1. go to hedora.ath.cx/doc/
2. wait

What is the expected output? What do you see instead?

I would expect the docs to appear, I get a timeout, I also tried with 
http://isup.me/hedora.ath.cx/doc/

What version of the product are you using? On what operating system?

latest firefox and chrome on ubuntu 13.04

Perhaps based on GiST

The lock manager is broken.  Also, it needs to be modified to use commit 
callbacks, which will remove hard-coding in Tcommit(), Tabort() and friends.

Currently, steal/force logging (which skips redos) of LSN-free pages will
lead to corruption at recovery.

The issue is that the force-write can update a reused page.  This page may
have been written to in the past by other log entries, which REDO might
replay (since the page is LSN-free).  Since the force-write does not log
the REDOs, replaying old entries corrupts the only copy of the data on disk.

The solution is to have the analysis phase detect this, and mark some pages
"known clean".  In ARIES, this would be an optimization; with lsn-free +
force it is needed for correctness.  Note that the list of known-clean
pages can be unbounded in size.  Two mechanisms solve the problem:

 - first, we can use a range tree to store the known clean pages; this
means that each lsn-free force region will use at most a few bytes of
memory at recovery.
 - when the range tree exhausts RAM, we can evict the highest range in the
tree.  Redo will then skip all entries above the eviction point.  We then
mark the range REDO covered known-clean, and repeat analysis + redo until
the entire log is recovered.  This adds log passes, but may actually
improve redo performance, as it acts as a blocked nested loop join

Also, Stasis' redo phase is currently not parallelizable.  Fixing this bug
will add support for concurrent redo.

Add two methods:

TarrayListReadRange()
TarrayListWriteRange()

This will allow Stasis' ArrayList type (with entry size = 1) to emulate a
standard file.  It will also be needed for the XSXL m-tree port to support
variable length items.

[deleted issue]

Pinning one page, then pinning a bunch of other ones leads to a deadlock in
the new concurrent buffer manager.  This is being tickled by LSM tree
implementations, and the unit test "stalePinConcurrentBufferManager" in
check_bufferManager.c

Provide segment-based recovery for ranges of array list entries.

Use cases:

1. Write-back to buffer manager when updating arrays of fixed length segments
2. General-purpose, append-only segment store

This cannot be done until Issue 4 is addressed.

What steps will reproduce the problem?

1. compile in RHEL5 2.6.18-164.el5, glibc 2.5 and run test


What is the expected output? What do you see instead?

*** glibc detected ***
stasis-read-only/build/test/stasis/check_lockManager: double free or
corruption (fasttop): 0x000000001b4d4dc0 ***
======= Backtrace: =========
/lib64/libc.so.6[0x310d8722ef]
/lib64/libc.so.6(cfree+0x4b)[0x310d87273b]
stasis-read-only/build/src/stasis/libstasis.so[0x2ae4d5571841]
stasis-read-only/build/src/stasis/libstasis.so[0x2ae4d5571c72]
stasis-read-only/build/src/stasis/libstasis.so(lhinsert+0x16f [0x2ae4d55720cc]
stasis-read-only/build/src/stasis/libstasis.so(pblHtInsert+0x84)[0x2ae4d557247f]
stasis-read-only/build/src/stasis/libstasis.so(createLock+0x94)[0x2ae4d557cdad]
stasis-read-only/build/src/stasis/libstasis.so(lockManagerReadLockHashed+0x10c)[
0x2ae4d557cf11]
stasis-read-only/build/src/stasis/libstasis.so(lockManagerReadLockRecord+0x1c)[0
x2ae4d557d66c]
stasis-read-only/build/test/stasis/check_lockManager(ridWorkerThread+0xc2)[0x401
95b]
/lib64/libpthread.so.0[0x310e4064a7]
/lib64/libc.so.6(clone+0x6d)[0x310d8d3c2d]
======= Memory map: ========
*** glibc detected ***
stasis-read-only/build/test/stasis/check_lockManager: double free or
corruption (!prev): 0x000000001b4ee420 ***
======= Backtrace: =========
***Exception: Other


What version of the product are you using? On what operating system?

RHEL5 2.6.18-164, GLIBC 2.5

Please provide any additional information below.

passed all other test cases

What steps will reproduce the problem?
1. Read existing log entries during normal operation.

What is the expected output? What do you see instead?

The log maintains multiple file handles, one of which is used for writes. 
Reading from the log causes the write handle to flush.  The write handle is
opened with O_SYNC.  Therefore, reading recently written log entries incurs
synchronous disk writes.

Global variables prevent Stasis' components from running in separate
processes / machines, and prevent multiple Stasis instances from running in
the same process.

Also, Stasis exports symbols that often clash with user applications.  The
output of 'nm --defined-only -g libstasis.so' should only include symbols
that start with 'stasis_' or 'T'.

Ashok's new fault injection script non-deterministically leads to data
corruption.

A number of unit tests non-deterministically fail in allocationPolicy.c and
dirtyPageTable.c  They are all due to mismatches with state stored in
libredblack.

Compile the attached hashtest.c file as follows:

gcc hashtest.c -lstasis -lpthread -lm

Running ./a.out yields the following:

ashok@ashok-desktop:~$ ./a.out 
found = 41
a.out: hashtest.c:80: main: Assertion `found == -1' failed.
Aborted

The assertion failure occurs because I do a hash-table lookup of a key that
was never inserted and expect a return value of -1.  However, I get a bogus
return value of '41'.

Mechanisms allowing records to be swapped, slot id's to be compacted would
make it much easier to balance tree nodes.

For some reason, Rose' compressed pages are failing to set their impl
pointers when they're swapped back in.  This leads to a segfault once rose
starts hitting disk.

In the current design, Page->LSN contains a valid LSN, even for LSN-free
pages.  Instead, if the page is LSN-free, it should contain a special
constant, such as LSN_FREE or INVALID_LSN.

One out of many runs of check_io produced the following:

28/34 Testing: check_io
28/34 Test: check_io
Command: "/bin/nice" "./check_io" 
Directory: /home/sears/workspace/stasis/build/test/stasis
"check_io" start time: Apr 19 18:00 PDT
Output:
----------------------------------------------------------
io:
        io_memoryTest...io_memoryTest
Seed = 1271725238
Running concurrency test with 68259 values
pass
        io_fileTest...io_fileTest
pass
        io_pfileTest...Warning: There is a race condition between force()
and truncate() in file.c (This shouldn't matter in practice, as the logger
hasn't moved over to use file.c yet.
Seed = 1271725336
io_pfileTest
Seed = 1271725404
Running concurrency test with 92623 values
pass
        io_nonBlockingTest_file...io_nonBlockingTest
check_io: /home/sears/workspace/stasis/test/stasis/check_io.c:238:
load_handle: Assertion `*(int*)(r->buf) == t->values[val]' failed.
Seed = 1271725487
Warning: There is a race condition between force_range() and truncate() in
file.c (This shouldn't matter in practice, as the logger hasn't moved over
to use file.c yet.
----------------------------------------------------------
"check_io" end time: Apr 19 18:04 PDT
"check_io" time elapsed: 00:04:09
----------------------------------------------------------

This is low priority because there is no reason to enable non_blocking on
modern Linux systems.

r1179 introduced a performance regression.

In order to write a CLR, we copy the compensated entry into the new entry.
 This causes the log to seek backwards, and perform a read.  The log has
not been optimized for this case, and performs a synchronous write in order
to obtain the older entry.

Add an array of fields to transaction structs.  At the end of each
transcation, consult the fields.  For each non-zero field, invoke a
corresponding callback.  This avoids useless allocator work, and is
generally useful.  It also reduces the amount of hard-coded logic in tcommit.

Since the field is in the transcation table, it allows such mechanisms to
avoid a mutex acquisition.

It is currently difficult to run the unit tests against out-of-tree stasis
modules.  The problem is that the makefiles don't link in the third-party
.so, and don't know what factory methods have been replaced.  Some sort of
an LD_PRELOAD or environment variable would solve the issue.

One proposal: check to see if the environment variable STASIS_ADDON_LIBRARY
is defined.  If so, dlopen it, then lookup the symbol "stasis_addon_init",
and call it with zero arguments.

Commit r1299 fixes the build by disabling the unit test on machines that
are missing libcheck.  Stasis no longer depends on libcheck, so this is a
terrible kludge.

Currently, ArrayList generates a log entry for each page that it allocates.
 (The entry is generated inside of TfixedPageInitialize().  Instead, it
should generate a redo that does not specify a page, but instead iterates
over a range of pages at recovery.  Of course, the redo/undo should check
page lsns.

Currently ringbuffer.c uses /dev/shm, which is not available in some 
environments. Instead, create a file in /tmp and mmap it. 

--Michi

A number of modules make use of global mutexes.  Remove the ones obtained
by each page pin and log operation.

Rose tends to go break periodically because it is not tested by make test.

Here are some glitches in transforming it into an XCode project.
There are some non-optional failures, with no obvious fixes. 

========

masood-mortazavis-macbook-pro:Stasis masood$ cmake -G XCode
CMake Error: Could not create named generator XCode
masood-mortazavis-macbook-pro:Stasis masood$ cmake -G Xcode
-- The C compiler identification is GNU
-- The CXX compiler identification is GNU
-- Checking whether C compiler has -isysroot
-- Checking whether C compiler has -isysroot - yes
-- Checking whether C compiler supports OSX deployment target flag
-- Checking whether C compiler supports OSX deployment target flag - yes
-- Check for working C compiler using: Xcode
-- Check for working C compiler using: Xcode -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Checking whether CXX compiler has -isysroot
-- Checking whether CXX compiler has -isysroot - yes
-- Checking whether CXX compiler supports OSX deployment target flag
-- Checking whether CXX compiler supports OSX deployment target flag - yes
-- Check for working CXX compiler using: Xcode
-- Check for working CXX compiler using: Xcode -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Found FLEX: /usr/bin/flex (found version "2.5.35")
-- Found BISON: /usr/bin/bison (found version "2.3")
-- Could NOT find Doxygen (missing:  DOXYGEN_EXECUTABLE) 
-- doxygen not found; documentation will not be built
-- libconfuse not found; sample application 'libdfa' will not be built
-- fuse not found; sample application 'stasis_fuse' will not be built
-- Looking for sync_file_range
-- Looking for sync_file_range - not found
-- Looking for fdatasync
-- Looking for fdatasync - found
-- Looking for tdestroy
-- Looking for tdestroy - not found
-- dbug not found. proceeding with normal build
-- Looking for powl
-- Looking for powl - found
-- Performing Test HAVE_O_DIRECT
-- Performing Test HAVE_O_DIRECT - Failed
-- Performing Test HAVE_ALLOCA_H
-- Performing Test HAVE_ALLOCA_H - Success
-- Performing Test HAVE_GETLINE
-- Performing Test HAVE_GETLINE - Failed
-- Performing Test HAVE_GCC_ATOMICS
-- Performing Test HAVE_GCC_ATOMICS - Success
-- Performing Test HAVE_PTHREAD_STACK_MIN
-- Performing Test HAVE_PTHREAD_STACK_MIN - Success
-- Configuring done
-- Generating done
-- Build files have been written to: /Users/masood/Development/Stasis