current/doc/Concurrency.txt

Several concurrency issues arise whenever a database is accessed
simultaniously be multiple processes or threads
(lightweight processes sharing all their system
ressources like memory and open files, including file positions).


*       multiprocess (MP) environments

MP environments are distinguished according to
-       whether all processes are readonly or there are one or more writers
-       whether processes are single-shot
        (i.e. open, work, exit like CGI scripts, including PHP in CGI mode)
        or resident (like PHP module living in Apache 1.x/Unix childs).
        Note that PHP module in a multithreaded server is not multiprocess.

Within a readonly environment, there is not much of a problem.
Each process may read and cache file contents independent of each other.
So the rest of this section discusses read/write access.

In the presence of writers, there are some problems:
-       at least the actual writing accesses must be *strictly* mutually exclusive
-       it must be ensured that readers do not use old cached data
        (or at least use it in a well controlled manner)
-       it must be ensured that changed data is written and read in a consistent way

These problems are addressed in reverse order:
-       the data structures used in OpenIsis are designed so
        that a consistent way of reading and writing can be defined.
        For example, the XRF pointer to a new or changed record is written
        after the record, so readers will not see an invalid pointer.
        However, this will work only where the operating system guarantees
        such semantics for file reads/writes. This again may depend on the
        filesystem and will not hold for most network file systems.
-       learning which cached blocks are outdated is not possible
        with reasonable effort. One possible approach is to not cache at all,
        i.e. resort to the operating system cache, which hopefully is
        properly synchronized (see above).
-       A simple and well supported means of mutual exclusion is the use
        of exclusive file locks. flock-(BSD-)style locks are sufficient;
        we do not need locking of file regions nor locking over NFS,
        which is not reliable anyway (and it's not much better with SMB).

The most easy and reliable solution is to completely encapsulate
any access --from database open to close-- within an exclusive lock.
That way there clearly is no inconsistent cache.

-       for single-shot processes, this solution is reliable and does
        not incurr too much cost: exit will release any lock and the
        processes may not benefit from caching anyway.
-       for resident processes, the need to open and close on any request
        is more of a disadvantage, and it is a problem how to guarantee
        that any lock is released after processing.

Possible perfomance enhancements that might be implemented one day:
-       readers could use shared locks.
        however, this gives a risk of writer starvation.
-       if all data access methods are carefully checked and a reasonable
        local file system is used, non-caching readers could get by without
        locking at all.
-       another, quite complex approach is to share cache memory between processes,
        similar to ORACLE's SGA. This would also help in guaranteeing consistent
        read-write-sequences.


To summarize the multiprocess issues:
-       readonly access is fine
-       DO NOT TRY TO WRITE ON A NETWORK DRIVE
        (or at least make sure it is accessed only by one host at a time)
-       the best solution for multiple processes is to contact
        a server for writing instead of doing it themselves
-       for PHP as module in read/write mode,
        we have to rely on register_shutdown_function to close any db


*       multithreaded environments

OpenIsis is designed to run multithreaded.
Multithreading is used only within some sort of server
(like database, web or servlet engine) in order to run multiple
requests from multiple clients in parallel.

MT environments are distinguished according to
-       whether they support active dispatching of requests to threads
-       whether they support parallel IO.
        Besides the basic calls for parallel IO (like pread,pwrite,
        or ReadFileEx "overlapped" IO in Win speak, which is missing on Win 9x/Me),
        this also requires condition variables (like pthread_cond_wait/broadcast,
        which are rather difficult to emulate on Win 9x/Me in the absence
        of SignalObjectAndWait) and should include memory mapping
        (like mmap,msync, which is working poorly on Win 9x/Me).

All threads of a single process share the same cache,
so dirty caches are not an issue here.
Synchronization is cheaper and more easy to use.

However, this great performance benefit comes at a price:
While there are a few utilities without any side effects
(i.e. proper FORTRAN functions),
not only access to the database and it's cache,
but any access to system ressources like files or the memory
heap must be carefully checked for possible collisions and,
when in doubt, must be synchronized -- even in a readonly environment.


*       Session synchronization

Our strategy is to share as little as possible between threads
and to protect all that must be shared (basically the database)
by a single lock. The means to give each thread it's own,
unshared environment is the SESSION.


A session represents a single client accessing the database.
(At least this is the idea, but depends on the dispatcher's abilities,
see below).  The session may hold result sets from previous queries,
some authentication info from the client and other temporary data.
In a standalone environment like the Tk GUI not connected to a server,
there is only one session, the "default session" (session id 0).
In a database or web-server, however, there may exist several sessions
on behalf of several users at the same time.

Requests from each session are serialized by some dispatcher,
so that each session is accessed by at most one thread at a time.
Consequently, in an environment with one session only,
there also is only one thread used to access the database.


To summarize, from a session's point of view, the world is single threaded.
Each session has a private memory heap and even it's own IO stream buffers
stdin, stdout and stderr (as streams 0,1,2)
and need not care about how it is connected and to whom.
Since the dispatcher guarantees that no session is accessed
by more than one thread at a time, dynamic memory, streaming
IO and other session ressources can be used without further interlocking.


*       dispatching requests and locking sessions

Due to the dual nature of a session as both representing a user and serving
as object of synchronization, dispatching requests has two tasks:
-       ensuring serialized (single-threaded) access
-       finding the session bound to a given user

While the former is crucial in MT environments, the latter is used only if
-       the environment identifies a user session in the first place
-       the session object's ability to keep state (like result sets) is used

We distinguish two cases of when and how dispatching is done:
-       passive/late dispatching:
        In most environments we have to get the session from within a thread
        dedicated to that request. The dispatcher is implemented as a call,
        accessing a session pool protected by some mutex.
-       active/early dispatching:
        Within the database server, the proper session can be looked up
        before a thread is allocated for a request.
        Here, the dispatcher is an active component, probably running in a
        thread on it's own (thus not requiring a mutex on the session pool).
        That way several requests on the same session may be queued
        (or discarded) without consuming any thread ressources.
        This should yield better performance under high load and somewhat
        better protection against denial of service.

There are also two different situations with regard to the scope
of synchronization:
-       per request:
        The session is "locked" (somehow marked as busy) until processing
        the request has finished. Locking is done by the dispatcher,
        and unlocking must be performed on exit,
        e.g. using register_shutdown_function in PHP.
        For the passive dispatcher, if some user session id is used to locate
        an existing session and there is already a request executing in this session,
        the current thread has to wait.
-       per use:
        In a high level language, i.e. Java, basic synchronization is achieved
        by having a Java object representing the session and marking the
        appropriate methods as synchronized.

Note that unless we promise that sessions actually will remember some state,
a simple dispatcher may decide to operate on a session pool of size 1 (one),
containing only the default session, thus ruling out any parallel operation.


*       Configuration synchronization

Operations that change the overall system state like opening a database
are allowed for session 0 only. Consequently, IO (logging) and memory
associated with such operations is bound to the default session.
Databases may be marked for exclusive use by session 0
for example during a lengthy batch index update
or in order to perform structural changes like modifying the FDT.


On the other hand, the worker sessions need some confidence that
configuration is not going to change while they are in the midth of
processing a request. Therefore, any database that is somehow accessed
by a session, is marked as used by the session and marked as unused
when the session is released. This protects the database from being
closed or put in exclusive ("single-user") mode and thus also
configuration from being changed.


Note that a request for the database need not be the same as
the original user request. For a database server, the request for
a database operation is all that is known, thus clients issuing
several remote requests won't get no guarantee that the DB is unchanged
between database accesses (regardless of the environment they are running in).
When accessing a local database, the scope of locking depends on
the environment as described above. An explicit lock on a local
database might be provided for Java (to be unlocked in a finally clause).


However, the situation is not as bad as it might look, since there are
complex database accesses, bundling several operations into one.
A standard example is to perform a query and not only obtain a result set,
but also the contents of the first n records, like with a Z39.50
piggybacked "present". For remote databasse access,
this is the most efficient operation mode anyway.


*       Database synchronization

All database ressources like master file and index have associated
in memory structures like a cache. These structures must not be
accessed by more than one thread at once and are therefore protected
by a mutex (some "mutual exclusion" object like a critical section).

Again, there are two modes to distinguish:
-       basic mutex
        The database (actually all databases) are locked when starting an
        access like reading or writing a record or searching an index,
        and unlocked when done.
        Since there is not very much and especially no IO happening outside
        the database access, it doesn't make much sense to allow parallel
        access in the first place and we will rather resort to a
        one-session environment. 
-       parallel IO
        This is the interesting case to be discussed now

Parallel IO aims at using the time one thread has to wait for
an IO operation to complete in order to let another thread
use the CPU and possibly start additional IOs.
Therefore, the mutex is released during IO.

In certain situations like thread A wishing to access a cache page
being read by another thread B, A has to wait on a condition
which will be signaled by B after returning from the IO.


The mutex and condition are implemented by an OpenIsisLockFunc,
which may map it to a pthread mutex and associated condition variable.
This is very similar to the concept of a monitor as implemented
by Java's synchronized blocks.


The mutual exclusion could be made even more finegrained by using
one mutex per database and another one for global structures.
With parallel IO, however, the mutex is locked only during CPU use and
released during IO, so this, while adding overhead,
would hardly increase concurrency on a single CPU system.
On a Windoze box capable of basic mutex only, on the other hand,
you would probably not access multiple databases anyway.


*       Summary by environments

The following gives an overview of simple approaches
to be used in basic implementations:
-       PHP/Apache1.x/Unix, any CGI:
        Multiple processes use mutual exclusion based on file locking.
        Database must be closed after request.
        Actually, file locking is performed always on database open/close,
        without asking whether there might be other processes.
-       PHP/MT/windoze:
        Uses trivial dispatcher, requests fully synchronized on default session.
-       PHP/MT/Apache2.0:
        May use real dispatcher, once the MT-Apache is stable.
-       Java:
        May use non-trivial dispatcher, if it provides LockFunc.
-       OpenIsis server:
        Uses active dispatcher /
>       Server  multiplexer


*       Notes on PHP

For various PHP run modes, see
>       http://www.php.net/manual/en/features.persistent-connections.php

As of Feb.03, several extensions are
>       http://www.php.net/manual/en/faq.obtaining.php  listed
as being NOT thread-safe!


---
        $Id: Concurrency.txt,v 1.6 2003/02/18 18:10:20 kripke Exp $
1	Several concurrency issues arise whenever a database is accessed
2	simultaniously be multiple processes or threads
3	(lightweight processes sharing all their system
4	ressources like memory and open files, including file positions).
5
6
7	* multiprocess (MP) environments
8
9	MP environments are distinguished according to
10	- whether all processes are readonly or there are one or more writers
11	- whether processes are single-shot
12	(i.e. open, work, exit like CGI scripts, including PHP in CGI mode)
13	or resident (like PHP module living in Apache 1.x/Unix childs).
14	Note that PHP module in a multithreaded server is not multiprocess.
15
16	Within a readonly environment, there is not much of a problem.
17	Each process may read and cache file contents independent of each other.
18	So the rest of this section discusses read/write access.
19
20	In the presence of writers, there are some problems:
21	- at least the actual writing accesses must be strictly mutually exclusive
22	- it must be ensured that readers do not use old cached data
23	(or at least use it in a well controlled manner)
24	- it must be ensured that changed data is written and read in a consistent way
25
26	These problems are addressed in reverse order:
27	- the data structures used in OpenIsis are designed so
28	that a consistent way of reading and writing can be defined.
29	For example, the XRF pointer to a new or changed record is written
30	after the record, so readers will not see an invalid pointer.
31	However, this will work only where the operating system guarantees
32	such semantics for file reads/writes. This again may depend on the
33	filesystem and will not hold for most network file systems.
34	- learning which cached blocks are outdated is not possible
35	with reasonable effort. One possible approach is to not cache at all,
36	i.e. resort to the operating system cache, which hopefully is
37	properly synchronized (see above).
38	- A simple and well supported means of mutual exclusion is the use
39	of exclusive file locks. flock-(BSD-)style locks are sufficient;
40	we do not need locking of file regions nor locking over NFS,
41	which is not reliable anyway (and it's not much better with SMB).
42
43	The most easy and reliable solution is to completely encapsulate
44	any access --from database open to close-- within an exclusive lock.
45	That way there clearly is no inconsistent cache.
46
47	- for single-shot processes, this solution is reliable and does
48	not incurr too much cost: exit will release any lock and the
49	processes may not benefit from caching anyway.
50	- for resident processes, the need to open and close on any request
51	is more of a disadvantage, and it is a problem how to guarantee
52	that any lock is released after processing.
53
54	Possible perfomance enhancements that might be implemented one day:
55	- readers could use shared locks.
56	however, this gives a risk of writer starvation.
57	- if all data access methods are carefully checked and a reasonable
58	local file system is used, non-caching readers could get by without
59	locking at all.
60	- another, quite complex approach is to share cache memory between processes,
61	similar to ORACLE's SGA. This would also help in guaranteeing consistent
62	read-write-sequences.
63
64
65	To summarize the multiprocess issues:
66	- readonly access is fine
67	- DO NOT TRY TO WRITE ON A NETWORK DRIVE
68	(or at least make sure it is accessed only by one host at a time)
69	- the best solution for multiple processes is to contact
70	a server for writing instead of doing it themselves
71	- for PHP as module in read/write mode,
72	we have to rely on register_shutdown_function to close any db
73
74
75	* multithreaded environments
76
77	OpenIsis is designed to run multithreaded.
78	Multithreading is used only within some sort of server
79	(like database, web or servlet engine) in order to run multiple
80	requests from multiple clients in parallel.
81
82	MT environments are distinguished according to
83	- whether they support active dispatching of requests to threads
84	- whether they support parallel IO.
85	Besides the basic calls for parallel IO (like pread,pwrite,
86	or ReadFileEx "overlapped" IO in Win speak, which is missing on Win 9x/Me),
87	this also requires condition variables (like pthread_cond_wait/broadcast,
88	which are rather difficult to emulate on Win 9x/Me in the absence
89	of SignalObjectAndWait) and should include memory mapping
90	(like mmap,msync, which is working poorly on Win 9x/Me).
91
92	All threads of a single process share the same cache,
93	so dirty caches are not an issue here.
94	Synchronization is cheaper and more easy to use.
95
96	However, this great performance benefit comes at a price:
97	While there are a few utilities without any side effects
98	(i.e. proper FORTRAN functions),
99	not only access to the database and it's cache,
100	but any access to system ressources like files or the memory
101	heap must be carefully checked for possible collisions and,
102	when in doubt, must be synchronized -- even in a readonly environment.
103
104
105	* Session synchronization
106
107	Our strategy is to share as little as possible between threads
108	and to protect all that must be shared (basically the database)
109	by a single lock. The means to give each thread it's own,
110	unshared environment is the SESSION.
111
112
113	A session represents a single client accessing the database.
114	(At least this is the idea, but depends on the dispatcher's abilities,
115	see below). The session may hold result sets from previous queries,
116	some authentication info from the client and other temporary data.
117	In a standalone environment like the Tk GUI not connected to a server,
118	there is only one session, the "default session" (session id 0).
119	In a database or web-server, however, there may exist several sessions
120	on behalf of several users at the same time.
121
122	Requests from each session are serialized by some dispatcher,
123	so that each session is accessed by at most one thread at a time.
124	Consequently, in an environment with one session only,
125	there also is only one thread used to access the database.
126
127
128	To summarize, from a session's point of view, the world is single threaded.
129	Each session has a private memory heap and even it's own IO stream buffers
130	stdin, stdout and stderr (as streams 0,1,2)
131	and need not care about how it is connected and to whom.
132	Since the dispatcher guarantees that no session is accessed
133	by more than one thread at a time, dynamic memory, streaming
134	IO and other session ressources can be used without further interlocking.
135
136
137	* dispatching requests and locking sessions
138
139	Due to the dual nature of a session as both representing a user and serving
140	as object of synchronization, dispatching requests has two tasks:
141	- ensuring serialized (single-threaded) access
142	- finding the session bound to a given user
143
144	While the former is crucial in MT environments, the latter is used only if
145	- the environment identifies a user session in the first place
146	- the session object's ability to keep state (like result sets) is used
147
148	We distinguish two cases of when and how dispatching is done:
149	- passive/late dispatching:
150	In most environments we have to get the session from within a thread
151	dedicated to that request. The dispatcher is implemented as a call,
152	accessing a session pool protected by some mutex.
153	- active/early dispatching:
154	Within the database server, the proper session can be looked up
155	before a thread is allocated for a request.
156	Here, the dispatcher is an active component, probably running in a
157	thread on it's own (thus not requiring a mutex on the session pool).
158	That way several requests on the same session may be queued
159	(or discarded) without consuming any thread ressources.
160	This should yield better performance under high load and somewhat
161	better protection against denial of service.
162
163	There are also two different situations with regard to the scope
164	of synchronization:
165	- per request:
166	The session is "locked" (somehow marked as busy) until processing
167	the request has finished. Locking is done by the dispatcher,
168	and unlocking must be performed on exit,
169	e.g. using register_shutdown_function in PHP.
170	For the passive dispatcher, if some user session id is used to locate
171	an existing session and there is already a request executing in this session,
172	the current thread has to wait.
173	- per use:
174	In a high level language, i.e. Java, basic synchronization is achieved
175	by having a Java object representing the session and marking the
176	appropriate methods as synchronized.
177
178	Note that unless we promise that sessions actually will remember some state,
179	a simple dispatcher may decide to operate on a session pool of size 1 (one),
180	containing only the default session, thus ruling out any parallel operation.
181
182
183	* Configuration synchronization
184
185	Operations that change the overall system state like opening a database
186	are allowed for session 0 only. Consequently, IO (logging) and memory
187	associated with such operations is bound to the default session.
188	Databases may be marked for exclusive use by session 0
189	for example during a lengthy batch index update
190	or in order to perform structural changes like modifying the FDT.
191
192
193	On the other hand, the worker sessions need some confidence that
194	configuration is not going to change while they are in the midth of
195	processing a request. Therefore, any database that is somehow accessed
196	by a session, is marked as used by the session and marked as unused
197	when the session is released. This protects the database from being
198	closed or put in exclusive ("single-user") mode and thus also
199	configuration from being changed.
200
201
202	Note that a request for the database need not be the same as
203	the original user request. For a database server, the request for
204	a database operation is all that is known, thus clients issuing
205	several remote requests won't get no guarantee that the DB is unchanged
206	between database accesses (regardless of the environment they are running in).
207	When accessing a local database, the scope of locking depends on
208	the environment as described above. An explicit lock on a local
209	database might be provided for Java (to be unlocked in a finally clause).
210
211
212	However, the situation is not as bad as it might look, since there are
213	complex database accesses, bundling several operations into one.
214	A standard example is to perform a query and not only obtain a result set,
215	but also the contents of the first n records, like with a Z39.50
216	piggybacked "present". For remote databasse access,
217	this is the most efficient operation mode anyway.
218
219
220
221	* Database synchronization
222
223	All database ressources like master file and index have associated
224	in memory structures like a cache. These structures must not be
225	accessed by more than one thread at once and are therefore protected
226	by a mutex (some "mutual exclusion" object like a critical section).
227
228	Again, there are two modes to distinguish:
229	- basic mutex
230	The database (actually all databases) are locked when starting an
231	access like reading or writing a record or searching an index,
232	and unlocked when done.
233	Since there is not very much and especially no IO happening outside
234	the database access, it doesn't make much sense to allow parallel
235	access in the first place and we will rather resort to a
236	one-session environment.
237	- parallel IO
238	This is the interesting case to be discussed now
239
240	Parallel IO aims at using the time one thread has to wait for
241	an IO operation to complete in order to let another thread
242	use the CPU and possibly start additional IOs.
243	Therefore, the mutex is released during IO.
244
245	In certain situations like thread A wishing to access a cache page
246	being read by another thread B, A has to wait on a condition
247	which will be signaled by B after returning from the IO.
248
249
250	The mutex and condition are implemented by an OpenIsisLockFunc,
251	which may map it to a pthread mutex and associated condition variable.
252	This is very similar to the concept of a monitor as implemented
253	by Java's synchronized blocks.
254
255
256	The mutual exclusion could be made even more finegrained by using
257	one mutex per database and another one for global structures.
258	With parallel IO, however, the mutex is locked only during CPU use and
259	released during IO, so this, while adding overhead,
260	would hardly increase concurrency on a single CPU system.
261	On a Windoze box capable of basic mutex only, on the other hand,
262	you would probably not access multiple databases anyway.
263
264
265	* Summary by environments
266
267	The following gives an overview of simple approaches
268	to be used in basic implementations:
269	- PHP/Apache1.x/Unix, any CGI:
270	Multiple processes use mutual exclusion based on file locking.
271	Database must be closed after request.
272	Actually, file locking is performed always on database open/close,
273	without asking whether there might be other processes.
274	- PHP/MT/windoze:
275	Uses trivial dispatcher, requests fully synchronized on default session.
276	- PHP/MT/Apache2.0:
277	May use real dispatcher, once the MT-Apache is stable.
278	- Java:
279	May use non-trivial dispatcher, if it provides LockFunc.
280	- OpenIsis server:
281	Uses active dispatcher /
282	> Server multiplexer
283
284
285	* Notes on PHP
286
287	For various PHP run modes, see
288	> http://www.php.net/manual/en/features.persistent-connections.php
289
290	As of Feb.03, several extensions are
291	> http://www.php.net/manual/en/faq.obtaining.php listed
292	as being NOT thread-safe!
293
294
295	---
296	$Id: Concurrency.txt,v 1.6 2003/02/18 18:10:20 kripke Exp $