Jim Starkey
2005-02-15 23:58:03 UTC
The single most contentious issue in the merge debate will be memory
pools. Here is some background.
The History
My use of memory pools goes back to PDP-11 Datatrieve. The PDP-11 was a
16 bit machine, but unlike the 286, didn't have segment registers. A 16
bit address space was it. Most of the too-many PDP-11 operating systems
gave user code the full 64K. An exception was the most popular one,
RSTS, which took 8K to map the Basic interpreter (or something). To
give decent functionality in limited address space, density was
everything. Datatrieve used three pools. The permanent pool (metadata)
started at the end of code an grew up. The execution (temporary) pool
start at the top of the address space and grew down. What was left over
in the middle was available for sort space. At the end of request
execution, the lower limit of the execution pool was moved back to the
top of the address space.
VAX Datatrieve had more address space but more challenges. The product
was architected as a callable facility fronted ended by a "terminal
server". An interactive user could have only one active request, but
the Datatrieve server (the product did automatic, network wide query
decomposition), also a front end to the callable facility, could and did
support multiple active requests. Rather than write request memory
garbage collect code, I kept the remnants of the Datatrieve-11 pool
architecture to support a per-request compilation pool (purged at the
end of request compilation) and a per-request runtime pool (purged at
the end of request execution).
Interbase, originally gds/Galaxy, was targeted at the Unix workstation
market, effectively split between 100% 68000 and the rest MicroVAX.
Workstations in that era were 3MB to 4 MB machines, max.
Galaxy/Interbase had to share address space and physical memory with the
client program and OS runtime services. Compared to the PDP-11, it was
generous, but if the virtual space exceeded physical memory, it flogged
itself to death. I used pools again, but for a different reasons. The
primary reasons were that the code to intelligently delete the more
complex execution structures would have been quite large in code size,
fragile, and prone to memory leakage and corruption. Allocating request
specific memory from a request pool allow the entire request to vanish
with a pool deletion.
The memory pool allocator was rewritten for Firebird 1.5, but the
semantics were unchanged.
Objects and Complexity
C++ has two huge advantages over C. One is polymorphism (Dimitry will
be happy to explain), generally referred to as inheritance in
object-speak. Where C would have a single structure that had to
represent many variations of a theme, C++ supports a type hierarchy of
like-minded objects with different implementations. This allows, for
example, a whole hierarchy of runtime node with different internal
representation but sharing a common interface. The second huge advance
was destructors -- code called by the infrastructure when an object was
deleted to clean up after itself.
At least two big things have changed since the original release of
Interbase in 1985. One is that virtual address space and physical
memory configurations are huge and growing. The other, not unrelated,
is that the complexity of software has mushroomed. The answer to almost
unbounded complexity is object technology that allows complex
implementation to be encapsulated into externally simple objects.
Object technology demands a price, however, and that price shouldn't be
a surprise to database engineers. That price is referential integrity.
Objects are created, establish relationships to other objects, and are
destroyed. For this to work, the integrity of object relationships must
be guaranteed. Garbage collected languages like Java and Lisp never
reclaim objects for which a pointer exists. C++, at least not the way
we use it, is not garbage collected, so the responsibility maintaining
the integrity of inter-object relationships falls of the programmer.
There are many ways to do this (one size does NOT fit all), but it must
be done. C++ provides the hook -- the class destructor, a method called
by the language infrastructure to break its relationship to other
objects, preserving the integrity of the data structures.
The memory pool architecture inherited by Firebird from Datatrieve-11 is
based on the assumption that all pointers in the execution structure are
either to permanent things or to other things in the same pool. At one
point, this was a simplifying aassumption that significantly reduced the
code size and complexity. Interbase/Firebird has grown dramatically
since then, and the code to manage pools now dwarfs the code necessary
to cleanup individual objects. At the same time, the fact that the
destructor mechanism is not respected by Firebird memory pools means
that resource management of individual objects can not be managed by the
object but must be managed globally across the entire code base. It is
not sufficient for an engineer to understand the implementation of an
object and its immediate clients to work on an object, it is necessary
for him or her to understand the entire system to know when that object
can disappear without notice, leaving related objects with broken pointers.
Object oriented technology, in short, is incompatible with
delete-by-pool. We can choose objects, we can choose memory pools, but
we can't choose both.
Peripheral Issues
A variety of defenses of memory pools have been raised. Here are some
answers.
One argument is locality of reference -- that objects within the same
pool are physically close, reducing page faults. Answer: a full 32 bit
address space worth of physical memory is about $600. If machines page
fault, locality won't help.
Another argument is that pool induced locality improves processor cache
efficiency when multiple threads are scheduled on different processors.
Answer: A running request makes memory references to code (shared),
metadata (shared), lock tables (shared), and execution objects (shared
after compiled request caching in enabled). The only code that is
thread specific is the request impure area which probably accounts for
less than 10% of memory references. A 10% theoretical improvement is
overwhelmed with more practical efficiencies of object encapsulation.
NUMA (non-uniform memory access). One hardware architecture for very
large numbers of processors in a single physical address space involves
clusters of processors sharing a memory controller. Local memory
references are fast. Memory references outside the cluster invoke a
message exchange to the processor cluster controlling the memory. The
argument is that on a NUMA machine, pools can take advantage of cluster
aware memory allocators to ensure that allocated memory is local the the
processor cluster. Answer: First, NUMA machines don't exist in our
space. Second, the same argument against process/thread/cache affinity
apply to NUMA, but even more so. Third, classic, where all memory
references are local, is a more appropriate architecture for a NUMA
machine. Fourth, a NUMA machine is a dog for database management, which
is disk bound, not cpu bound. The way to make a NUMA machine do fast
database access is to put the database in a different cabinet connected
with a big pipe.
Bottom Line
Memory pools as used by Firebird are incompatible with object oriented
programming. You can pick objects or you can pick pools. Yes, classes
can be made pool-aware, but has nothing to do with the problem of
referential integrity between objects. Simply put, ripping an object
out of a complex structure when its parent memory pool is deleted
destroys the integrity of that data structure.
There is a compromise position that works but is of questionable value,
which is to support memory pools with the restriction that deleting a
pool containing an active object is a fatal error. It is consistent
with most of the pro-pool arguments as well as object referential
integrity. The benefit is problematic, at best.
pools. Here is some background.
The History
My use of memory pools goes back to PDP-11 Datatrieve. The PDP-11 was a
16 bit machine, but unlike the 286, didn't have segment registers. A 16
bit address space was it. Most of the too-many PDP-11 operating systems
gave user code the full 64K. An exception was the most popular one,
RSTS, which took 8K to map the Basic interpreter (or something). To
give decent functionality in limited address space, density was
everything. Datatrieve used three pools. The permanent pool (metadata)
started at the end of code an grew up. The execution (temporary) pool
start at the top of the address space and grew down. What was left over
in the middle was available for sort space. At the end of request
execution, the lower limit of the execution pool was moved back to the
top of the address space.
VAX Datatrieve had more address space but more challenges. The product
was architected as a callable facility fronted ended by a "terminal
server". An interactive user could have only one active request, but
the Datatrieve server (the product did automatic, network wide query
decomposition), also a front end to the callable facility, could and did
support multiple active requests. Rather than write request memory
garbage collect code, I kept the remnants of the Datatrieve-11 pool
architecture to support a per-request compilation pool (purged at the
end of request compilation) and a per-request runtime pool (purged at
the end of request execution).
Interbase, originally gds/Galaxy, was targeted at the Unix workstation
market, effectively split between 100% 68000 and the rest MicroVAX.
Workstations in that era were 3MB to 4 MB machines, max.
Galaxy/Interbase had to share address space and physical memory with the
client program and OS runtime services. Compared to the PDP-11, it was
generous, but if the virtual space exceeded physical memory, it flogged
itself to death. I used pools again, but for a different reasons. The
primary reasons were that the code to intelligently delete the more
complex execution structures would have been quite large in code size,
fragile, and prone to memory leakage and corruption. Allocating request
specific memory from a request pool allow the entire request to vanish
with a pool deletion.
The memory pool allocator was rewritten for Firebird 1.5, but the
semantics were unchanged.
Objects and Complexity
C++ has two huge advantages over C. One is polymorphism (Dimitry will
be happy to explain), generally referred to as inheritance in
object-speak. Where C would have a single structure that had to
represent many variations of a theme, C++ supports a type hierarchy of
like-minded objects with different implementations. This allows, for
example, a whole hierarchy of runtime node with different internal
representation but sharing a common interface. The second huge advance
was destructors -- code called by the infrastructure when an object was
deleted to clean up after itself.
At least two big things have changed since the original release of
Interbase in 1985. One is that virtual address space and physical
memory configurations are huge and growing. The other, not unrelated,
is that the complexity of software has mushroomed. The answer to almost
unbounded complexity is object technology that allows complex
implementation to be encapsulated into externally simple objects.
Object technology demands a price, however, and that price shouldn't be
a surprise to database engineers. That price is referential integrity.
Objects are created, establish relationships to other objects, and are
destroyed. For this to work, the integrity of object relationships must
be guaranteed. Garbage collected languages like Java and Lisp never
reclaim objects for which a pointer exists. C++, at least not the way
we use it, is not garbage collected, so the responsibility maintaining
the integrity of inter-object relationships falls of the programmer.
There are many ways to do this (one size does NOT fit all), but it must
be done. C++ provides the hook -- the class destructor, a method called
by the language infrastructure to break its relationship to other
objects, preserving the integrity of the data structures.
The memory pool architecture inherited by Firebird from Datatrieve-11 is
based on the assumption that all pointers in the execution structure are
either to permanent things or to other things in the same pool. At one
point, this was a simplifying aassumption that significantly reduced the
code size and complexity. Interbase/Firebird has grown dramatically
since then, and the code to manage pools now dwarfs the code necessary
to cleanup individual objects. At the same time, the fact that the
destructor mechanism is not respected by Firebird memory pools means
that resource management of individual objects can not be managed by the
object but must be managed globally across the entire code base. It is
not sufficient for an engineer to understand the implementation of an
object and its immediate clients to work on an object, it is necessary
for him or her to understand the entire system to know when that object
can disappear without notice, leaving related objects with broken pointers.
Object oriented technology, in short, is incompatible with
delete-by-pool. We can choose objects, we can choose memory pools, but
we can't choose both.
Peripheral Issues
A variety of defenses of memory pools have been raised. Here are some
answers.
One argument is locality of reference -- that objects within the same
pool are physically close, reducing page faults. Answer: a full 32 bit
address space worth of physical memory is about $600. If machines page
fault, locality won't help.
Another argument is that pool induced locality improves processor cache
efficiency when multiple threads are scheduled on different processors.
Answer: A running request makes memory references to code (shared),
metadata (shared), lock tables (shared), and execution objects (shared
after compiled request caching in enabled). The only code that is
thread specific is the request impure area which probably accounts for
less than 10% of memory references. A 10% theoretical improvement is
overwhelmed with more practical efficiencies of object encapsulation.
NUMA (non-uniform memory access). One hardware architecture for very
large numbers of processors in a single physical address space involves
clusters of processors sharing a memory controller. Local memory
references are fast. Memory references outside the cluster invoke a
message exchange to the processor cluster controlling the memory. The
argument is that on a NUMA machine, pools can take advantage of cluster
aware memory allocators to ensure that allocated memory is local the the
processor cluster. Answer: First, NUMA machines don't exist in our
space. Second, the same argument against process/thread/cache affinity
apply to NUMA, but even more so. Third, classic, where all memory
references are local, is a more appropriate architecture for a NUMA
machine. Fourth, a NUMA machine is a dog for database management, which
is disk bound, not cpu bound. The way to make a NUMA machine do fast
database access is to put the database in a different cabinet connected
with a big pipe.
Bottom Line
Memory pools as used by Firebird are incompatible with object oriented
programming. You can pick objects or you can pick pools. Yes, classes
can be made pool-aware, but has nothing to do with the problem of
referential integrity between objects. Simply put, ripping an object
out of a complex structure when its parent memory pool is deleted
destroys the integrity of that data structure.
There is a compromise position that works but is of questionable value,
which is to support memory pools with the restriction that deleting a
pool containing an active object is a fatal error. It is consistent
with most of the pro-pool arguments as well as object referential
integrity. The benefit is problematic, at best.