Documentation Source Text

Check-in [ca6db0c14f]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add text describing file locking and the database header cookies (file and schema versions) to fileformat.html.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:ca6db0c14fe8a4a96f971f572519e03351bc68f5
User & Date: dan 2009-05-01 10:45:51
Context
2009-05-05
18:23
Website updates in preparation for the 3.6.14 release. check-in: e3715164fb user: drh tags: trunk
2009-05-01
10:45
Add text describing file locking and the database header cookies (file and schema versions) to fileformat.html. check-in: ca6db0c14f user: dan tags: trunk
2009-04-30
16:00
Update the DELETE documentation to discuss the truncation optimization. check-in: dcd3325dd3 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/fileformat.in.

78
79
80
81
82
83
84
85




86


87
88
89
90

91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
...
422
423
424
425
426
427
428

429
430
431
432
433
434
435
....
2717
2718
2719
2720
2721
2722
2723































2724
2725
2726
2727









2728


































2729















2730
2731
2732
2733





2734















2735
2736

2737
2738
2739
2740
2741
2742
2743












2744





















































2745
2746
2747

2748
2749
2750
2751
2752
2753
2754
      <center>
      <a name="$zName"></a>
      <img src="images/fileformat/$zImage">
      <p><i>Figure $::SectionNumbers(fig) - $zCaption</i>
      </center>
  }
}





proc FixReferences {body} {


  foreach {term anchor} $::Glossary {
    set re [string map {" " [-[:space:]]+} $term]
    set re "${re}s?"
    set body [regsub -all -nocase $re $body "<a class=defnlink href=\"#$anchor\">\\0</a>"]

  }

  foreach {key value} [array get ::References] {
    foreach {zNumber zTitle} $value {}
    lappend l <cite>$key</cite> "<cite><a href=\"#$key\" title=\"$zTitle\">$zNumber</a></cite>"
  }
  set body [string map $l $body]
}

set ::Glossary {}
proc Glossary {term definition} {
  set anchor [string map {" " _ ' _} $term]
  set anchor "glossary_$anchor"
  lappend ::Glossary $term $anchor

  return "<tr><td class=defn><a name=\"$anchor\"></a>$term <td>$definition"
}

proc Table {} {
  set ::Stripe 1
  return "<table class=striped>"
................................................................................
      [Glossary "Page size" {<span class=todo>This.</span>}]
      [Glossary "Sector size" {<span class=todo>This.</span>}]

      [Glossary "Journal Section" {<span class=todo>This.</span>}]
      [Glossary "Journal Header" {<span class=todo>This.</span>}]
      [Glossary "Journal Record" {<span class=todo>This.</span>}]
      [Glossary "Master Journal Pointer" {<span class=todo>This.</span>}]


    </table>

<!--
h1 "SQLite Database Files" sqlite_database_files
 
  <p>
................................................................................
      forward journal or "transaction log". This section does not 
      contain requirements. It is only here to make the point that
      alternatives to the rollback journal method exist.


[h1 "SQLite Interoperabilty Requirements" interoperability_requirements]
































  [h2 "SQLite Locking Protocol" locking_protocol]

    <p>
      Basic rules:












































    [fileformat_import_requirement2 H33000]















    [fileformat_import_requirement2 H33020]

    <p>
      Special requirement for RESERVED locks:





















    [fileformat_import_requirement2 H33010]
    [fileformat_import_requirement2 H33030]

  

  [h2 "SQLite Database Header Cookie Protocol" database_header_cookies_protocol]

  <p class=todo>
    The following need to take into account (a) integer overflow and (b)
    exclusive-locking mode.


































































    [fileformat_import_requirement2 H33040]
    [fileformat_import_requirement2 H33050]




[h1 References]

  <table id="refs" style="width:auto; margin: 1em 5ex">
    <tr><td style="width:5ex" id="ref_comer_btree">\[1\]<td>
     Douglas Comer, <u>Ubiquitous B-Tree</u>, ACM Computing Surveys (CSUR),








>
>
>
>

>
>
|



>













|







 







>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



<
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



|
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
>
|
<


<
<
<
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


<
>







78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
...
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
....
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765

2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854

2855
2856



2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924

2925
2926
2927
2928
2929
2930
2931
2932
      <center>
      <a name="$zName"></a>
      <img src="images/fileformat/$zImage">
      <p><i>Figure $::SectionNumbers(fig) - $zCaption</i>
      </center>
  }
}

proc sort_by_length {lhs rhs} {
  return [expr [string length $lhs] - [string length $rhs]]
}

proc FixReferences {body} {
  foreach E [lsort -decr -index 1 -command sort_by_length $::Glossary] {
  puts $E
    foreach {term anchor} $E {}
    set re [string map {" " [-[:space:]]+} $term]
    set re "${re}s?"
    set body [regsub -all -nocase $re $body "<a class=defnlink href=\"#$anchor\">\\0</a>"]
    # set body [regsub -all -nocase {(defnlink[^<]*) } $body "\\1&20;"]
  }

  foreach {key value} [array get ::References] {
    foreach {zNumber zTitle} $value {}
    lappend l <cite>$key</cite> "<cite><a href=\"#$key\" title=\"$zTitle\">$zNumber</a></cite>"
  }
  set body [string map $l $body]
}

set ::Glossary {}
proc Glossary {term definition} {
  set anchor [string map {" " _ ' _} $term]
  set anchor "glossary_$anchor"
  lappend ::Glossary [list $term $anchor]

  return "<tr><td class=defn><a name=\"$anchor\"></a>$term <td>$definition"
}

proc Table {} {
  set ::Stripe 1
  return "<table class=striped>"
................................................................................
      [Glossary "Page size" {<span class=todo>This.</span>}]
      [Glossary "Sector size" {<span class=todo>This.</span>}]

      [Glossary "Journal Section" {<span class=todo>This.</span>}]
      [Glossary "Journal Header" {<span class=todo>This.</span>}]
      [Glossary "Journal Record" {<span class=todo>This.</span>}]
      [Glossary "Master Journal Pointer" {<span class=todo>This.</span>}]
      [Glossary "Database File-System Representation" {<span class=todo>This.</span>}]

    </table>

<!--
h1 "SQLite Database Files" sqlite_database_files
 
  <p>
................................................................................
      forward journal or "transaction log". This section does not 
      contain requirements. It is only here to make the point that
      alternatives to the rollback journal method exist.


[h1 "SQLite Interoperabilty Requirements" interoperability_requirements]

  <p>
    This section contains requirements that further constrains the behaviour
    of software that accesses (reads and/or writes) SQLite databases stored
    within the file-system. These requirements need only be implemented by
    systems that access databases while other clients may also be doing so.
    More specifically, they need only be implemented by software operating
    within a system where one or more of the database clients writes to the
    database. If the database file-system representation remains constant
    at all times, or if there is only ever a single database client for each
    database within the system, the requirements in this section can be 
    ignored.

  <p>
    The requirements in this section fall into two categories:

  <ul>
    <li> <p><b>Locking Requirements</b>. Section <cite>locking_protocol</cite>
         contains a description of the file-system locks that must be obtained
         on the database file, and how locks placed by other database clients 
         should be interpreted.

    <li> <p><b>Header Cookie Requirements</b>. An SQLite database image header 
         (see section <cite>file_header</cite>) contains two "cookie" values
         that must sometimes be incremented when the database image stored in
         the file-system is updated. Section 
         <cite>database_header_cookies_protocol</cite> contains requirements
         identifying exactly when the cookie values must be incremented, and
         how they can be used by a database client to determine if cached
         data is valid or not.
  </ul> 

  [h2 "SQLite Locking Protocol" locking_protocol]

    <p>

      An SQLite database client may hold at any time one of four different types 
      of locks on a database file-system representation. This document does not
      describe how these locks are to be implemented. Possible implementation
      techniques include mapping the four SQLite locks to operating system file
      locks, using an external software module to manage locks, or by creating
      special "lock files" within the file-system. Regardless of how the locks
      are implemented, it is important that all database clients in a system 
      use the same implementation. The following table summarizes the four 
      types of locks used by SQLite:

    [Table]
      [Tr] <th> Lock type <th> Description <th> Blocks <th> Blocked By
      [Tr] <td> SHARED    <td> 
          It is only possible to obtain a SHARED lock if no other client is
          holding a PENDING or EXCLUSIVE lock. Holding a SHARED lock prevents
          any other client from obtaining an EXCLUSIVE lock.
          <td> EXCLUSIVE <td> PENDING, EXCLUSIVE

      [Tr] <td> RESERVED  <td> 
          A RESERVED lock may only be obtained if no other client holds a 
          RESERVED, PENDING or EXCLUSIVE lock on the database. While a
          client holds a RESERVED lock, other clients may obtain new SHARED
          locks, but may not obtain new RESERVED, PENDING or EXCLUSIVE locks.
          <td> RESERVED, PENDING, EXCLUSIVE <td> RESERVED, PENDING, EXCLUSIVE

      [Tr] <td> PENDING <td>
          It is only possible to obtain a PENDING lock if no other client holds
          a RESERVED, PENDING or EXCLUSIVE lock. While a database client is 
          holding a PENDING lock, no other client may obtain any new lock. 
          <td> All <td> RESERVED, PENDING, EXCLUSIVE

      [Tr] <td> EXCLUSIVE <td>
          An EXCLUSIVE lock may only be obtained if no other client holds any
          lock on the database. While an EXCLUSIVE lock is held, no other 
          client may obtain any kind of lock on the database.
          <td> All <td> All

    </table>
      
    <p>
      The most important types of locks are SHARED and EXCLUSIVE. Before any 
      part of the database file is read, a database client must obtain a SHARED 
      lock or greater.

    [fileformat_import_requirement2 H33000]

    <p>
      Before the database file may be written to, a database client must
      be holding an EXCLUSIVE lock. Because holding an EXCLUSIVE lock 
      guarantees that no other client is holding a SHARED lock, it also
      guarantees that no other client may be reading from the database file
      as it is being written.

    [fileformat_import_requirement2 H33010]

    <p>
      The two requirements above govern reading from and writing to the
      database file. In order to write to a journal file, a database client
      must obtain at least a RESERVED lock.

    [fileformat_import_requirement2 H33020]

    <p>
      The requirement above implies that a database writer may write to the
      journal file at the same time as a reader is reading from the database
      file. This improves concurrency in environments that feature multiple
      clients, as a database writer may perform part of its IO before locking
      the database file-system representation with an EXCLUSIVE lock. In order
      for this to work though, the following must be true:

    <ul>
      <li> <p>Database readers must recognize that when a writer holds a RESERVED 
           or PENDING lock on the database file-system representation the
           writer may be manipulating the journal file and as a result it is
           not safe to read.

      <li> <p>Database writers may only obtain a RESERVED or PENDING lock on the
           database file-system representation when it would be safe for a
           database reader to assume that the contents of the database file
           represents the current database image.
    </ul>

    <p>
      The following requirements formally restate the above bullet points.

    [fileformat_import_requirement2 H33030]
    [fileformat_import_requirement2 H33060]
    [fileformat_import_requirement2 H33080]


  [h2 "SQLite Database Header Cookie Protocol" database_header_cookies_protocol]




    <p>
      While a database reader is holding a SHARED lock on the database
      file-system representation, it may freely cache data in main memory
      since there is no way that another client can modify the database
      image. However, if a client relinquishes all locks on a database
      file-system representation and then re-establishes a SHARED lock
      at some point in the future, any cached data may or may not be
      valid (as the database image may have been modified while the client
      was not holding a lock). The requirements in this section dictate
      the way in which database writers must update two fields of the database
      image header (the "cookies") in order to enable readers to determine
      when cached data can be safely reused and when it must be discarded.

    <p>
      SQLite clients may cache two types of data from a database image in
      main-memory:

    <ul>
      <li> <p>The <b>database schema</b>. In order to access database content,
           the contents of the schema table must be parsed (see section 
           <cite>schema_table</cite>). Since this is a relatively expensive
           process, it is advantageous for clients to cache the parsed 
           representation in memory.

      <li> <p>Database image <b>page content</b>. Clients may also cache raw
           page content in order to reduce the number of file-system read 
           operations required when reading the database image.
    </ul>

    <p>
      Similar mechanisms are used to support cache validation for each class
      of data. If a database writer changes the database schema in any way, it
      is also required to increment the value stored in the database schema
      version field of the database image header (see section 
      <cite>file_header</cite>). This way, when a database reader establishes
      a SHARED lock on a database file-system representation, it may validate
      any cached schema data by checking if the value of the database schema 
      version field has changed since the data was cached. If the value has not
      changed, then the cached schema data may be retained and reused. 
      Otherwise, if the value of the database schema version field is not the
      same as it was when the schema data was last cached, then the reader
      can deduce that some other database client has modified the database
      schema in some way and it must be reparsed.

    <p>
      Each time a database image stored within a database file-system 
      representation is modified, the database writer is required to increment
      the value stored in the change counter field of the database image header
      (see section <cite>file_header</cite>). This allows database readers to
      validate any cache of raw database image page content that may be present
      when a database reader establishes a SHARED (or other) lock on the 
      database file-system representation. If the value stored in the change
      counter field of the database image has not changed since the cached
      data was read, then it may be safely reused. Otherwise, if the change
      counter value has changed, then any cached page content data must be
      deemed untrustworthy and discarded.

    <p>
      If a database image is modified more than once while a writer is holding
      an EXCLUSIVE lock, then each header value need only be updated once, as
      part of the first image modification that modifies the associated class
      of data. Specifically, the change counter field need only be incremented
      as part of the first image modification that takes place, and the 
      database schema version need only be incremented as part of the first
      modification that includes a schema change. 

    [fileformat_import_requirement2 H33040]
    [fileformat_import_requirement2 H33050]

    [fileformat_import_requirement2 H33070]


[h1 References]

  <table id="refs" style="width:auto; margin: 1em 5ex">
    <tr><td style="width:5ex" id="ref_comer_btree">\[1\]<td>
     Douglas Comer, <u>Ubiquitous B-Tree</u>, ACM Computing Surveys (CSUR),

Changes to req/hlr30000.txt.

861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
....
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096

1097
1098
1099

1100
1101
1102
1103
1104
1105




1106






1107
1108
1109
1110



1111
1112
1113
1114
1115
1116



1117






1118


HLR H32010
If the first 28 bytes of a <i>journal file</i> do not contain a well-formed
<i>journal header</i>, then the <i>journal file</i> shall be considered
invalid.

HLR H32020
If the journal file exists within the file-system and neither H32000 nor 
H32010 apply, then the journal file shall be considered valid.



HLR H32030
If there exists a valid <i>journal file</i> in the file-system, then the
database <i>page-size</i> in bytes used to interpret the <i>database image</i>
shall be the value stored as a 4-byte big-endian unsigned integer at byte
................................................................................
file has been truncated the journal records corresponding to pages from the
original database image that were part of the truncated region and were not
free-list leaf pages are not modified or made unstable.



HLR H33000
Before reading from a database file or journal file, a database
reader shall establish a SHARED or greater lock on the database file.

HLR H33010
Before writing to a journal file, a database writer shall establish
a RESERVED or greater lock on the database file.


HLR H33020
Before writing to a database file, a database writer shall establish
an EXCLUSIVE lock on the database file.


HLR H33030
Before establishing a RESERVED or PENDING lock on a database file, a 
database writer shall ensure that the database file contains a valid 
database image.












HLR H33040
When updating a database image stored within a file-system, a database writer
shall ensure that the database header change-counter field in the updated
database image is larger than the same value in the original database image.




HLR H33050
When updating a database image stored within a file-system such that the
contents of the schema table is changed, a database writer shall ensure that
the database header schema-cookie field in the updated database image is larger
than the same value in the original database image.



















|
|







 







|
|


|
|

>

|
|
>






>
>
>
>

>
>
>
>
>
>

<
<
<
>
>
>


<
<
<
<
>
>
>

>
>
>
>
>
>

>
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
....
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119



1120
1121
1122
1123
1124




1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136

HLR H32010
If the first 28 bytes of a <i>journal file</i> do not contain a well-formed
<i>journal header</i>, then the <i>journal file</i> shall be considered
invalid.

HLR H32020
If the journal file exists within the file-system and neither H32000 
, H32010 nor H33080 apply, then the journal file shall be considered valid.



HLR H32030
If there exists a valid <i>journal file</i> in the file-system, then the
database <i>page-size</i> in bytes used to interpret the <i>database image</i>
shall be the value stored as a 4-byte big-endian unsigned integer at byte
................................................................................
file has been truncated the journal records corresponding to pages from the
original database image that were part of the truncated region and were not
free-list leaf pages are not modified or made unstable.



HLR H33000
Before reading from a database file , a database reader shall establish a 
SHARED or greater lock on the database file-system representation.

HLR H33010
Before writing to a database file, a database writer shall establish
an EXCLUSIVE lock on the database file-system representation.


HLR H33020
Before writing to a journal file, a database writer shall establish
a RESERVED, PENDING or EXCLUSIVE lock on the database file-system
representation.

HLR H33030
Before establishing a RESERVED or PENDING lock on a database file, a 
database writer shall ensure that the database file contains a valid 
database image.

HLR H33060
Before establishing a RESERVED or PENDING lock on a database file, a 
database writer shall ensure that any journal file that may be present
is not a valid journal file.

HLR H33080
If another database client holds either a RESERVED or PENDING lock on the
database file-system representation, then any journal file that exists within
the file system shall be considered invalid.


HLR H33040



A database writer shall increment the value of the database header change
counter field (H30100) either as part of the first database image modification 
that it performs after obtaining an EXCLUSIVE lock.

HLR H33050




A database writer shall increment the value of the database schema version 
field (H30110) as part of the first database image modification that includes
a schema change that it performs after obtaining an EXCLUSIVE lock.

HLR H33070
If a database writer is required by either H33050 or H33040 to increment a
database header field, and that header field already contains the maximum
value possible (0xFFFFFFFF, or 4294967295 for 32-bit unsigned integer 
fields), "incrementing" the field shall be interpreted to mean setting it to 
zero.