Project 1: OwlDB

For this project you will build a network accessible NoSQL document database using the Go programming language. Your database will be a RESTful web service that you access using the HTTP protocol. The database stores JSON documents that can be created, modified, retrieved, watched, and deleted.

Throughout this document, if you see the word must then that means this is a requirement of the project. If you see the word should, then that means that you *should* follow the given advice, but it is not strictly required.

Note that this document describes the requirements of the project. By default everything is a requirement (whether you see the word "must" or not), unless specified otherwise (using "should" or some other clear statement). The word "must" is used to emphasize particularly important requirements and/or constraints.

Table of Contents

1. Persistence 2. Document Structure 3. Database Organization 4. HTTP Methods 5. Authentication/Authorization 6. Subscribing to Changes 7. Atomic Transactions 8. API Specification 9. Command Line Interface 10. Logging 11. Constraints 12. Concurrency

Persistence

Any database must persistently store its contents. This requires data to ultimately be stored on disk. For this project, your database is *not* required to be persistent. Data can be stored in memory and all data can be lost when the system terminates. There are many ways in which the system could be extended to provide persistence. Such extensions would not require a complete redesign of the system.

Document Structure

You are building a document database, which means your NoSQL database will store *documents*. A document stored in the database is a [JSON](https://www.json.org/json-en.html) value encoded in UTF-8. The database must store each document's contents as a sequence of bytes (type []byte in Go).

The database must also impose a structure that the documents must conform to. This structure is provided as a [JSON Schema](http://json-schema.org/understanding-json-schema/). A JSON schema is a JSON object that describes the required structure of another JSON value. Whenever a document is created or modified in the system, it must be validated against the document schema. You may use the [github.com/santhosh-tekuri/jsonschema/v5](https://github.com/santhosh-tekuri/jsonschema) package to help you do so.

A JSON document is a hierarchical, recursive structure containing unknown values and types. Accessing components of that structure can be challenging and defies the type safety of statically typed languages like Go. For any operations that access, modify, or validate the contents of documents, you must first unmarshal the document's byte slice into the provided JSONValue type. You may then pass a jsonschema validator (from the above package) to the Validate method of the JSONValue type or you may access the data within the JSONValue using the visitor pattern and the provided generic Accept function. You must not access the document contents in any other way. This minimizes the type unsafe code and confines it to the Validate method and Accept function. Carefully read the documentation in the provided jsonvalue.go and visitor.go files within the jsondata package.

All documents have the following unforgeable metadata associated with them:

{
    "createdBy": "username",
    "createdAt": timestamp,
    "lastModifiedBy": "username",
    "lastModifiedAt": timestamp
}

The "createdBy" and "lastModifiedBy" fields map to a string which is the user name of the user who created and last modified the document, respectively. The "createdAt" and "lastModifiedAt" fields map to a number which is the number of milliseconds since January 1, 1970 UTC (see Go's [UnixMilli](https://pkg.go.dev/time#Time.UnixMilli) function) when the document was created and last modified, respectively. When a document is initially created, the system must create and populate this metadata structure for the document (setting the "createdBy" and "lastModifiedBy" fields both the user name of the user creating the document and setting the "createdAt" and "lastModifiedAt" to the same timestamp representing the time at which the document was created) and store it alongside the document. Whenever the document is modified, the latter two fields must be updated by the server. When the document is returned to a requester, this metadata will be returned with the document.

Note that the metadata is separate from the sequence of bytes that represent the JSON document. Therefore, you do not need to JSON encode the metadata to store it in your database. You will, however, need to do so when you return the metadata in response to an API call to retrieve the document.

A command line argument will indicate the name of a file that contains the JSON schema to which all documents in the database must conform. Note that this means you must not hard code the schema, but rather must use the provided schema. For example, this schema is the one that is used in the API documentation on Swagger. Note that this is only an *example* schema. Your database must accept any valid schema and ensure that documents conform to that schema.

Database Organization

Documents are stored in a hierarchical structure, as follows:

1. The system contains a set of zero or more top-level databases. 2. Each database contains a set of zero or more documents. 3. A document is stored as raw bytes representing a JSON value encoded in UTF-8 along with server-created metadata, as previously described. 4. A document has a set of zero or more collections associated with it. These collections are *not* part of the encoded JSON value of the document. Rather, they can be considered "children" of the document. 5. A collection contains a set of zero or more documents (as defined in 3 and 4).

Resources are identified using a *path*. Elements of a path are separated by the forward slash ("/") character. The database can be arbitrarily deep, but paths must always start with a database name, and then alternate between the names of documents and collections. If the final element of the path is a database or collection, the path must end with a trailing slash. If the final element of the path is a document, the path must not have a trailing slash at the end. A path is therefore of the form: /<database>/<document>/<collection>/<document> (note that this is just a representative example, paths can contain 0 or more document and collection elements). The shortest possible path is just a database name (i.e., /db/). Paths can be arbitrarily long.

Examples of valid paths and the resource they refer to are as follows:

1. /comp318/ : This path refers to the database named "comp318". 2. /messaging/post1 : This path refers to the document named "post1" at the top-level of the database named "messaging". 3. /comp318/group1/members/rixner : This path refers to the document named "rixner" within the collection named "members". The "members" collection is associated with the document named "group1" within the database named "comp318". 4. /db/comp318/students/ : This path refers to the collection named "students" associated with the document named "comp318" within the database named "db".

Note the following about naming:

1. All database names must be unique. 2. The document names within a single database or a single collection must be unique. There may be documents with the same name that reside in different collections or databases. 3. The collection names associated with a single document must be unique. There may be collections with the same name that are associated with different documents.

All names must be at least one character, but there is no effective limit on the length of a name. However, note that some software limits the length of URLs to roughly 2000 characters. As the path will be part of the URL for database requests, long paths could become problematic. This is not an issue you need to concern yourself with for the project. You may assume that it is the user's problem if they create a deeply nested database with long document and collection names.

Also, given that the path will be part of the request URLs, they must be properly encoded. Most software will handle this transparently for you. The only safe characters you can use in a URL are A-Z, a-z, 0-9, and the characters "\_", "-", ".", and "~". All other characters need to be "percent encoded". For example, a byte with the value of 32 (the ASCII space character) would be encoded as the three characters "%20". This is a percent sign and then two hexadecimal digits indicating the value of the byte (Hexadecimal 0x20 is equivalent to decimal 32). Again, most software handles this completely transparently, automatically encoding/decoding characters in a URL that need to be encoded.

You should test that your system properly converts names in a path that have percent encoded characters to their string equivalents (i.e., "my%20database" is stored in your database as "my database".

While in general, you would not treat %2F as a path separator in a URL, we will do so for this project. The Swagger UI encodes "/" characters in document and collection paths as %2F, so if we do not interpret %2F as a "/" character, you would not be able to test your system with Swagger. This means that the path "/a/b%2Fc/d" is the same as "/a/b/c/d", and both have the component names "a", "b", "c", and "d".

Note that in Go, if you have a Request object r you can get the path with r.URL.Path. This path will already have converted all percent encoded characters (including %2F) back to their original characters. If you want to see the original path, you should call r.URL.EscapedPath(). For example, if the original path in the URL was "/a%20/b%2Fc/d", then r.URL.Path would be "/a /b/c/d" and r.URL.EscapedPath() would return "/a%20/b%2Fc/d".

HTTP Methods

To access your database, a client will make HTTP requests using the well-understood HTTP methods:

1. GET: retrieve a resource 2. PUT: create or overwrite a resource 3. POST: create a new resource 4. PATCH: modify a resource 5. DELETE: remove a resource 6. OPTIONS: detect which methods and options are allowed

These methods each operate on a URL. The URL is of the form: "http://localhost:3318/v1/database/document/collection/". There are several components of the URL:

1. "http://": This names the protocol to be used for the request. For an HTTP RESTful service, this would be http (unencrypted) or https (encrypted). Any real service should always use encrypted HTTPS. As the setup for such encryption is beyond the scope of this course, we will use HTTP. Nothing about your system would change in any way, other than to have a registered security certificate that can be used for encryption and then all requests/responses would automatically be encrypted for you. 2. "localhost": This names the host that is running the service. The special name "localhost" means "this computer I'm running on right now". Normally this would be a domain name (such as "owldb.rice.edu"), but you will generally use localhost as you develop your system. 3. ":3318": This names the port that the service is listening to. Numbers below 1024 have well known meanings and name particular services. Web servers, for example, listen on port 80. Numbers above 1024 can be used by any service. The client needs to know what port the service is listening to in order to access the service. 4. "/v1": This is the version of the API to use. It is important to include the desired version of an API in the request to ensure compatibility with clients as the API evolves. Including the version in the URL is a common technique, though the version could alternatively be included in the request in other ways. 5. "/database/document/collection/": This is the path, as previously described, to the target resource of the request.

Some of these methods (such as PUT) require further information beyond just the method and the URL. Any such data would be JSON encoded data within the body of the request. Some methods (such as DELETE) need no further information, so would have empty bodies.

Each method returns a response. The response includes an [HTTP status code](https://developer.mozilla.org/en-US/docs/Web/HTTP/Status) indicating whether the operation was successful or not. Some methods (such as GET) would potentially also have additional information (such as the document you are getting) depending on the status code. Such information would be JSON encoded data within the body of the response.

As you are building a RESTful web service, these operations are stateless. This means that each operation is self contained and operates on the system in an isolated way. This does not mean that the operations do not modify the state of the database. They absolutely do. It does mean that the system does not keep any information about the client from request to request. The one (and only) exception to this is the authentication state of the user (discussed next).

Authentication/Authorization

Authentication is the process of verifying a user's identity and authorization is the process of determining whether or not an identified user should be allowed to perform the requested operation on a resource. Both authentication and authorization are critical components of any multi-user service. However, both authentication and authorization can be complex and have security implications for the system. Therefore, they need to be done carefully and properly.

However, authentication and authorization are not the focus of this project, so we will implement a minimalist system. Furthermore, any real authentication/authorization system would require the use of HTTPS, as there are many attacks that can be performed against unencrypted authentication/authorization flows.

Authentication

The system must have an "/auth" endpoint to perform authentication. It can be accessed using POST (login) and DELETE (logout) HTTP methods to the URL "http://localhost:3318/auth". As we are using unencrypted HTTP, we will not use passwords. You should never build a service that sends passwords over unencrypted connections. The JSON encoded body of a login request, therefore, will just include the user name as follows:

{
  "username": "rixner"
}

In a real system, you would include more information (such as a hash of the password, etc.) Your system must just log this person in with the given username. Note that this means that anyone can claim to be any user at any time. This is obviously an unacceptable design for any real system. Again, in any real system, you would need an encrypted way of exchanging and verifying credentials (such as passwords). The subsequent bearer token authorization mechanisms you will implement, however, would remain the same after you properly verified the user's identity.

To log the user in, a new, unique, randomly generated string token must be generated (such as sE4t6_oPq83dZX, for example). The token should be completely random. It should not have been seeded with information about the user. So, there should be no way for an attacker with the token to determine who it belongs to no matter how hard or long they try to do so. Nor should there be any way for them to generate a token associated with a user, even if they know all of the algorithms you are using to create tokens. (Note that in a real system, you would want to use a cryptographically secure random number generator. The common psuedo random number generators available in most languages produce sequences of random numbers that can be recreated. For the the purposes of this project, though, you may use any random number generator.)

The system must store the token and map it to the username. The system must then return the token back to the user (in a real system, this would happen over an encrypted HTTPS connection so no one could steal the token). From that point on, the token serves to identify the user and will be included with all further requests in the Authorization header of the HTTP request (note again, that in a real system these requests would be encrypted using HTTPS, so no one could steal the token):

Authorization: Bearer sE4t6_oPq83dZX

The use of "bearer" tokens in this way is a common way of performing authentication such that a user only needs to prove who they are once (with a password, for example) and then may use an unforgeable token thereafter for authorization purposes. These tokens should expire in a reasonable period of time. This limits the period of time an attacker can use the token if they steal it and forces users to log in again after long periods of inactivity to prove they are still who they were when they initially logged in. All tokens generated by your system must expire one hour after they are issued. This means that if you receive a request after the token expires, you must reject the request as Unauthorized.

If the system were to use HTTPS instead of HTTP, the only difference would be that the password (or other credential) would need to be transferred to the server and verified before creating and returning a token. The rest of the process would remain unchanged, as all of the exchanges between the client and the server would occur over an encrypted HTTPS connection, so the credentials and token would automatically be encrypted when they are in transit over the network.

Authorization

The only authorization that you need to perform is to confirm that the request includes a valid, unexpired Bearer token. Any request with a valid, unexpired Bearer token should be allowed to proceed. This means that the user has been properly authenticated. This is an "allow all authenticated users to perform all actions" authorization policy.

The only exceptions to this are login requests (POST to /auth) and all OPTIONS requests. When a user is trying to log in, they don't yet have a Bearer token, so obviously cannot include one. OPTIONS is meant to be used to discover what operations are allowed before sending an actual request (using another HTTP method). OPTIONS requests are often sent automatically by many systems without including Bearer tokens, so your system cannot require them for OPTIONS requests.

You can hopefully envision how you could add an additional authorization layer on top of this system which checks if an authenticated user has the authority to perform a particular action. For example, one way is to create a set of "security rules" that dictate which users can perform which actions on which resources. These security rules could be based simply on user names, HTTP methods, and resource paths, or they could also include information contained within documents in the database. For example, you can imagine including a "writers" field in a document that contains a list of user names. A security rule for that document could then enforce that only users in that list can modify that document. While envisioning how such security rules could be implemented is an interesting exercise, it is beyond the scope of the project. Keep in mind, however, that the core elements upon which such a system could be built will exist in your system.

Subscribing to Changes

A useful feature of a cloud database is to allow clients to "subscribe" to updates. Your system must support client subscriptions to a single document or a single collection. If a client is subscribed to a document, they must be notified if that document is modified (changed or completely overwritten) or deleted. If a client is subscribed to a collection, they must be notified if a document in the collection is modified (changed or overwritten), a document is added to the collection, or a document is removed from the collection.

This allows clients to respond to changes in real-time without having to constantly query the database to see if anything has changed. Unlike the other operations supported by the system, this requires communication between the client and server to be initiated by the server, instead of by a request from the client.

Your system must use [server sent events](https://javascript.info/server-sent-events) to communicate changes to the client. They are relatively simple to understand and use. And they have all of the capabilities needed to allow subscriptions to documents and collections. One serious limitation of server sent events is that when they are used over HTTP version 1, there is a limitation on the maximum number of connections. Using HTTP version 2, this is not an issue. For our purposes, we will ignore this problem and assume that everything will use HTTP version 2 (the Go HTTP libraries do so by default).

To use server sent events, the client needs to perform an HTTP GET operation to a server endpoint that supports server sent events with the additional query parameter "mode=subscribe". The client then keeps that connection open and the server can send events back to the client whenever it needs to. These events look like normal JavaScript events to the client and can be handled using all of the normal JavaScript event handling mechanisms. The [server sent events specification](https://html.spec.whatwg.org/multipage/server-sent-events.html) explains what your system will need to do in order to send events to the client. Basically, to send an event, you would just send the following text:

: This is a comment
event: eventname
data: this is the information in the event
data: this is a second line of information
id: 1

Events are separated by blank lines. The name of the event (after the "event:" prefix) influences how the event can be received in JavaScript. You must use the event "update" when a document is updated, modified, or created and "delete" when a document is deleted. For the event IDs, you must use the number of milliseconds since January 1, 1970 UTC (as with the metadata time stamps) when the event is sent. The event data will be described below and is the same as for "normal" (non-subscription) requests. Some servers might close the connection if no data is sent for a while. To prevent this, you should send a comment line around every 15 seconds.

A delete event should look like this:

event: delete
data: "/path/to/document-or-collection"
id: 19983438883

The data of the delete event must be quoted so that it is a valid JSON value.

An update event should look like this (where {...} is replaced with the appropriate JSON encoded objects):

event: update
data: {"path":"/path/to/document","doc":{...},"meta":{...}}
id: 199834388899

The data field is the contents of the document that was modified, replaced, or added along with its path and metadata. As with the delete event, this must be a valid JSON value.

You are *not* required to support the Last-Event-ID header. While you must send proper IDs, you do not have to replay old messages for clients who were disconnected and retry with the Last-Event-ID header. Instead, you may just ignore that header and assume it is a new request, sending the current data and all subsequent events. Note that this will break clients that rely on that header working correctly. To properly support this header, you would need to keep a history of all events and only resend those that occurred after the Last-Event-ID.

When the client subscribes to a single document, they should only receive "update" and "delete" events for that particular document. When the client subscribes to a collection, they should receive "update" and "delete" events for all documents within the collection and "delete" events for the collection itself. When a collection is deleted, you can just send a "delete" event for the collection. You do not need to send individual delete notifications for every document within the collection (though it is not incorrect to do so).

You also do not need to handle the situation where an ancestor of a subscribed resource is deleted. For example, if someone is subscribed to the document /a/b/c and then the document /a is deleted, it would make sense to notify the subscriber that /a/b/c no longer exists, but you do not have to do so.

Note also that because you are not required to support the Last-Event-ID header, you may miss some events if you put your browser tab in the background. In that case, the browser *may* close the connection and then send a new subscription request using the Last-Event-ID header when you bring the tab back into the foreground. While you test, we recommend keeping the browser tab in the foreground to avoid confusion.

Atomic Transactions

A relational database supports the notion of a *transaction*. A transaction is an atomic operation that can read, modify, and write elements within the database. Such transactions are implemented in such a way that they do not require locking the entire database. Rather they have complex mechanisms that enable the transaction to proceed and will *commit* all of the changes in one atomic operation at the end of the transaction. The transaction can commit, abort (without modifying anything in the database), or retry (if the state of the database involved in the transaction has changed since it started). Some NoSQL databases support some type of transactions, some do not.

Your system must support a limited set of atomic operations that can only operate on single documents. You must support the following two types of atomic operations:

1. A conditional write: a PUT operation to a document with the additional query parameter "mode=nooverwrite". If the mode is "nooverwrite", the PUT operation should only succeed if there is no document at the given document path. In other words, a PUT with "nooverwrite" should not overwrite an existing document. The query parameter could also be "mode=overwrite" to indicate that a document can be overwritten by this operation. If no mode is specified, PUT should default to "overwrite" mode. Effectively, the "overwrite" mode turns the PUT operation into a "create only" operation instead of a "create or update" operation. 2. A limited document update: a PATCH operation to a document atomically applies the list of patches to the document. This allows the client to make updates that are guaranteed to operate on the current state of the document. While you will only support a limited set of patch operations, one can easily imagine extending this functionality to a much larger set of operations. The supported operations are described in detail below.

These two atomic operations enable clients to safely create and update single documents. This does not provide the full power of transactions that you would find in a SQL database, but it does provide some of the most useful operations a client might need.

Patch operations are specified as a JSON array of objects in the PATCH body. Each object in the array must have the following three properites:

1. op : the value of this property specifies the patch operation and must be one of "ArrayAdd", "ArrayRemove" or "ObjectAdd". 2. path : the value of this property is a [jsonpointer](https://www.rfc-editor.org/rfc/rfc6901) that specifies the element of the JSON value to be modified. 3. value : the value of this property is the JSON value that should be added or removed.

For the "ArrayAdd" and "ArrayRemove" operations, the path is expected to refer to a JSON array element. For the "ObjectAdd" operation, the path is expected to refer to a property within a JSON object element.

If the document being patched is found, the response should always be 200 OK (whether the patch is applied successfully or not) and the response body should be a JSON object containing three properties:

1. uri : the value of this property is the full path to the document that was patched 2. patchFailed : the value of this property is a boolean value that is true if the patch failed (for any reason) or false otherwise. 3. message : the value of this property is a string providing information about why the patch failed (if it did) or the string "patch applied" if the patch was applied successfully.

If the document exists, each patch operation within the array of patches is considered to be successfully applied if the path JSON pointer refers to an element of the appropriate type. For an array operation (ArrayAdd or ArrayRemove) this means the path refers to an array. For an object operation (ObjectAdd) this means the path up to, but not including, the last element refers to an object.

For an "ArrayAdd" operation, the given value should be added to the array referred to by path if it is not already there. For an "ArrayRemove" operation, the given value should be removed from the array referred to by path if it is there. For an "ObjectAdd" operation the property that is the last element of path should be mapped to the given value in the object referred to by the path without the last element if that property does not already exist in the object. For example, an ObjectAdd operation with path "/a/b" and value "c" should map "b" to "c" in the object referred to by "/a".

The patchFailed value in the response should be true if any of the path jsonpointers in any of the patches were found to refer to non-existent elements or elements that were not of the appropriate type. Note, however, that the operations in the patch array should be applied in order. Allowing the patches to chain "Add" operations to guarantee an element is added, if it was not already there, before it is accessed. So, a subsequent patch operation in the array of patches could have a path that refers to an element that may have just been added during this patch by a previous patch operation in the array of patches.

The patchFailed value in the response should be false if all of the patches had valid path jsonpointers that referred to elements of the appropriate type (when the patch operations are applied in order). Note that even if nothing was added or removed (because they were already there/not there), the patch still succeeded, because the final state of the document is as the patch operations intended.

If any of the individual patch operations fail, the entire patch should be considered to have failed, the document should not be modified by any of the operations, patchFailed should be set to true, and message should contain an explanation of the failure..

Complete API Specification

The API can be broken down into the following categories:

Authentication

As previously described, you can login (POST) and logout (DELETE) with the /auth URL.

Database Management

You can create (PUT) and delete (DELETE) databases with URLs of the form: /v1/*database name*.

Documents

You can create (PUT, POST), modify (PATCH), and retrieve (GET) documents with URLs of the form /v1/*database name*/*document path*.

You can subscribe (GET) to a document, as well.

Collection Management

You can create (PUT) and delete (DELETE) collections with URLs of the form: /v1/*database name*/*collection path*.

Collection Queries

You can perform queries (GET) on collections with URLs of the form /v1/*database name*/*collection path*. Note that a database itself behaves as a collection, so the collection path might be empty. You can get the entire collection or you may include the interval query parameter to narrow the interval, as follows: /v1/*database name*/*collection path*?interval=[*low*,*high*]. The interval is inclusive, so this should return all documents whose names are >= *low* and <= *high*. If *low* is omitted (i.e., [,*high*]), then all documents with names are <= *high* should be returned. If *high* is omitted (i.e., [*low*,]), then all documents with names >= *low* should be returned. If both are omitted (i.e., [,]), then all documents in the collection should be returned. The determination of whether or not a name is greater than, less than, or equal to the bounds should be done using Go's ==, <, >, <=, and >= operators on strings.

You can subscribe (GET) to a collection query (with or without an interval), as well.

Detailed Description

The detailed API specification is provided below in the Swagger UI Documentation section. The Swagger interface documents all of the possible API commands, their inputs (URL, query parameters, bodies, etc.) and their responses (status codes, headers, bodies, etc.).

Command Line Arguments

Your system must support the following command line arguments:

• -p <portnum> : This argument determines the port your server will listen to. If omitted, your server must listen to port 3318.
• -s <JSON schema file name> : This argument names the file that contains the JSON schema that must be used to validate all documents stored in your database. If omitted, your server must print an error message describing the problem and terminate.
• -t <token file name> : This argument names a JSON file that contains a single JSON object mapping string user names to string tokens. These tokens must be installed in your system with an expiration time of at least 24 hours into the future (meaning that they effectively never expire, as you are unlikely to keep your server running that long continuously).

You will find the [flag package](https://pkg.go.dev/flag) helpful in implementing these arguments.

With these flags, your system can be launched as follows (we will test your system using a command such as this):

owldb -p 3318 -s document-schema.json -t testing-tokens.json

You may add whatever additional flags you would like to help you develop and test your system. For instance, you may find it helpful to have a flag that when set indicates that the database should be initialized with some well known data, to enable easier testing.

Logging

You should use structured logging throughout your application. The [slog](https://pkg.go.dev/log/slog) package provides mechanisms to easily do so. Rather than using fmt.Printf throughout your application to print information, you should use slog.Debug/Error/Info/Warn to log useful information that will allow you to more easily debug your code. By using the different logging levels, you can make it easier to print more/less information depending on what you are doing. Consider adding a command line flag to control the logging level for that run of your program. By using these levels judiciously, you can leave debug logging in your program and only turn it on when needed.

Structured logging also allows you to put key/value pairs of data into the logs. This simplifies logging and makes it easier to search. The logs can be output as plain text or as JSON. With JSON output, the logs can be processed, searched, and filtered more easily by other programs.

Constraints

The database must be written entirely in the Go programming language (version 1.23). It must correctly and completely implement the entire API described in this document, including the rudimentary authentication and authorization mechanisms. The database must also accept the command line arguments described in this document and correctly utilize those arguments.

The following four restrictions must be obeyed.

1. Packages

You may not use any packages outside of the [Go standard library](https://pkg.go.dev/std) and [github.com/santhosh-tekuri/jsonschema/v5](https://github.com/santhosh-tekuri/jsonschema). You may use any package in the Go standard library, without exception. Packages from the standard library can all be imported using their names (i.e., "fmt" or "encoding/json"). External packages require the use of a host (i.e., "golang.org/x/exp/apidiff"). Note that your own packages that are part of your application will also require the use of a host in your import statements. However, they will not appear in your go.mod file. You can therefore confirm what external packages are being used by examining your go.mod file. If any packages other than github.com/santhosh-tekuri/jsonschema/v5 are required in your go.mod file, then you are violating this restriction. When in doubt about whether a package belongs to the standard library or not, ask!

The jsonschema package should be used to validate JSON documents against a given schema (provide in a file whose name is passed to the system using the "-s" flag) to ensure that they are valid documents.

2. Indices

The indices for your collections must be implemented using a concurrent skip list. Your skip list must use lazy synchronization and atomics. It must be implemented using Go generics to allow you to use different key (cmp.Ordered) and value (any) types. Once you have such a generic skip list, you will find you can use it in other places throughout your system as well.

For example, your Skip List should conform to the following "database index" interface:

type UpdateCheck[K cmp.Ordered, V any] func(key K, currValue V, exists bool) (newValue V, err error)

type Pair[K cmp.Ordered, V any] struct {
    Key   K
    Value V
}

type DBIndex[K cmp.Ordered, V any] interface {
    Upsert(key K, check UpdateCheck[K, V]) (updated bool, err error)
    Remove(key K) (removedValue V, removed bool)
    Find(key K) (foundValue V, found bool)
    Query(ctx context.Context, start K, end K) (results []Pair[K, V], err error)
}

The "Upsert" method should either UPdate or inSERT into the SkipList. Note that it does not take a value of type V to upsert. Rather it takes a function, check, that *returns* a value of type V. This dramatically increases the utility of this method. Your "check" function will receive the key you are trying to upsert, the current value associated with that key (if any), and a boolean flag indicating whether a value exists that is associated with that key. If "exists" is false, then the current value would just be the zero value of type V. Right before doing the actual update or insert, the Upsert method should lock the node for the given key (if one was found) and then call the check function. The check function can either just return the desired value, no matter what, or can make a conditional decision on whether to return a value at all, or it can modify the current document. If the check function returns a value and no error, the Upsert method should then update or insert the node. However, if the check function returns an error, it should not update or insert the node and instead return the error returned by the check function. That enables the code calling the method to know why the value was not updated or inserted.

This structure allows for an atomic update to the SkipList. Otherwise, you would need to Find the current value in the SkipList, make a decision or modification, then potentially Update/Insert a new value. This would not be atomic, and the current value could change before the update. By having the Upsert method lock the node which the check function executes, no other goroutine can modify or remove the node during the operation.

The "Remove" and "Find" methods should be self explanatory.

The "Query" method should return all elements in the SkipList (in order) with keys between start and end inclusive. This could take a long time, so the ctx parameter can be used to indicate if/when the query should be cancelled.

Note that the name of the interface is "DBIndex", not "SkipList". This is because a skip list is only one way of implementing such indices for the database. Before you have a working skip list, you should consider building a simple type that implements "DBIndex" to use as your index. Once you have a working skip list, you can then easily just replace your initial implementation without changing any code that uses the index.

3. JSON

All access to elements of the JSON documents (such as to implement the PATCH method) stored in your system must use the visitor design pattern and the provided Accept function within the provided jsondata package. You may not add, modify, or remove anything in this package. You must use these facilities exactly as provided.

Note that the provided Accept function takes objects of type JSONValue. When you receive JSON data, you do not necessarily know its structure, so you can not store it in a typed Go variable. Instead, you should unmarshal it into a JSONValue type (you would otherwise need to use the "any" type) and operate on it with a visitor using the Accept function. The visitor pattern is ideal for accessing/processing such structured JSON data, as it allows the Accept method to determine the type of the data once with all of the possible JSON types. The visitor itself is then completely type safe and does not need to operate on data of unknown types and do type assertions or use type switches. You should not be using the any type elsewhere in your code except as a generic type constraint for containers where you do not need to access the data (such as in your SkipList).

4. Control-C

Your program must end gracefully when Control-C is pressed in the terminal that is running your program. You are provided with code that does this. You must not modify, skip, or break this code.

Concurrency

Modern software relies on concurrency and this project is no exception. You need to plan for this concurrency in your design and consider it as you implement that design. Go provides many features that help you manage concurrency and you should take advantage of them.

Go's http.ServeMux invokes the handler for each request in a new goroutine. Go provides channels, mutexes, atomics, wait groups, and other synchronization primitives. For performance critical data structures, like the SkipList, mutexes and atomics should be used. Everywhere else, goroutines and channels should be used if at all possible. While channels do not solve all concurrency issues, they are much easier to work with and build correct programs with than the lower level synchronization primitives.

The code is built and tested as follows:

go build -o owldb
./owldb <args>

Where "<args>" will be replaced by the appropriate command line arguments.

---

OwlDB API (Swagger UI Documentation)

Version 1.1, OAS 3.1

---

Authentication

POST /auth - Login request

Returns a bearer token corresponding to username in the request body. If the request body is not a JSON object with a "username" key, an error will be returned.

Parameters: No parameters

Request body: application/json

Example Value:

{
  "username": "a_user"
}

Responses:

Media type: application/json

Example Value:

{
  "token": "a88dBdX3z9kl3Q"
}

Media type: application/json

Example Value:

"No username in request body"

---

DELETE /auth - Logout request

Invalidates the bearer token in the Authorization header. If no such header exists or the bearer token contained therein is invalid, an error will be returned.

Parameters: No parameters

Responses:

Media type: application/json

Example Value:

"Missing or invalid bearer token"

---

Database Management

PUT /v1/{database} - Add a new database

Add a new database to the system with the name provided in the URL. Returns an error if the system is unable to create the database (for example, because it already exists). Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Responses:

Media type: application/json

Example Value:

{
  "uri": "/v1/my_new_database"
}

Headers:

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

---

DELETE /v1/{database} - Remove a database

Remove the database with the name provided in the URL from the system. Returns an error if the database does not exist. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Responses:

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Database does not exist"

---

Query Collections

GET /v1/{database}/ - Get all documents in the database's top-level collection

Retrieves the documents within the top-level collection of the database with the name given in the URL. If the interval query parameter is not present, or it is set to [,], then all documents in the collection will be returned. If the interval query parameter is set to an interval [low,high] only the documents with names between low and high, inclusive, will be returned. If the lower or upper bound is omitted (i.e., [low,]), that means there is no bound in the omitted direction. If the mode query parameter is set to subscribe, then this is an SSE request and all documents in the given interval will be sent as events, as will any future updates in the interval. Returns an error if the database is not found or the query parameters are malformed. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Responses:

Media type: application/json

Example Value:

[
  {
    "path": "string",
    "doc": {
      "additionalProp1": "string",
      "additionalProp2": "string",
      "additionalProp3": "string"
    },
    "meta": {
      "createdAt": 0,
      "createdBy": "string",
      "lastModifiedAt": 0,
      "lastModifiedBy": "string"
    }
  }
]

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Database does not exist"

---

GET /v1/{database}/{collectionPath}/ - Get all documents in the collection

Retrieves the documents within the collection with the collection path given in the URL. If the interval query parameter is not present, or it is set to [,], then all documents in the collection will be returned. If the interval query parameter is set to an interval [low,high] only the documents with names between low and high, inclusive, will be returned. If the lower or upper bound is omitted (i.e., [low,]), that means there is no bound in the omitted direction. If the mode query parameter is set to subscribe, then this is an SSE request and all documents in the given interval will be sent as events, as will any future updates in the interval. An error will be returned if the collection is not found or the query parameters are malformed. An error will also be returned if there is not a valid bearer token in the Authorization header.

Parameters:

Responses:

Media type: application/json

Example Value:

[
  {
    "path": "string",
    "doc": {
      "additionalProp1": "string",
      "additionalProp2": "string",
      "additionalProp3": "string"
    },
    "meta": {
      "createdAt": 0,
      "createdBy": "string",
      "lastModifiedAt": 0,
      "lastModifiedBy": "string"
    }
  }
]

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Collection does not exist"

---

Documents

POST /v1/{database}/ - Upload a document to the database's top-level collection

Stores the document in the body of the request within the top-level collection of the database given in the URL using a unique document name selected by the server. On success, returns the URI of the stored document both in the Location header and in a JSON object within the response body corresponding to the uri property. Returns an error if the database does not exist or if the request body does not conform to the document schema. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Request body: application/json

Example Value:

{
  "additionalProp1": "string",
  "additionalProp2": "string",
  "additionalProp3": "string"
}

Responses:

Media type: application/json

Example Value:

{
  "uri": "/v1/db/a27czPEcQ0l3oS"
}

Headers:

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Database does not exist"

---

GET /v1/{database}/{documentPath} - Get document

Retrieves the document with the document path given in the URL. The document is returned as JSON in the response body. If the mode query parameter is set to subscribe, then this is an SSE request and the document will be sent as an event, as will any future changes to the document. Returns an error if the document is not found or the query parameters are malformed. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Responses:

Media type: application/json

Example Value:

{
  "path": "string",
  "doc": {
    "additionalProp1": "string",
    "additionalProp2": "string",
    "additionalProp3": "string"
  },
  "meta": {
    "createdAt": 0,
    "createdBy": "string",
    "lastModifiedAt": 0,
    "lastModifiedBy": "string"
  }
}

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Document does not exist"

---

PATCH /v1/{database}/{documentPath} - Modify document

Patches the document with the document path given in the URL. The body of the request must be a valid JSON array of patches. The patches will be applied sequentially. If the document is found and the authorization is valid, the response body will be a JSON object with the properties uri, patchFailed, and message. The uri property will be associated with the document URI. The patchFailed property will be associated with false if the patch was successfully applied and true otherwise. The message property will be associated with a string providing information about the success or failure of the patch operation(s). Returns an error if the document is not found or the request body is malformed. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Request body: application/json

Example Value:

[
  {
    "op": "ArrayAdd",
    "path": "/a/b/c",
    "value": {
      "user": "another_user"
    }
  }
]

Responses:

Media type: application/json

Example Value:

{
  "uri": "/v1/db/doc",
  "patchFailed": false,
  "message": "patches applied"
}

Headers:

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Document does not exist"

---

PUT /v1/{database}/{documentPath} - Upload document

Stores the document in the body of the request at the document path given in the URL. The entire document path must already exist in the database, except perhaps the final component naming the document. If the mode query parameter is set to nooverwrite, then if the document already exists, it will not be overwritten. Otherwise, the document will be replaced if it already exists or created if it does not. On success, returns the URI of the stored document both in the Location header and in a JSON object within the response body corresponding to the uri property. Returns an error if the collection the document is to be stored in does not exist, if the request body does not conform to the document schema, or the document already exists and the mode query parameter is set to nooverwrite. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Request body: application/json

Example Value:

{
  "additionalProp1": "string",
  "additionalProp2": "string",
  "additionalProp3": "string"
}

Responses:

Media type: application/json

Example Value:

{
  "uri": "/v1/db/doc"
}

Headers:

Media type: application/json

Example Value:

{
  "uri": "/v1/db/doc"
}

Headers:

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Collection does not exist"

Media type: application/json

Example Value:

"Document already exists"

---

DELETE /v1/{database}/{documentPath} - Delete document

Removes the document with the document path in the URL from the system. Returns an error if the document is not found. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Responses:

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Document does not exist"

---

POST /v1/{database}/{collectionPath}/ - Upload a document to the collection

Stores the document in the body of the request within the collection with the collection path given in the URL using a unique document name selected by the server. On success, returns the URI of the stored document both in the Location header and in a JSON object within the response body corresponding to the uri property. Returns an error if the collection does not exist or if the request body does not conform to the document schema. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Request body: application/json

Example Value:

{
  "additionalProp1": "string",
  "additionalProp2": "string",
  "additionalProp3": "string"
}

Responses:

Media type: application/json

Example Value:

{
  "uri": "/v1/db/doc/col/UY5koZ0ns60A"
}

Headers:

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Collection does not exist"

---

Manage Collections

PUT /v1/{database}/{collectionPath}/ - Create new collection

Creates a new collection with the collection path in the URL. The entire collection path must already exist in the database except the final component naming the collection. On success, returns the URI of the new collection both in the Location header and in a JSON object within the response body corresponding to the uri property. Returns an error if the document the collection is to be created in does not exist or the collection already exists. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Responses:

Media type: application/json

Example Value:

{
  "uri": "/v1/db/doc/col/"
}

Headers:

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Document does not exist"

---

DELETE /v1/{database}/{collectionPath}/ - Delete collection

Removes the collection, and all documents contained therein, with the collection path in the URL from the system. Returns an error if the collection is not found. Also returns an error if there is not a valid bearer token in the Authorization header.

Parameters:

Responses:

Media type: application/json

Example Value:

"string"

Media type: application/json

Example Value:

"Missing or invalid bearer token"

Media type: application/json

Example Value:

"Collection does not exist"

---

Schemas

login

Schema for login requests. object

• username* string
• Additional properties: forbidden

Example:

username="a_user"

token

Bearer token. object

• token* string
• Additional properties: forbidden

Example:

token="a88dBdX3z9kl3Q"

document

Schema for documents stored in the system. object

• Additional properties: (string | number | boolean | array<string | number | boolean | object> | object)

- One of: (string | number | boolean | array<string | number | boolean | object> | object) - #0 string - #1 number - #2 boolean - #3 array<string | number | boolean | object> - Items: (string | number | boolean | object) - One of: (string | number | boolean | object) - #0 string - #1 number - #2 boolean - #3 object - Additional properties: (string | number | boolean) - One of: (string | number | boolean) - #0 string - #1 number - #2 boolean - #4 object - Additional properties: (string | number | boolean | array<string | number | boolean>) - One of: (string | number | boolean | array<string | number | boolean>) - #0 string - #1 number - #2 boolean - #3 array<string | number | boolean> - Items: (string | number | boolean) - One of: (string | number | boolean) - #0 string - #1 number - #2 boolean

pathdocmeta

Schema for API document responses. object

• path* string - Document path.
• doc* object - Schema for documents stored in the system

- Additional properties: (string | number | boolean | array<string | number | boolean | object> | object) - One of: (string | number | boolean | array<string | number | boolean | object> | object) - #0 string - #1 number - #2 boolean - #3 array<string | number | boolean | object> - Items: (string | number | boolean | object) - One of: (string | number | boolean | object) - #0 string - #1 number - #2 boolean - #3 object - Additional properties: (string | number | boolean) - One of: (string | number | boolean) - #0 string - #1 number - #2 boolean - #4 object - Additional properties: (string | number | boolean | array<string | number | boolean>) - One of: (string | number | boolean | array<string | number | boolean>) - #0 string - #1 number - #2 boolean - #3 array<string | number | boolean> - Items: (string | number | boolean) - One of: (string | number | boolean) - #0 string - #1 number - #2 boolean

• meta* object - Metadata about a document.

- createdAt* number - createdBy* string - lastModifiedAt* number - lastModifiedBy* string - Additional properties: forbidden

• Additional properties: forbidden

documents

Schema for API document collection responses. array<object>

• Items: object - Schema for API document responses.

- path* string - Document path. - doc* object - Schema for documents stored in the system - Additional properties: (string | number | boolean | array<string | number | boolean | object> | object) - One of: (string | number | boolean | array<string | number | boolean | object> | object) - #0 string - #1 number - #2 boolean - #3 array<string | number | boolean | object> - Items: (string | number | boolean | object) - One of: (string | number | boolean | object) - #0 string - #1 number - #2 boolean - #3 object - Additional properties: (string | number | boolean) - One of: (string | number | boolean) - #0 string - #1 number - #2 boolean - #4 object - Additional properties: (string | number | boolean | array<string | number | boolean>) - One of: (string | number | boolean | array<string | number | boolean>) - #0 string - #1 number - #2 boolean - #3 array<string | number | boolean> - Items: (string | number | boolean) - One of: (string | number | boolean) - #0 string - #1 number - #2 boolean - meta* object - Metadata about a document. - createdAt* number - createdBy* string - lastModifiedAt* number - lastModifiedBy* string - Additional properties: forbidden - Additional properties: forbidden

patches

Schema for document patches. array<object>

• Items: object

- op* string matches ^(ArrayAdd)|(ArrayRemove)|(ObjectAdd) - patch operation name - path* string - jsonpointer to element to patch - value* any - JSON encoded value for patch operation - Additional properties: forbidden

Example:

op="ArrayAdd"
path="/a/b/c"
value: { user="another_user" }

patchResult

Schema for patch result. object

• uri* string uri-reference - URI of resource
• patchFailed* boolean - True if patch could not be applied.
• message* string - Message explaining why document was not patched
• Additional properties: forbidden

location

Schema for location header. string uri-reference

uri

Schema for URI response body. object

• uri* string uri-reference - URI of resource

error

Error message. string