Sqlite Internal

table interior page 是用来保存 sqlite 表数据的 B+-tree 中间节点. 其 cell 的格式为:

[子 page 索引] [记录号]

其中第一个字段是 page 号, 第二个字段是记录号, 所谓记录号, 就是 sqlite 表中对应于每条记录的唯一标识 (rowid)

因为 table interior page 是 B+-tree 中间节点, 所以它们只保存着索引信息 (记录号和子节点 page 号),不包含 cell 对应的记录的详细信息.

另外, sqlite 的 B-tree 或 B+-tree 并不是严格的 x 阶 B 树, 因为它每个节点可以包含的子节点个数是不定的, 由 cell 的大小决定, 例如, table interior page 中每个 cell 可能只占几个字节, 1K 的 page 除去 page 头和其它一些开销可能可以保存上百个 cell.

table leaf page 是用来保存表数据的 B+-tree 叶节点, 其 cell 格式为: [cell payload 大小][记录号][payload 内容][overflow page 索引]

其中 payload 内容 保存着一个 record 的实际的数据. 若一个 record 的内容过多, 则会分配一个 overflow page 来保存过多的内容. 但要注意的是并不是 record 大小超过 page_size 时才使用 overflow page, 实际上, sqlite 定义了一个常量, 使得 record 大小 page_size 的 1/4 时就会使用 overflow page, 并且只有 7/8 的内容会放在 overflow page 里, 剩下的 1/8 内容放在 cell payload 中.

index interior page 用来保存 sqlite 索引的 B-tree 中间节点, 其 cell 格式为:

[子 page 索引] [索引使用的 key] [索引记录本身]

这里与 table interior page 的区别主要有两点:

1. table interior page 使用记录号有标识 cell 本身的 key, 而 index interior page 使用的是建立索引时使用 key 字段, 例如:

   create index test_index on test(name), 则对于 test_index 的 interior page, key 就是 name 字段的值

2. index interior page 的 cell 中还保存着 cell 本身对应索引记录本身, 因为 index interior page 是 B-tree 中间节点. 这样设计也是由 index 的工作原理决定的.

index leaf page 是 B-tree 叶节点, 和 table leaf page 基本相同, 只是 B-tree 中间节点不包含在 B-tree 叶节点中.

查询 1600 W 条记录所耗的时间的比较

可见,

• 不使用多线程的情况下, SINGLETHREAD 和 MULTITHREAD 差不多,SERIALZIED 变慢
• 使用多线程的情况下,
  • SINGLETHREAD 无法使用
  • MULTITHREAD 可以利用多线程显著的降低 real time
  • SERIALZIED 使用不同的线程时也比 MULTITHREAD 稍慢
  • SERIALZIED 使用相同的线程时速度无法接受

综上, 使用 MULTITHREAD 多线程使用不同的 connection 是最好的选择.

Use the SQLITE_THREADSAFE compile-time parameter to selected the threading mode. If no SQLITE_THREADSAFE compile-time parameter is present, then serialized mode is used. This can be made explicit with -DSQLITE_THREADSAFE=1. With -DSQLITE_THREADSAFE=0 the threading mode is single-thread. With -DSQLITE_THREADSAFE=2 the threading mode is multi-thread.

The return value of the sqlite3_threadsafe() interface is determined by the compile-time threading mode selection. If single-thread mode is selected at compile-time, then sqlite3_threadsafe() returns false. If either the multi-thread or serialized modes are selected, then sqlite3_threadsafe() returns true. The sqlite3_threadsafe() interface predates the multi-thread mode and start-time and run-time mode selection and so is unable to distinguish between multi-thread and serialized mode nor is it able to report start-time or run-time mode changes.

If single-thread mode is selected at compile-time, then critical mutexing logic is omitted from the build and it is impossible to enable either multi-thread or serialized modes at start-time or run-time.

Assuming that the compile-time threading mode is not single-thread, then the threading mode can be changed during initialization using the sqlite3_config() interface. The SQLITE_CONFIG_SINGLETHREAD verb puts SQLite into single-thread mode, the SQLITE_CONFIG_MULTITHREAD verb sets multi-thread mode, and the SQLITE_CONFIG_SERIALIZED verb sets serialized mode.

If single-thread mode has not been selected at compile-time or start-time, then individual database connections can be created as either multi-thread or serialized. It is not possible to downgrade an individual database connection to single-thread mode. Nor is it possible to escalate an individual database connection if the compile-time or start-time mode is single-thread.

The threading mode for an individual database connection is determined by flags given as the third argument to sqlite3_open_v2(). The SQLITE_OPEN_NOMUTEX flag causes the database connection to be in the multi-thread mode and the SQLITE_OPEN_FULLMUTEX flag causes the connection to be in serialized mode. If neither flag is specified or if sqlite3_open() or sqlite3_open16() are used instead of sqlite3_open_v2(), then the default mode determined by the compile-time and start-time settings is used.

这里的 lock 是指数据库级别的文件锁, 这个锁是一个建议性锁 (advisory lock), 实际上, 为了实现这种多状态的锁, sqlite 针对 sqlite db 文件的三块区域(从 PENDING_BYTE 开始的 1+1+510=512 个字节)定义了三个读写锁, 通过对不同的区域的锁定实现不同的状态.

PENDING_BYTE 目前定义为 0x40000000 (1G) 处, 需要注意的是 fcntl 对文件区域加锁时并不需要文件真的有那么大, 所以即时一个很小不到 1G 的数据库文件,也可以对 1G 处的"内容"进行锁定 … 之所以设置 PENDING_BYTE 为 1G, 就是因为当数据库文件小于 1G 时可以节省这 512 字节, 因为 windows 只支持强制性文件锁, 为了避免 sqlite 读写这 512 字节的内容时因为强制锁出错, sqlite 要求这 512 字节的空间不允许存储任何数据.

当数据库文件大于 1G 时, 这 512 的字节被称为 lock-byte page.

#+BEGIN_EXAMPLE r -------------------------------------

---- w ---+ w | -----------------v----- |

---+ ---- | -------------------—+ | rese|rved pending | shared | | ^ (starting) ----------------------------–—+ --------------------------------------------------- #+END_EXAMPLE w

• pending
• unlocked
• shared

执行任何语句前要进行 shared 状态

• reserved 执行任何写语句前需要首先进入 reserved 状态

  shared 想升级为 reserved, 必须保证当前没有任何 reserved 及 exclusive lock

• exclusive

  • pending

    commit 前需要进行 pending 状态

    reserved 升级为 exclusive 时会先暂时的升级为 pending, pending lock 会禁止任何新的 lock 的获取, 包括 shared, 否则可以会因为不停的有新的 shared lock 进入而导致 reserved 永远无法升级为 exclusive.

  reserved 要想升级为 exclusive, 必须保证当前没有任何其他的 lock, 包含 shared

android framework 中采用了 ONE primary connection + N non-primary connections 的 connection pool 方案, 可能也是考虑到了这种死锁:

primary connection 用于"可能"需要写操作的 transaction, 只有一个. 而 non-primary connection 是用于读操作的 transaction, 可以有 N 个. 但这种做法仍然无法避免多个进程同时对同一个数据库写时的死锁, 如果要避免,可能需要要求所有写操作的 transaction 都以 begin reversed 开始.

若程序中发生了这种死锁, sqlite 只能保证对相应的 statement 如 "insert inot foo values ('bar')" 返回 SQLITE3_BUSY, 应用应自己保证此时将 transaction rollback, 而不是不断的去重试该语句.

另外, sqlite 本身有对于这个死锁的检测能力, 所以这时 sqlite 可能不会调用任何 busy handler 而是直接向上层返回 busy. 所以上层应用不应过多依赖 busy handler 来处理 busy 状况.

• begin [deferred]
• begin immediate
• begin exclusive

http://www.sqlite.org/faq.html#q5

Multiple processes can have the same database open at the same time. Multiple processes can be doing a SELECT at the same time. But only one process can be making changes to the database at any moment in time, however.

SQLite uses reader/writer locks to control access to the database. (Under Win95/98/ME which lacks support for reader/writer locks, a probabilistic simulation is used instead.) But use caution: this locking mechanism might not work correctly if the database file is kept on an NFS filesystem. This is because fcntl() file locking is broken on many NFS implementations. You should avoid putting SQLite database files on NFS if multiple processes might try to access the file at the same time. On Windows, Microsoft's documentation says that locking may not work under FAT filesystems if you are not running the Share.exe daemon. People who have a lot of experience with Windows tell me that file locking of network files is very buggy and is not dependable. If what they say is true, sharing an SQLite database between two or more Windows machines might cause unexpected problems.

We are aware of no other embedded SQL database engine that supports as much concurrency as SQLite. SQLite allows multiple processes to have the database file open at once, and for multiple processes to read the database at once. When any process wants to write, it must lock the entire database file for the duration of its update. But that normally only takes a few milliseconds. Other processes just wait on the writer to finish then continue about their business. Other embedded SQL database engines typically only allow a single process to connect to the database at once.

However, client/server database engines (such as PostgreSQL, MySQL, or Oracle) usually support a higher level of concurrency and allow multiple processes to be writing to the same database at the same time. This is possible in a client/server database because there is always a single well-controlled server process available to coordinate access. If your application has a need for a lot of concurrency, then you should consider using a client/server database. But experience suggests that most applications need much less concurrency than their designers imagine.

When SQLite tries to access a file that is locked by another process, the default behavior is to return SQLITE_BUSY. You can adjust this behavior from C code using the sqlite3_busy_handler() or sqlite3_busy_timeout() API functions.

http://www.sqlite.org/faq.html#q6

Threads are evil. Avoid them.

SQLite is threadsafe. We make this concession since many users choose to ignore the advice given in the previous paragraph. But in order to be thread-safe, SQLite must be compiled with the SQLITE_THREADSAFE preprocessor macro set to 1. Both the Windows and Linux precompiled binaries in the distribution are compiled this way. If you are unsure if the SQLite library you are linking against is compiled to be threadsafe you can call the sqlite3_threadsafe() interface to find out.

Prior to version 3.3.1, an sqlite3 structure could only be used in the same thread that called sqlite3_open() to create it. You could not open a database in one thread then pass the handle off to another thread for it to use. This was due to limitations (bugs?) in many common threading implementations such as on RedHat9. Specifically, an fcntl() lock created by one thread cannot be removed or modified by a different thread on the troublesome systems. And since SQLite uses fcntl() locks heavily for concurrency control, serious problems arose if you start moving database connections across threads.

The restriction on moving database connections across threads was relaxed somewhat in version 3.3.1. With that and subsequent versions, it is safe to move a connection handle across threads as long as the connection is not holding any fcntl() locks. You can safely assume that no locks are being held if no transaction is pending and all statements have been finalized.

Under Unix, you should not carry an open SQLite database across a fork() system call into the child process. Problems will result if you do.