From dev-return-48268-archive-asf-public=cust-asf.ponee.io@couchdb.apache.org Sat Feb 9 16:19:57 2019 Return-Path: X-Original-To: archive-asf-public@cust-asf.ponee.io Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by mx-eu-01.ponee.io (Postfix) with SMTP id 9406E180677 for ; Sat, 9 Feb 2019 17:19:56 +0100 (CET) Received: (qmail 50786 invoked by uid 500); 9 Feb 2019 16:19:55 -0000 Mailing-List: contact dev-help@couchdb.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@couchdb.apache.org Delivered-To: mailing list dev@couchdb.apache.org Received: (qmail 50774 invoked by uid 99); 9 Feb 2019 16:19:54 -0000 Received: from pnap-us-west-generic-nat.apache.org (HELO spamd4-us-west.apache.org) (209.188.14.142) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 09 Feb 2019 16:19:54 +0000 Received: from localhost (localhost [127.0.0.1]) by spamd4-us-west.apache.org (ASF Mail Server at spamd4-us-west.apache.org) with ESMTP id 80C59C273D for ; Sat, 9 Feb 2019 16:19:54 +0000 (UTC) X-Virus-Scanned: Debian amavisd-new at spamd4-us-west.apache.org X-Spam-Flag: NO X-Spam-Score: -0.203 X-Spam-Level: X-Spam-Status: No, score=-0.203 tagged_above=-999 required=6.31 tests=[DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001] autolearn=disabled Authentication-Results: spamd4-us-west.apache.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from mx1-lw-us.apache.org ([10.40.0.8]) by localhost (spamd4-us-west.apache.org [10.40.0.11]) (amavisd-new, port 10024) with ESMTP id aEP4VDs9tlLu for ; Sat, 9 Feb 2019 16:19:53 +0000 (UTC) Received: from mail-ed1-f50.google.com (mail-ed1-f50.google.com [209.85.208.50]) by mx1-lw-us.apache.org (ASF Mail Server at mx1-lw-us.apache.org) with ESMTPS id B66275F36F for ; Sat, 9 Feb 2019 16:19:52 +0000 (UTC) Received: by mail-ed1-f50.google.com with SMTP id a2so5366773edi.0 for ; Sat, 09 Feb 2019 08:19:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=whXhXNPzwzCZCcUYLaT1KIV03tWP8f57cAh9vKEOB20=; b=s7hIB4DDpbGUmsZtY6gC+TMmIa/z3uaqCflETb3b24bQGKncJUpcsGoZIpqD08JPG1 uF/CSYq7Q33/3nHdDWOe72boeRKMfme1H7uQVW+aam2GXHNrA/vbfa0UusXJVXiNX0O4 yF8o2d/wi3qcWNPwr0x94JwNVjx3dN6hPAyNT6aneFRXiO8DIlDe5YEvElBnX6nAcOny 50RhxojeN7z69g8yFlGgO00KdIM5B51TjlT3oiCAH9YZxL6pvA0pQx0XolvraFqQofwt fmUKWZH4Nbu8qnhdjG5W/JoN8OaUgyqMB9Wi6UKuzGq5lLe/PmuTEdHnrV9K/y36gHUU tALg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=whXhXNPzwzCZCcUYLaT1KIV03tWP8f57cAh9vKEOB20=; b=iJHmh3h40R/rifbzvdzSOuzdDOo4lnTEy7T5UO04PYMewIVPjdbZZWDgchOUTMMaNf CtDQ7Qc4JkDK51kRQAIjqzL+GW3q8dJKZU5Ye1UDz/vnMpYTcKgXzR7Fsk/QWMYel6Fg XvEB2Z4TypbAI2m231NmDpzUkTAwdpb1SVs76RWfJeoxyeDbxEA91cmqGJtEJ+2ZjYFR McfEWtYIoh6o+imxHNXJzHdPdqSfzu0C4XTQhIn2v99nt30H0bPhtGelRUcZm/mykshv CeORTN6if5Ubq4HS6mEYP9MCBLeijniRXhBvHRIRDnKb5D6TEzblvLE9cbKq1Bgn3oZ8 8mSg== X-Gm-Message-State: AHQUAuZJT3zl8SeF2WjRMUVy4hZFfu4aFEFyZsduXrfMDoGf1OWJPy1p sxcgiqcQ8Eksm2ZYLsv3Z0uJkbzhOrYsGfOt8EyfjA== X-Google-Smtp-Source: AHgI3IZp8s4Q8QCYBHilElEeDil8rdCfIc+3BvJj2Uvx6XJuw4psvrNUwRuEQlI6IRlsp9LxaeHr/ITtZUPVcSKkfT0= X-Received: by 2002:a17:906:23f1:: with SMTP id j17mr20378395ejg.188.1549729185613; Sat, 09 Feb 2019 08:19:45 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Paul Davis Date: Sat, 9 Feb 2019 10:19:08 -0600 Message-ID: Subject: Re: # [DISCUSS] : things we need to solve/decide : storage of edit conflicts To: dev@couchdb.apache.org Content-Type: text/plain; charset="UTF-8" The _by_field indexes are a bit worrisome there. We've had users toss UUIDs and email addresses into keys which then blows the size of those indexes through the roof which causes all sorts of badness. On Fri, Feb 8, 2019 at 6:48 PM Ilya Khlopotov wrote: > > # Data model without support for per key revisions > > In this model "per key revisions" support was sacrificed so we can avoid doing read of previous revision of the document when we write new version of it. > > # Ranges used in the model > > - `{NS} / _mapping / _last_field_id > - `{NS} / _mapping / _by_field / {field_name} = field_id` # we would cache it in Layer's memory > - `{NS} / _mapping / _by_field_id / {field_id} = field_name` # we would cache it in Layer's memory > - `{NS} / {docid} / _info` = '{"scheme": {scheme_name} / {scheme_revision}, "revision": {revision}}' > - `{NS} / {docid} / _data / {compressed_json_path} = latest_value | part` > - `{NS} / {docid} / {revision} / _info` = '{"scheme": {scheme_name} / {scheme_revision}}' > - `{NS} / {docid} / {revision} / _data / {compressed_json_path} = value | part` > - `{NS} / {docid} / _index / _revs / {is_deleted} / {rev_pos} / {revision} = {parent_revision}` > - `{NS} / _index / _by_seq / {seq}` = "{docid} / {revision}" # seq is a FDB versionstamp > > We would have few special documents: > - "_schema / {schema_name}" - this doc would contain validation rules for schema (not used in MVP). > - when we start using schema we would be able to populate `{NS} / _mapping / xxx` range when we write schema document > - the schema document MUST fit into 100K (we don't use flatten JSON model for it) > > # JSON path compression > > - Assign integer field_id to every unique field_name of a JSON document starting from 10. > - We would use first 10 integers to encode type of the value: > - 0 - the value is an array > - 1 - the value is a big scalar value broken down into multiple parts > - 2..10 -- reserved for future use > - Replace field names in JSON path with field IDs > > ## Example of compressed JSON > ``` > { > foo: { > bar: { > baz: [1, 2, 3] > }, > langs: { > "en_US": "English", > "en_UK": "English (UK)" > "en_CA": "English (Canada)", > "zh_CN": "Chinese (China)" > }, > translations: { > "en_US": { > "license": "200 Kb of text" > } > } > } > } > ``` > this document would be compressed into > ``` > # written in separate transaction and cached in the Layer > {NS} / _mapping / _by_field / foo = 10 > {NS} / _mapping / _by_field / bar = 12 > {NS} / _mapping / _by_field / baz = 11 > {NS} / _mapping / _by_field / langs = 18 > {NS} / _mapping / _by_field / en_US = 13 > {NS} / _mapping / _by_field / en_UK = 14 > {NS} / _mapping / _by_field / en_CA = 15 > {NS} / _mapping / _by_field / zh_CN = 16 > {NS} / _mapping / _by_field / translations = 17 > {NS} / _mapping / _by_field / license = 19 > {NS} / _mapping / _by_field_id / 10 = foo > {NS} / _mapping / _by_field_id / 12 = bar > {NS} / _mapping / _by_field_id / 11 = baz > {NS} / _mapping / _by_field_id / 18 = langs > {NS} / _mapping / _by_field_id / 13 = en_US > {NS} / _mapping / _by_field_id / 14 = en_UK > {NS} / _mapping / _by_field_id / 15 = en_CA > {NS} / _mapping / _by_field_id / 16 = zh_CN > {NS} / _mapping / _by_field_id / 17 = translations > {NS} / _mapping / _by_field_id / 19 = license > > # written on document write > {NS} / {docid} / _data / 10 /12 / 11 / 0 / 0 = 1 > {NS} / {docid} / _data / 10 /12 / 11 / 0 / 1 = 2 > {NS} / {docid} / _data / 10 /12 / 11 / 0 / 2 = 3 > {NS} / {docid} / _data / 10 / 18 / 13 = English > {NS} / {docid} / _data / 10 / 18 / 14 = English (UK) > {NS} / {docid} / _data / 10 / 18 / 15 = English (Canada) > {NS} / {docid} / _data / 10 / 18 / 16 = Chinese (China) > {NS} / {docid} / _data / 10 / 17 / 13 / 19 / 1 / 0 = first 100K of license > {NS} / {docid} / _data / 10 / 17 / 13 / 19 / 1 / 1 = second 100K of license > ``` > > # Operations > > > ## Read latest revision > > - We do range read "{NS} / {docid}" and assemble documents using results of the query. > - If we cannot find field_id in Layer's cache we would read "{NS} / _mapping / _by_field_id " range and cache the result. > > ## Read specified revision > > - Do a range read "`{NS} / {docid} / {revision} /" and assemble document using result of the query > - If we cannot find field_id in Layer's cache we would read "{NS} / _mapping / _by_field_id " range and cache the result. > > ## Write > > - flatten JSON > - check if we there are missing fields in field cache of the Layer > - if the keys are missing start key allocation transaction > - read "{NS} / _mapping / _by_field / {field_name}" > - if it doesn't exists add key to the write conflict range (the FDB would do it by default) > - `field_idx = txn["{NS} / _mapping / _last_field_id"] + 1` and add it to the write conflict range (the FDB would do it by default) > - write `"{NS} / _mapping / _last_field_id" = field_idx` > - write `"{NS} / _mapping / _by_field / {field_name}" = field_idx` > - write `"{NS} / _mapping / _by_field_id / {field_idx}" = field_name` > - read `{NS} / {docid} / _info`, verify that revision is equal to specified parent_revision and add the key into write conflict range > - generate new_revision > - write all fields into two ranges (split big values as needed) > - "{NS} / {docid} / _data / {compressed_json_path}" > - "{NS} / {docid} / {new_revision} / _data / {compressed_json_path}" > - write into following keys > - `{NS} / {docid} / _info` = '{"scheme": {scheme_name} / {scheme_revision}, "revision": {revision}}' > - `{NS} / {docid} / {new_revision} / _info` = '{"scheme": {scheme_name} / {scheme_revision}}' > - `{NS} / {docid} / _index / _revs / {is_deleted} / {rev_pos} / {new_revision} = {parent_revision}` > - `{NS} / _index / _by_seq / {seq}` = "{docid} / {revision}" # seq is a FDB versionstamp > - update database stats > - `{NS} / _meta / number_of_docs` += 1 > - `{NS} / _meta / external_size` += external_size > > ## Get list of all known revisions for the document > > - range query `{NS} / {docid} / _index / _revs /` > > ## Changes feed > > - we would set a watch for `{NS} / _meta / external_size` key > - when watch is fired we would do a range query starting from "{NS} / _index / _by_seq / {since_seq}" > - remember last key returned by range query to set a new value for since_seq > > best regards, > iilyak > On 2019/02/04 19:25:13, Ilya Khlopotov wrote: > > This is a beginning of a discussion thread about storage of edit conflicts and everything which relates to revisions. > > > > > >