<commit_before>* SPTM - Shared Persistent Transactional Memory
  Simple online storage for lisp data, using the ideas of in-memory 
  persistence and optimistic concurrency control.

  Operates via transaction log stored on Amazon Web Services (S3 and SimpleDB).

** Informal Description of the Ideas
*** In-Memory Persistence
   This idea is also known as Prevalence and there is a Common Lisp
   library [[http://common-lisp.net/project/cl-prevalence/][cl-prevalence]].
   
   All perstent data modifications are expressed as named functions
   with parameters. For example
   
#+BEGIN_SRC common-lisp
   (add-user database :id 1 :name "anton")
   (add-order database id: 117 :user 1 :book "AIMA" :count 1)
   (delete-user database :id 1)
#+END_SRC
   Here =database= is some datastructure where you store the information,
   and =add-user=, =add-order=, =delete-user= are your functions which
   modify the database.
   
   To make the modifications persistent they are executed in transactions
#+BEGIN_SRC common-lisp
   (execute-transaction database 'add-user (list :id 1 :name "anton"))
   (execute-transaction database 'add-order (list id: 117 :user 1 :book "AIMA" :count 1))
   (execute-transaction database 'delete-user (list database :id 1))
#+END_SRC
   
   The =execute-transaction= first applies the specified function to arguments,
   thus modifying the database, and then records the function name and all the arguments,
   except for the =database= argument, to a transaction log. In cl-prevalence
   transaction log is a file on local file system.
   
   When application process is restarted after a crash or normal termination,
   it reads the transaction log and executes the functions specified here.
   In result all the the database modifications are repeated, so the
   application sees it's in-memory database persistent across restarts.
   
   Besides the transaction log, a complete snapshot of database can be stored.
   Therefore the full procedure of restoring the in-memory database state
   when application is restarted is to read the snapshot if present, and then
   execute the transactions recorded in the log after the snapshot was made.
   
   To make this working, all these functions have =database= as the first
   parameter, and all other parameters must be serializable.

   The functions must be ready to receive arguments deserialized from log/snapshot,
   therefore we typically want to pass some string/numeric IDs as arguments,
   not whole object references. For example =add-order= accepts user ID as
   the parameter, but not a =user= object. Othersize we might end up
   dealing with many copies of the same =user= object, duplicated by
   deserialization.
   
   In contrast to cl-prevalence, in SPTM transaction log and snapshots
   are stored online and may be used by several processes to share data.
   
   For example cl-test-grid agents on different machines collect test
   results and publish them by recording =add-test-run= transaction
   to the online log. Then cl-test-grid admin executes all these transactions
   on his machine and so receives the data collected.
     
*** Concurrency Control

   In cl-prevalence transactions in different application threads
   may be serialized using global lock.
   
   But in SPTM the transactions are executed in different processes
   runing on different machines over Internet. How to synchronize them?
   
   Here we use ideas from optimistic concurrency approach in Clojure
   software transactional memory.

   It has similarities with Prevalence - the data modifications are expressed as
   functions with parameters. But the functions are pure: they
   compute new version of data, instead of modifying the data destructively;
   also the functions do not perform any IO.

   After the function has computed new version of data, an attempt to
   commit the transaction is performed (in Clojure this means storing
   new data value in Ref; in SPTM this means adding transaction record
   to the transaction log).

   If during the commit attempt it is determined that another transaction(s)
   has commited since our transaction has started, the value computed by
   the function is rejected, the data is updated to reflect the changes
   made by concurrent (remote in case of SPTM) transactions,
   and our transaction is restarted again.

   This protocol guarantees that everyone replaying the transaction log
   executes the functions on exactly the same data as the process
   which recorded this transaction to the log.

** Security
   So, we retrieve function names from transaction log and call these functions.

   If the log is writable by untrasted parties, we can protect ourselves with
   a =transaction-checker= - a predicate on the function name. SPTM API
   accepts such a predicate as a parameter and uses it to verifies that
   transactions use only allowed functions before executing the transactions.

** Example
   [[./example.lisp]]
   <commit_msg>Improve wording in sptm/README.org<commit_after>* SPTM - Shared Persistent Transactional Memory
  Simple online storage for lisp data, using the ideas of in-memory 
  persistence and optimistic concurrency control.

  Operates via transaction log stored on Amazon Web Services (S3 and SimpleDB).

** Informal Description of the Ideas
*** In-Memory Persistence
   This idea is also known as Prevalence and there is a Common Lisp
   library [[http://common-lisp.net/project/cl-prevalence/][cl-prevalence]].
   
   All perstent data modifications are expressed as named functions
   with parameters. For example
   
#+BEGIN_SRC common-lisp
   (add-user database :id 1 :name "anton")
   (add-order database id: 117 :user 1 :book "AIMA" :count 1)
   (delete-user database :id 1)
#+END_SRC
   Here =database= is some datastructure where you store the information,
   and =add-user=, =add-order=, =delete-user= are your functions which
   modify the database.
   
   To make the modifications persistent they are executed in transactions
#+BEGIN_SRC common-lisp
   (execute-transaction database 'add-user (list :id 1 :name "anton"))
   (execute-transaction database 'add-order (list id: 117 :user 1 :book "AIMA" :count 1))
   (execute-transaction database 'delete-user (list database :id 1))
#+END_SRC
   
   The =execute-transaction= first applies the specified function to arguments,
   thus modifying the database, and then records the function name and all the arguments,
   except for the =database= argument, to a transaction log. In cl-prevalence
   transaction log is a file on local file system.
   
   When application process is restarted after a crash or normal termination,
   it reads the transaction log and executes the functions specified here.
   In result all the the database modifications are repeated, so the
   application sees it's in-memory database persistent across restarts.
   
   Besides the transaction log, a complete snapshot of database can be stored.
   Therefore the full procedure of restoring the in-memory database state
   when application is restarted is to read the snapshot if present, and then
   execute the transactions recorded in the log after the snapshot was made.
   
   To make this working, all these functions have =database= as the first
   parameter, and all other parameters must be serializable.

   The functions must be ready to receive arguments deserialized from log/snapshot,
   therefore we typically want to pass some string/numeric IDs as arguments,
   not whole object references. For example =add-order= accepts user ID as
   the parameter, but not a =user= object. Otherwize we might end up
   dealing with many copies of the same =user= object, duplicated by
   deserialization.
   
   In contrast to cl-prevalence, in SPTM the transaction log and snapshots
   are stored online and may be used by several processes to share data.
   
   For example cl-test-grid agents on different machines collect test
   results and publish them by recording =add-test-run= transaction
   to the online log. Then cl-test-grid admin executes all these transactions
   on his machine and so receives the data collected.
     
*** Concurrency Control

   In cl-prevalence transactions in different application threads
   may be serialized using global lock.
   
   But in SPTM the transactions are executed in different processes
   runing on different machines over Internet. How to synchronize them?
   
   Here we use ideas from optimistic concurrency approach in Clojure's
   software transactional memory.

   It has similarities with Prevalence - the data modifications are expressed as
   functions with parameters. But the functions are pure: they
   compute new version of data, instead of modifying the data destructively;
   also the functions do not perform any IO.

   After the function has computed new version of data, an attempt to
   commit the transaction is performed (in Clojure this means storing
   new data value in Ref; in SPTM this means adding transaction record
   to the transaction log).

   If during the commit attempt it is determined that another transaction(s)
   has commited since our transaction has started, the value computed by
   the function is rejected, the data is updated to reflect the changes
   made by concurrent (remote in case of SPTM) transactions,
   and our transaction is restarted again.

   This protocol guarantees that everyone replaying the transaction log
   executes the functions on exactly the same data as the process
   which recorded this transaction to the log.

** Security
   So, we retrieve function names from transaction log and call these functions.

   If the log is writable by untrasted parties, we can protect ourselves with
   a =transaction-checker= - a predicate on the function name. SPTM API
   accepts such a predicate as a parameter and uses it to verify that
   transactions refer only allowed functions before executing the transactions.

** Example
   [[./example.lisp]]
   
{'fraction_non_alphanumeric': 0.0437306114279996, 'fraction_numerical': 0.003002101471029721, 'mean_word_length': 3.784107228338918, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1149869', 'n_tokens_mistral': 2489, 'n_tokens_neox': 2387, 'n_words': 1368}