From: sss@world.std.com (Sergiu S Simmel)
Subject: Re: Oct 1992 Version of Schema Evolution Support Summary
Organization: Penobscot Development Corporation, Arlington MA
Date: Tue, 13 Oct 1992 01:33:52 GMT


SC| >> Kala
SC|
SC| Kala manages an untyped persistent store, implementing the semantics
SC| of robust, distributed, secure, changing, and shareable persistent
SC| data.  Layers built upon the Kala platform can implement the semantics
SC| of objects with the same properties.
SC|
SC| As it operates below the schema layer, Kala does not address schema
SC| evolution directly. However, It supports the building of schema'ed
SC| layers above it and below the application, and those layers can
SC| provide for schema evolution conveniently using Kala primitives.
SC| This parts-box approach requires extra work on the part of the developer
SC| compared to out-of-the-box solutions, but provides power and
SC| flexibility sufficient for relatively low cost solutions in
SC| difficult environments (e.g. graph-structured data, dynamic classing) 
SC| where no out-of-the-box solution is available.
SC|
SC| [Ivan Godard <ivang@cup.portal.com>]
SC|
SC|
SC|
SC| For more information, contact either Sergiu Simmel (sss@world.std.com)
SC| or Ivan Godard <ivang@cup.portal.com>.
SC|
SC|
SC| REFERENCES:
SC| Sergiu S. Simmel and Ivan Godard. "The Kala Basket: A
SC| Semantic Primitive Unifying Object Transactions,
SC| Access Control, Versions, annd Configurations
SC|
SC| [clamen]


Here is a technical note bringing more detail and specificity to the
relation between Kala and the issue of schema evolution. I hope this
would clarify things further, and bring a flavor of practical
experience and results to the discussion. For questions, please
address them by e-mail to: kala@world.std.com




===========================================================================

                              Kala In Depth

                       09 -- Schema Evolution With Kala

---------------------------------------------------------------------------
     Does Kala support schema evolution? Does this question 
     even make sense? Is it an oxymoron? In one sense - yes: Kala 
     does not have any schema, for all it knows about are bits and 
     pointers. In a different sense - no: we used Kala's primitives to 
     quickly, economically, and efficiently implement a schema evolution 
     facility behind Smalltalk.
---------------------------------------------------------------------------

  At first sight, schema evolution in Kala might appear to be as 
much an oxymoron as attorney ethics. After all, Kala is essentially 
a typeless persistent data manager with no notion of schema (as 
understood in the database world) at all. You give your data to 
Kala; she gives you a hat check. Later on you present your check; 
she gives back your original data. Where is a schema in this? You 
might as well expect that a real hat- check person would have 
changed your Stetson for a straw hat if you dropped it off when you 
were wearing a suit and later picked it up while wearing blue jeans.

  And yet... While at Kala's level there is no representation of a 
schema of which Kala is aware, there nonetheless is a schema 
somewhere in the application. It might be implicit in the code, in 
which case schema evolution with Kala means rewriting the code and 
writing a data translator, the same painful process as if the data 
had been held in a file instead of in the Kala MonadBase. Is this a 
fault of Kala? No, no more than it would be a fault of the file 
system. The fault lies in using an implicit schema.

  How about explicit schemata? A full blown DBMS includes a schema 
manager, and will (with greater or lesser pain) accommodate some 
changes to the schema of already stored data. Clearly such a manager 
could be written atop Kala. However, no such manager comes with Kala 
off the shelf. Why not?

  The answer is that no schema solution short of a universal typing 
model is consistent with the Kala goal of supporting any kind of 
data. The schema managers of conventional DBMSs support a limited 
list of data types (e.g. amounts, dates, etc.) and a small number of 
primitive composition primitives (e.g. tuples and rows). Data of the 
complexity found in actual applications is simply unrepresentable in 
a conventional DBMS. We call this condition schema impedance 
mismatch.

  Kala supports any application data structure, with no mismatch. If 
we put schema knowledge into Kala (again, short of a universal 
typing system ), then some application data structures would be 
schema manageable, and others (those not representable in the chosen 
schema model) would not be schema manageable. A clearly Orwellian 
situation of some data being more equal than others.

-----------------------------
External Schema Specification
---------------------------------------------------------------------------

  Are we then back to the initial oxymoron? Not quite. In certain 
application domains, there already exists a well defined schema, 
imposed from outside the application by the programming language or 
the environment. While Kala gives no language precedence over others 
(unlike the OODB world), nevertheless Kala can support the schema 
model of any application language, once given a bit of code compos- 
ing the Kala primitives.

  In this character, the schema situation in Kala is very much like 
the transaction situation. As with schemata, Kala has no transaction 
model built in, for you to use or suffer through. Instead, Kala 
primitives can be used to support any conceivable transaction model 
of your choice, given a page or two of glue code sitting under the 
API of your model. We say that Kala delivers only mechanism, leaving 
the policy up to you. This is a great virtue if you understand well 
the policy you want; it certainly requires work if you don't.

  Similarly, Kala and glue code can support any externally defined 
schema. You will get the schema evolution facilities inherent in the 
schema model you have chosen. If your application has an implicit 
schema embedded in the code (not recommended), you can use Kala for 
persistence, and schema evolution is as painful as you would expect 
for a schema model which has no allowance for evolution. However, if 
you are using a model which allows for evolution, then Kala (with 
the glue code) will too.

----------
An Example
---------------------------------------------------------------------------

  Here is an example drawn from a recent consulting experience with 
a major and venerable Wall Street firm. The subject matter was a 
Kala application involving trading of specialized securities. 
Because the market, and even the approach to the market, is changing 
very rapidly in this area, the bank realized that speed of applica- 
tion evolution was a critical aspect of their design. Implementa- 
tions in spreadsheets on PCs, or COBOL on mainframes, simply could 
not evolve fast enough to keep up with developments. Consequently, 
they selected Smalltalk as the implementation vehicle, giving up 
performance and familiarity for flexibility and ease of transforma- 
tion.

  The applications need persistence, of course. Various technical, 
security, and scale considerations (irrelevant here) made the 
obvious OODBMS choices unsuitable, and they eventually found Kala. 
The result (development is still in process) is a very large scale 
network of Smalltalk applications floating over some tens of giga- 
bytes of data on the Kala persistence core, using dynamically 
recruited compute servers for performance.

  Smalltalk provides rapid evolution of the application code. 
However, all would be fine if the evolution were stilled by frozen 
schemata on the persistent store. Hence, in this application Kala 
must provide schema evolution.

------------------
The Implementation
---------------------------------------------------------------------------

  Fortunately, Smalltalk also supplies a well worked out externally 
defined schema model. Model design (required by definition in any 
Kala based implementation) is minimal, because we can merely define 
that persistent data is subject to exactly the same semantics for 
schema evolution as is regular non-persistent Smalltalk local data. 
End of design.

  And start of implementation. Schemata in Smalltalk is explicitly 
represented by classes, which are first class objects. Schema evolu- 
tion in Smalltalk amounts to simply any change to a class object. 
Class changes must be propagated to the already existing instances 
of those classes, and that propagation is schema evolution as surely 
as any on a DBMS.

  Because Smalltalk does run time typing throughout (well, almost), 
we always know what kind of thing it is which is given to Kala to be 
made persistent. We require that the class of any persistent object 
(as it was at the time the value was stored) is also a persistent 
object too. This restriction is easily enforced and could be 
performed automatically when necessary as a side effect of the Kala 
Creates.

  Because Kala primitives can be used easily to build very conve- 
nient versioning facilities, it is simple to keep a copy of each 
step in the evolution of  a class. Kala will organize these dif- 
ferent class versions without confusion, and store sufficient 
information with each stored value to identify what version of its 
class is its actual schema. As classes evolve, Kala may accumulate 
quite a bit of legacy data of now outdated class versions, but in 
each datum Kala has the actual class version used for that datum. In 
addition, the application has the class version currently being used.

  Because classes are held in regular monads as far as Kala is 
concerned, they are subject to regular transaction facilities just 
like any other old data. Consequently, different applications, or 
different users of the same application, can be using different 
versions of the same class simultaneously without confusion. Thus 
schema evolution becomes a Commitable operation which for this 
application includes the nested and branching distributed transac- 
tions used by the bank for the data transaction model in this 
application.

  Retaining actual schema information is merely the sine qua non for 
schema evolution under persistence. You also have to recognize and 
deal with the situation when evolution has in fact occurred and some 
persistent datum is out of step with the current application class 
hierarchy.

  The Kala based implementation does this by not bringing the data 
back to memory with its original class, but with a special dedicated 
class built into the implementation. If the data was brought in as 
part of a larger unit of transfer (monad) and is in fact never 
touched by the application, then no further action occurs. However, 
if a legacy datum is touched (in Smalltalk, by sending it a method), 
then the special class intercepts the method in order to perform 
schema verification and evolution as necessary.

  A reference to the class version of the Loaded object (the stored 
version, not the current version of the application) is in the value 
as Loaded. The interception method looks up the current version of 
the same class, and checks whether the stored version and the 
current version are the same. This check could involve a complete 
walk over both class structures, but is optimized by keeping the 
version id (the original Kala mid) in the class instances, and just 
doing a mid equality. Transient changes to the current class 
(changes which are local to the application and have not yet 
resulted in a new persistent version of the class with its own mid) 
simple clobber the saved mid of the current class to nil, thereby 
forcing failure in the equality test of the interception method.

  If the interception method test succeeds, then no change in schema 
has occurred and the true stored object (with the current class) 
replaces the place holder object (with its interception class) in 
memory. Thereafter references proceed at speed. However, if the test 
fails, the interception method invokes Smalltalk's own built-in tool 
for updating instances in the presence of class changes. The result 
is a new value for the object, of the correct current class, 
initialized from the original persistent value Loaded form Kala.

  The newly evolved value is written back (with its new class 
version) using the application's innermost transaction. Subsequent 
Commits will move it back through the succession of nested 
transactions (or may discard it with Fail, of course) until ultima- 
tely it may replace the outdated version. However, if there are 
other application or data structures still referencing the old 
version, then the old version will be retained automatically by 
Kala. In the actual application, regulatory and auditing 
requirements usually produce configuration data structures which 
retain references to the old versions, and so the old version is 
kept indefinitely and will ultimately migrate to archive store as 
part of normal Kala Store sweeping. In other environments, the 
updated value would likely supplant the older version, which would 
be removed from the Store automatically by normal Kala scavenging.

  The whole of the system services of this application - Kala 
interface, distribution and network transmission, multiple 
dynamically acquired compute engines, class maintenance, schema 
evolution, automatic optimistic concurrency control, etc. - are 
being implemented using Kala primitives and facilities of the Kala 
reusable facilities library. The implementation glue code totals 
thirty or forty pages of C, and a similar amount of Smalltalk. Plus 
Kala. A working prototype is a few engineer months, ready for 
documentation and integration with the rest of the application.

----------
Conclusion
---------------------------------------------------------------------------

  So is schema evolution in Kala really so oxymoronic? Yes, in one 
sense -- even in the example application the store itself has no 
schema other than bits and pointers. No, in another sense -- the 
schema model selected for the application, with its incorporated 
notions of schema evolution, has been cheaply and easily extended to 
full persistence using Kala primitives for the mechanism and a small 
amount of glue code for the policy.

  So it comes down to a matter of definition. A Kala application has 
schema evolution. Does Kala? It's the same question as for transac- 
tions - a Kala application clearly has transactions, but does Kala? 
Out of such questions are sales literature made.

  We like to think that it doesn't really matter whether Kala has 
transactions, or schema evolution. What matters is whether the 
application has transactions or schema evolution. Kala gives you a 
powerful and flexible mechanism for the model and policy of your 
choice, without ramming her choice down your throat. In the example 
environment, even OODBMSs which supposedly supported Smalltalk were 
unusable, because the model they supplied/imposed did not anticipate 
the realities of this application. These realities include the fact 
that (using the distributed compute servers) a given Smalltalk image 
will be executing in one transaction environment now and a moment 
later (and without intervening Commits) will be executing in a 
different transaction, while simultaneously from tens to hundreds of 
other Smalltalk images on machines across the net are also executing 
in the same transaction environment.

  Sure, Kala doesn't embed this model either. But now the 
application does.

     +---------------------------------------------------------------+
     |   Copyright (c) 1992, Penobscot Development Corporation.      |
     |   Kala is a Trademark of Penobscot Development Corporation.   |
     +---------------------------------------------------------------+


===========================================================================
===========================================================================


  ___    ___    ___   ________________________________________________________ 
 |   `  |   `  |   `  Sergiu S. Simmel       Penobscot Development Corporation
  \ __   \ __   \ __   50 Princeton Road      Internet: sss@world.std.com
       \      \      \  Arlington, Mass        Voice:  +1-617-646-3951
   ` ___) ` ___) ` ___)  02174-8253 USA         Fax:  +1-617-646-5753 


-- 
  ___    ___    ___   ________________________________________________________ 
 |   `  |   `  |   `  Sergiu S. Simmel       Penobscot Development Corporation
  \ __   \ __   \ __   50 Princeton Road      Internet: sss@world.std.com
       \      \      \  Arlington, Mass        Voice:  +1-617-646-3951