You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "tustvold (via GitHub)" <gi...@apache.org> on 2023/10/11 10:38:33 UTC

[PR] DynamoDB Coordination for AmazonS3 (#4880) [arrow-rs]

tustvold opened a new pull request, #4918:
URL: https://github.com/apache/arrow-rs/pull/4918

   # Which issue does this PR close?
   
   <!--
   We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
   -->
   
   Closes #4880
   
   # Rationale for this change
    
   <!--
   Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
   Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
   -->
   
   This crate aims to provide a uniform interface across a variety of different storage backends, facilitating the development of cloud-agnostic applications. Unfortunately the lack of support for conditional operations in S3 limits the scope of applications that this holds for, especially given how prevalent S3 is. _It should be noted I am not aware of an S3-compatible store that doesn't natively support conditional operations_
   
   This PR therefore adds a simple DynamoDB-based synchronisation mechanism, which avoids the lowest-denominator problem we currently have. Whilst perhaps not optimal for all use-cases, having an out-of-the-box mechanism to support this I think will open up some exciting new possibilities for applications built on top of object_store.
   
   # What changes are included in this PR?
   
   <!--
   There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
   -->
   
   # Are there any user-facing changes?
   
   No
   <!--
   If there are user-facing changes then we may require documentation to be updated before approving the PR.
   -->
   
   <!---
   If there are any breaking changes to public APIs, please add the `breaking change` label.
   -->
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1361216243


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   Two reasons:
   
   * DynamoDB TTL is best effort, I think the only guarantee is it runs about once a day
   * You want to avoid any risk of it kicking in early as a result of clock skew
   
   I'll try to encode these in comments



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] DynamoDB Coordination for AmazonS3 (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#issuecomment-1757926744

   I intend to add a mechanism using etag for lock busting


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1379936716


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,567 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+use chrono::Utc;
+use reqwest::{Response, StatusCode};
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::aws::AwsCredential;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "ConditionalCheckFailedException";
+
+const STORE: &str = "DynamoDB";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, `delete`, or
+/// conditional operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently delete and then create
+/// objects at the same path, instead being optimised for systems that primarily create
+/// files with paths never used before, or perform conditional updates to existing files
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),
+/// the commit protocol is as follows:
+///
+/// 1. Perform HEAD request on `path` and error on precondition mismatch
+/// 2. Create record in DynamoDB with key `{path}#{etag}` with the configured timeout
+///     1. On Success: Perform operation with the configured timeout
+///     2. On Conflict:
+///         1. Periodically re-perform HEAD request on `path` and error on precondition mismatch
+///         2. If `timeout * max_skew_rate` passed, replace the record incrementing the `"generation"`
+///             1. On Success: GOTO 2.1
+///             2. On Conflict: GOTO 2.2
+///
+/// Provided no writer modifies an object with a given `path` and `etag` without first adding a
+/// corresponding record to DynamoDB, we are guaranteed that only one writer will ever commit.
+///
+/// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+/// requirements of synchronizing object storage. The major changes are:
+///
+/// * Uses a monotonic generation count instead of a UUID rvn, as this is:
+///     * Cheaper to generate, serialize and compare
+///     * Cannot collide
+///     * More human readable / interpretable
+/// * Relies on [TTL] to eventually clean up old locks
+///
+/// It also draws inspiration from the DeltaLake [S3 Multi-Cluster] commit protocol, but
+/// generalised to not make assumptions about the workload and not rely on first writing
+/// to a temporary path.
+///
+/// [TTL]: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html
+/// [DynamoDB Lock Client]: https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
+/// [S3 Multi-Cluster]: https://docs.google.com/document/d/1Gs4ZsTH19lMxth4BSdwlWjUNR-XhKHicDvBjd2RqNd8/edit#heading=h.mjjuxw9mcz9h
+#[derive(Debug, Clone)]
+pub struct DynamoCommit {
+    table_name: String,
+    /// The number of milliseconds a lease is valid for
+    timeout: u64,
+    /// The maximum clock skew rate tolerated by the system
+    max_clock_skew_rate: u32,
+    /// The length of time a record will be retained in DynamoDB before being cleaned up
+    ///
+    /// This is purely an optimisation to avoid indefinite growth of the DynamoDB table
+    /// and does not impact how long clients may wait to acquire a lock
+    ttl: Duration,
+    /// The backoff duration before retesting a condition
+    test_interval: Duration,
+}
+
+impl DynamoCommit {
+    /// Create a new [`DynamoCommit`] with a given table name
+    pub fn new(table_name: String) -> Self {
+        Self {
+            table_name,
+            timeout: 20_000,
+            max_clock_skew_rate: 3,
+            ttl: Duration::from_secs(60 * 60),
+            test_interval: Duration::from_millis(100),
+        }
+    }
+
+    /// Overrides the lock timeout.
+    ///
+    /// A longer lock timeout reduces the probability of spurious commit failures and multi-writer
+    /// races, but will increase the time that writers must wait to reclaim a lock lost. The
+    /// default value of 20 seconds should be appropriate for must use-cases.
+    pub fn with_timeout(mut self, millis: u64) -> Self {
+        self.timeout = millis;
+        self
+    }
+
+    /// The maximum clock skew rate tolerated by the system.
+    ///
+    /// An environment in which the clock on the fastest node ticks twice as fast as the slowest
+    /// node, would have a clock skew rate of 2. The default value of 3 should be appropriate
+    /// for most environments.
+    pub fn with_max_clock_skew_rate(mut self, rate: u32) -> Self {
+        self.max_clock_skew_rate = rate;
+        self
+    }
+
+    /// The length of time a record should be retained in DynamoDB before being cleaned up
+    ///
+    /// This should be significantly larger than the configured lock timeout, with the default
+    /// value of 1 hour appropriate for most use-cases.
+    pub fn with_ttl(mut self, ttl: Duration) -> Self {
+        self.ttl = ttl;
+        self
+    }
+
+    /// Returns the name of the DynamoDB table.
+    pub(crate) fn table_name(&self) -> &str {
+        &self.table_name
+    }
+
+    pub(crate) async fn copy_if_not_exists(
+        &self,
+        client: &S3Client,
+        from: &Path,
+        to: &Path,
+    ) -> Result<()> {
+        check_not_exists(client, to).await?;
+
+        let mut previous_lease = None;
+
+        loop {
+            let existing = previous_lease.as_ref();
+            match self.try_lock(client, to.as_ref(), existing).await? {
+                TryLockResult::Ok(lease) => {
+                    let fut = client.copy_request(from, to).send();
+                    let expiry = lease.acquire + lease.timeout;
+                    return match tokio::time::timeout_at(expiry.into(), fut).await {
+                        Ok(Ok(_)) => Ok(()),
+                        Ok(Err(e)) => Err(e),
+                        Err(_) => Err(Error::Generic {
+                            store: "DynamoDB",
+                            source: format!(
+                                "Failed to perform copy operation in {} milliseconds",
+                                self.timeout
+                            )
+                            .into(),
+                        }),
+                    };
+                }
+                TryLockResult::Conflict(conflict) => {
+                    let mut interval = tokio::time::interval(self.test_interval);
+                    let expiry = conflict.timeout * self.max_clock_skew_rate;
+                    loop {
+                        interval.tick().await;
+                        check_not_exists(client, to).await?;
+                        if conflict.acquire.elapsed() > expiry {
+                            previous_lease = Some(conflict);
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    /// Retrieve a lock, returning an error if it doesn't exist
+    async fn get_lock(&self, s3: &S3Client, key: &str) -> Result<Lease> {
+        let key_attributes = [("key", AttributeValue::String(key))];
+        let req = GetItem {
+            table_name: &self.table_name,
+            key: Map(&key_attributes),
+        };
+        let credential = s3.config.get_credential().await?;
+
+        let resp = self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.GetItem", req)
+            .await
+            .map_err(|e| e.error(STORE, key.to_string()))?;
+
+        let body = resp.bytes().await.map_err(|e| Error::Generic {
+            store: STORE,
+            source: Box::new(e),
+        })?;
+
+        let response: GetItemResponse<'_> =
+            serde_json::from_slice(body.as_ref()).map_err(|e| Error::Generic {
+                store: STORE,
+                source: Box::new(e),
+            })?;
+
+        extract_lease(&response.item).ok_or_else(|| Error::NotFound {
+            path: key.into(),
+            source: "DynamoDB GetItem returned no items".to_string().into(),
+        })
+    }
+
+    /// Attempt to acquire a lock, reclaiming an existing lease if provided
+    async fn try_lock(
+        &self,
+        s3: &S3Client,
+        key: &str,
+        existing: Option<&Lease>,
+    ) -> Result<TryLockResult> {
+        let attributes;
+        let (next_gen, condition_expression, expression_attribute_values) = match existing {
+            None => (0_u64, "attribute_not_exists(#pk)", Map(&[])),
+            Some(existing) => {
+                attributes = [(":g", AttributeValue::Number(existing.generation))];
+                (
+                    existing.generation.checked_add(1).unwrap(),
+                    "attribute_exists(#pk) AND generation = :g",
+                    Map(attributes.as_slice()),
+                )
+            }
+        };
+
+        let ttl = (Utc::now() + self.ttl).timestamp();
+        let items = [
+            ("key", AttributeValue::String(key)),
+            ("generation", AttributeValue::Number(next_gen)),
+            ("timeout", AttributeValue::Number(self.timeout)),
+            ("ttl", AttributeValue::Number(ttl as _)),
+        ];
+        let names = [("#pk", "key")];
+
+        let req = PutItem {
+            table_name: &self.table_name,
+            condition_expression,
+            expression_attribute_values,
+            expression_attribute_names: Map(&names),
+            item: Map(&items),
+            return_values: None,
+            return_values_on_condition_check_failure: Some(ReturnValues::AllOld),
+        };
+
+        let credential = s3.config.get_credential().await?;
+
+        let acquire = Instant::now();
+        match self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.PutItem", req)
+            .await
+        {
+            Ok(_) => Ok(TryLockResult::Ok(Lease {
+                acquire,
+                generation: next_gen,
+                timeout: Duration::from_millis(self.timeout),
+            })),
+            Err(e) => match parse_error_response(&e) {
+                Some(e) if e.error.ends_with(CONFLICT) => match extract_lease(&e.item) {
+                    Some(lease) => Ok(TryLockResult::Conflict(lease)),
+                    // ReturnValuesOnConditionCheckFailure is a relatively recent addition
+                    // to DynamoDB and is not supported by dynamodb-local, which is used
+                    // by localstack. In such cases the conflict error will not contain
+                    // the conflicting item, and we must instead perform a get request
+                    //
+                    // There is a potential race here if the conflicting record is removed
+                    // before we retrieve it. We could retry the transaction in such a scenario,
+                    // but as this only occurs for emulators, we simply abort with a
+                    // not found error
+                    //
+                    // <https://aws.amazon.com/about-aws/whats-new/2023/06/amazon-dynamodb-cost-failed-conditional-writes/>
+                    // <https://repost.aws/questions/QUNfADrK4RT6WHe61RzTK8aw/dynamodblocal-support-for-returnvaluesonconditioncheckfailure-for-single-write-operations>
+                    // <https://github.com/localstack/localstack/issues/9040>
+                    None => Ok(TryLockResult::Conflict(self.get_lock(s3, key).await?)),
+                },
+                _ => Err(Error::Generic {
+                    store: STORE,
+                    source: Box::new(e),
+                }),
+            },
+        }
+    }
+
+    async fn request<R: Serialize + Send + Sync>(
+        &self,
+        s3: &S3Client,
+        cred: Option<&AwsCredential>,
+        target: &str,
+        req: R,
+    ) -> Result<Response, RetryError> {
+        let region = &s3.config.region;
+
+        let builder = match &s3.config.endpoint {
+            Some(e) => s3.client.post(e),
+            None => {
+                let url = format!("https://dynamodb.{region}.amazonaws.com");
+                s3.client.post(url)
+            }
+        };
+
+        builder
+            .timeout(Duration::from_millis(self.timeout))
+            .json(&req)
+            .header("X-Amz-Target", target)
+            .with_aws_sigv4(cred, region, "dynamodb", true, None)
+            .send_retry(&s3.config.retry_config)
+            .await
+    }
+}
+
+#[derive(Debug)]
+enum TryLockResult {
+    /// Successfully acquired a lease
+    Ok(Lease),
+    /// An existing lease was found
+    Conflict(Lease),
+}
+
+/// Returns an [`Error::AlreadyExists`] if `path` exists
+async fn check_not_exists(client: &S3Client, path: &Path) -> Result<()> {
+    let options = GetOptions {
+        head: true,
+        ..Default::default()
+    };
+    match client.get_opts(path, options).await {
+        Ok(_) => Err(Error::AlreadyExists {
+            path: path.to_string(),
+            source: "Already Exists".to_string().into(),
+        }),
+        Err(Error::NotFound { .. }) => Ok(()),
+        Err(e) => Err(e),
+    }
+}
+
+/// Parses the error response if any
+fn parse_error_response(e: &RetryError) -> Option<ErrorResponse<'_>> {
+    match e {
+        RetryError::Client {
+            status: StatusCode::BAD_REQUEST,
+            body: Some(b),
+        } => serde_json::from_str(b).ok(),
+        _ => None,
+    }
+}
+
+/// Extracts a lease from `item`, returning `None` on error
+fn extract_lease(item: &HashMap<&str, AttributeValue<'_>>) -> Option<Lease> {
+    let generation = match item.get("generation") {
+        Some(AttributeValue::Number(generation)) => generation,
+        _ => return None,
+    };
+
+    let timeout = match item.get("timeout") {
+        Some(AttributeValue::Number(timeout)) => *timeout,
+        _ => return None,
+    };
+
+    Some(Lease {
+        acquire: Instant::now(),

Review Comment:
   This method is for extracting someone else's lease, i.e. for detecting lock timeouts, and therefore should be pessimistic, i.e. start measuring the timeout from after the response



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362805509


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   > For 60 seconds and then the other writer will detect a stale lock, and reclaim it? Is that very bad?
   
   No. I seem to be confused.  was talking about whatever the 1 hour timeout is for.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#issuecomment-1868250435

   I plan to merge this in a few days unless anybody objects


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362748081


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   > this is the scenario when the whole table would be locked
   
   For 60 seconds?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#issuecomment-1785146247

   I think this is ready for review, I intend to follow this up with put_opts support and some more testing, but I want to avoid this PR getting too large


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "crepererum (via GitHub)" <gi...@apache.org>.
crepererum commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1379869043


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,567 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+use chrono::Utc;
+use reqwest::{Response, StatusCode};
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::aws::AwsCredential;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "ConditionalCheckFailedException";
+
+const STORE: &str = "DynamoDB";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, `delete`, or
+/// conditional operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently delete and then create
+/// objects at the same path, instead being optimised for systems that primarily create
+/// files with paths never used before, or perform conditional updates to existing files
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),
+/// the commit protocol is as follows:
+///
+/// 1. Perform HEAD request on `path` and error on precondition mismatch
+/// 2. Create record in DynamoDB with key `{path}#{etag}` with the configured timeout
+///     1. On Success: Perform operation with the configured timeout
+///     2. On Conflict:
+///         1. Periodically re-perform HEAD request on `path` and error on precondition mismatch
+///         2. If `timeout * max_skew_rate` passed, replace the record incrementing the `"generation"`
+///             1. On Success: GOTO 2.1
+///             2. On Conflict: GOTO 2.2
+///
+/// Provided no writer modifies an object with a given `path` and `etag` without first adding a
+/// corresponding record to DynamoDB, we are guaranteed that only one writer will ever commit.
+///
+/// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+/// requirements of synchronizing object storage. The major changes are:
+///
+/// * Uses a monotonic generation count instead of a UUID rvn, as this is:
+///     * Cheaper to generate, serialize and compare
+///     * Cannot collide
+///     * More human readable / interpretable
+/// * Relies on [TTL] to eventually clean up old locks
+///
+/// It also draws inspiration from the DeltaLake [S3 Multi-Cluster] commit protocol, but
+/// generalised to not make assumptions about the workload and not rely on first writing
+/// to a temporary path.
+///
+/// [TTL]: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html
+/// [DynamoDB Lock Client]: https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
+/// [S3 Multi-Cluster]: https://docs.google.com/document/d/1Gs4ZsTH19lMxth4BSdwlWjUNR-XhKHicDvBjd2RqNd8/edit#heading=h.mjjuxw9mcz9h
+#[derive(Debug, Clone)]
+pub struct DynamoCommit {
+    table_name: String,
+    /// The number of milliseconds a lease is valid for
+    timeout: u64,
+    /// The maximum clock skew rate tolerated by the system
+    max_clock_skew_rate: u32,
+    /// The length of time a record will be retained in DynamoDB before being cleaned up
+    ///
+    /// This is purely an optimisation to avoid indefinite growth of the DynamoDB table
+    /// and does not impact how long clients may wait to acquire a lock
+    ttl: Duration,
+    /// The backoff duration before retesting a condition
+    test_interval: Duration,
+}
+
+impl DynamoCommit {
+    /// Create a new [`DynamoCommit`] with a given table name
+    pub fn new(table_name: String) -> Self {
+        Self {
+            table_name,
+            timeout: 20_000,
+            max_clock_skew_rate: 3,
+            ttl: Duration::from_secs(60 * 60),
+            test_interval: Duration::from_millis(100),
+        }
+    }
+
+    /// Overrides the lock timeout.
+    ///
+    /// A longer lock timeout reduces the probability of spurious commit failures and multi-writer
+    /// races, but will increase the time that writers must wait to reclaim a lock lost. The
+    /// default value of 20 seconds should be appropriate for must use-cases.
+    pub fn with_timeout(mut self, millis: u64) -> Self {
+        self.timeout = millis;
+        self
+    }
+
+    /// The maximum clock skew rate tolerated by the system.
+    ///
+    /// An environment in which the clock on the fastest node ticks twice as fast as the slowest
+    /// node, would have a clock skew rate of 2. The default value of 3 should be appropriate
+    /// for most environments.
+    pub fn with_max_clock_skew_rate(mut self, rate: u32) -> Self {
+        self.max_clock_skew_rate = rate;
+        self
+    }
+
+    /// The length of time a record should be retained in DynamoDB before being cleaned up
+    ///
+    /// This should be significantly larger than the configured lock timeout, with the default
+    /// value of 1 hour appropriate for most use-cases.
+    pub fn with_ttl(mut self, ttl: Duration) -> Self {
+        self.ttl = ttl;
+        self
+    }
+
+    /// Returns the name of the DynamoDB table.
+    pub(crate) fn table_name(&self) -> &str {
+        &self.table_name
+    }
+
+    pub(crate) async fn copy_if_not_exists(
+        &self,
+        client: &S3Client,
+        from: &Path,
+        to: &Path,
+    ) -> Result<()> {
+        check_not_exists(client, to).await?;
+
+        let mut previous_lease = None;
+
+        loop {
+            let existing = previous_lease.as_ref();
+            match self.try_lock(client, to.as_ref(), existing).await? {
+                TryLockResult::Ok(lease) => {
+                    let fut = client.copy_request(from, to).send();
+                    let expiry = lease.acquire + lease.timeout;
+                    return match tokio::time::timeout_at(expiry.into(), fut).await {
+                        Ok(Ok(_)) => Ok(()),
+                        Ok(Err(e)) => Err(e),
+                        Err(_) => Err(Error::Generic {
+                            store: "DynamoDB",
+                            source: format!(
+                                "Failed to perform copy operation in {} milliseconds",
+                                self.timeout
+                            )
+                            .into(),
+                        }),
+                    };
+                }
+                TryLockResult::Conflict(conflict) => {
+                    let mut interval = tokio::time::interval(self.test_interval);
+                    let expiry = conflict.timeout * self.max_clock_skew_rate;
+                    loop {
+                        interval.tick().await;
+                        check_not_exists(client, to).await?;
+                        if conflict.acquire.elapsed() > expiry {
+                            previous_lease = Some(conflict);
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    /// Retrieve a lock, returning an error if it doesn't exist
+    async fn get_lock(&self, s3: &S3Client, key: &str) -> Result<Lease> {
+        let key_attributes = [("key", AttributeValue::String(key))];
+        let req = GetItem {
+            table_name: &self.table_name,
+            key: Map(&key_attributes),
+        };
+        let credential = s3.config.get_credential().await?;
+
+        let resp = self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.GetItem", req)
+            .await
+            .map_err(|e| e.error(STORE, key.to_string()))?;
+
+        let body = resp.bytes().await.map_err(|e| Error::Generic {
+            store: STORE,
+            source: Box::new(e),
+        })?;
+
+        let response: GetItemResponse<'_> =
+            serde_json::from_slice(body.as_ref()).map_err(|e| Error::Generic {
+                store: STORE,
+                source: Box::new(e),
+            })?;
+
+        extract_lease(&response.item).ok_or_else(|| Error::NotFound {
+            path: key.into(),
+            source: "DynamoDB GetItem returned no items".to_string().into(),
+        })
+    }
+
+    /// Attempt to acquire a lock, reclaiming an existing lease if provided
+    async fn try_lock(
+        &self,
+        s3: &S3Client,
+        key: &str,
+        existing: Option<&Lease>,
+    ) -> Result<TryLockResult> {
+        let attributes;
+        let (next_gen, condition_expression, expression_attribute_values) = match existing {
+            None => (0_u64, "attribute_not_exists(#pk)", Map(&[])),
+            Some(existing) => {
+                attributes = [(":g", AttributeValue::Number(existing.generation))];
+                (
+                    existing.generation.checked_add(1).unwrap(),
+                    "attribute_exists(#pk) AND generation = :g",
+                    Map(attributes.as_slice()),
+                )
+            }
+        };
+
+        let ttl = (Utc::now() + self.ttl).timestamp();
+        let items = [
+            ("key", AttributeValue::String(key)),
+            ("generation", AttributeValue::Number(next_gen)),
+            ("timeout", AttributeValue::Number(self.timeout)),
+            ("ttl", AttributeValue::Number(ttl as _)),

Review Comment:
   Isn't this attribute name a user setting? According to <https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/time-to-live-ttl-how-to.html> the user has to set this for the table. If you expect the user to set this up (e.g. using the console), then you should probably document this on a higher level. Another option would be to set this up using the client (e.g. when the client is created or first used) via <https://docs.aws.amazon.com/amazondynamodb/latest/APIReference/API_UpdateTimeToLive.html>.



##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,567 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+use chrono::Utc;
+use reqwest::{Response, StatusCode};
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::aws::AwsCredential;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "ConditionalCheckFailedException";
+
+const STORE: &str = "DynamoDB";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, `delete`, or
+/// conditional operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently delete and then create
+/// objects at the same path, instead being optimised for systems that primarily create
+/// files with paths never used before, or perform conditional updates to existing files
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),
+/// the commit protocol is as follows:
+///
+/// 1. Perform HEAD request on `path` and error on precondition mismatch
+/// 2. Create record in DynamoDB with key `{path}#{etag}` with the configured timeout
+///     1. On Success: Perform operation with the configured timeout
+///     2. On Conflict:
+///         1. Periodically re-perform HEAD request on `path` and error on precondition mismatch
+///         2. If `timeout * max_skew_rate` passed, replace the record incrementing the `"generation"`
+///             1. On Success: GOTO 2.1
+///             2. On Conflict: GOTO 2.2
+///
+/// Provided no writer modifies an object with a given `path` and `etag` without first adding a
+/// corresponding record to DynamoDB, we are guaranteed that only one writer will ever commit.
+///
+/// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+/// requirements of synchronizing object storage. The major changes are:
+///
+/// * Uses a monotonic generation count instead of a UUID rvn, as this is:
+///     * Cheaper to generate, serialize and compare
+///     * Cannot collide
+///     * More human readable / interpretable
+/// * Relies on [TTL] to eventually clean up old locks
+///
+/// It also draws inspiration from the DeltaLake [S3 Multi-Cluster] commit protocol, but
+/// generalised to not make assumptions about the workload and not rely on first writing
+/// to a temporary path.
+///
+/// [TTL]: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html
+/// [DynamoDB Lock Client]: https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
+/// [S3 Multi-Cluster]: https://docs.google.com/document/d/1Gs4ZsTH19lMxth4BSdwlWjUNR-XhKHicDvBjd2RqNd8/edit#heading=h.mjjuxw9mcz9h
+#[derive(Debug, Clone)]
+pub struct DynamoCommit {
+    table_name: String,
+    /// The number of milliseconds a lease is valid for
+    timeout: u64,
+    /// The maximum clock skew rate tolerated by the system
+    max_clock_skew_rate: u32,
+    /// The length of time a record will be retained in DynamoDB before being cleaned up
+    ///
+    /// This is purely an optimisation to avoid indefinite growth of the DynamoDB table
+    /// and does not impact how long clients may wait to acquire a lock
+    ttl: Duration,
+    /// The backoff duration before retesting a condition
+    test_interval: Duration,
+}
+
+impl DynamoCommit {
+    /// Create a new [`DynamoCommit`] with a given table name
+    pub fn new(table_name: String) -> Self {
+        Self {
+            table_name,
+            timeout: 20_000,
+            max_clock_skew_rate: 3,
+            ttl: Duration::from_secs(60 * 60),
+            test_interval: Duration::from_millis(100),
+        }
+    }
+
+    /// Overrides the lock timeout.
+    ///
+    /// A longer lock timeout reduces the probability of spurious commit failures and multi-writer
+    /// races, but will increase the time that writers must wait to reclaim a lock lost. The
+    /// default value of 20 seconds should be appropriate for must use-cases.
+    pub fn with_timeout(mut self, millis: u64) -> Self {
+        self.timeout = millis;
+        self
+    }
+
+    /// The maximum clock skew rate tolerated by the system.
+    ///
+    /// An environment in which the clock on the fastest node ticks twice as fast as the slowest
+    /// node, would have a clock skew rate of 2. The default value of 3 should be appropriate
+    /// for most environments.
+    pub fn with_max_clock_skew_rate(mut self, rate: u32) -> Self {
+        self.max_clock_skew_rate = rate;
+        self
+    }
+
+    /// The length of time a record should be retained in DynamoDB before being cleaned up
+    ///
+    /// This should be significantly larger than the configured lock timeout, with the default
+    /// value of 1 hour appropriate for most use-cases.
+    pub fn with_ttl(mut self, ttl: Duration) -> Self {
+        self.ttl = ttl;
+        self
+    }
+
+    /// Returns the name of the DynamoDB table.
+    pub(crate) fn table_name(&self) -> &str {
+        &self.table_name
+    }
+
+    pub(crate) async fn copy_if_not_exists(
+        &self,
+        client: &S3Client,
+        from: &Path,
+        to: &Path,
+    ) -> Result<()> {
+        check_not_exists(client, to).await?;
+
+        let mut previous_lease = None;
+
+        loop {
+            let existing = previous_lease.as_ref();
+            match self.try_lock(client, to.as_ref(), existing).await? {
+                TryLockResult::Ok(lease) => {
+                    let fut = client.copy_request(from, to).send();
+                    let expiry = lease.acquire + lease.timeout;
+                    return match tokio::time::timeout_at(expiry.into(), fut).await {
+                        Ok(Ok(_)) => Ok(()),
+                        Ok(Err(e)) => Err(e),
+                        Err(_) => Err(Error::Generic {
+                            store: "DynamoDB",
+                            source: format!(
+                                "Failed to perform copy operation in {} milliseconds",
+                                self.timeout
+                            )
+                            .into(),
+                        }),
+                    };
+                }
+                TryLockResult::Conflict(conflict) => {
+                    let mut interval = tokio::time::interval(self.test_interval);
+                    let expiry = conflict.timeout * self.max_clock_skew_rate;
+                    loop {
+                        interval.tick().await;
+                        check_not_exists(client, to).await?;
+                        if conflict.acquire.elapsed() > expiry {
+                            previous_lease = Some(conflict);
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    /// Retrieve a lock, returning an error if it doesn't exist
+    async fn get_lock(&self, s3: &S3Client, key: &str) -> Result<Lease> {
+        let key_attributes = [("key", AttributeValue::String(key))];
+        let req = GetItem {
+            table_name: &self.table_name,
+            key: Map(&key_attributes),
+        };
+        let credential = s3.config.get_credential().await?;
+
+        let resp = self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.GetItem", req)
+            .await
+            .map_err(|e| e.error(STORE, key.to_string()))?;
+
+        let body = resp.bytes().await.map_err(|e| Error::Generic {
+            store: STORE,
+            source: Box::new(e),
+        })?;
+
+        let response: GetItemResponse<'_> =
+            serde_json::from_slice(body.as_ref()).map_err(|e| Error::Generic {
+                store: STORE,
+                source: Box::new(e),
+            })?;
+
+        extract_lease(&response.item).ok_or_else(|| Error::NotFound {
+            path: key.into(),
+            source: "DynamoDB GetItem returned no items".to_string().into(),
+        })
+    }
+
+    /// Attempt to acquire a lock, reclaiming an existing lease if provided
+    async fn try_lock(
+        &self,
+        s3: &S3Client,
+        key: &str,
+        existing: Option<&Lease>,
+    ) -> Result<TryLockResult> {
+        let attributes;
+        let (next_gen, condition_expression, expression_attribute_values) = match existing {
+            None => (0_u64, "attribute_not_exists(#pk)", Map(&[])),
+            Some(existing) => {
+                attributes = [(":g", AttributeValue::Number(existing.generation))];
+                (
+                    existing.generation.checked_add(1).unwrap(),
+                    "attribute_exists(#pk) AND generation = :g",
+                    Map(attributes.as_slice()),
+                )
+            }
+        };
+
+        let ttl = (Utc::now() + self.ttl).timestamp();
+        let items = [
+            ("key", AttributeValue::String(key)),
+            ("generation", AttributeValue::Number(next_gen)),
+            ("timeout", AttributeValue::Number(self.timeout)),
+            ("ttl", AttributeValue::Number(ttl as _)),
+        ];
+        let names = [("#pk", "key")];
+
+        let req = PutItem {
+            table_name: &self.table_name,
+            condition_expression,
+            expression_attribute_values,
+            expression_attribute_names: Map(&names),
+            item: Map(&items),
+            return_values: None,
+            return_values_on_condition_check_failure: Some(ReturnValues::AllOld),
+        };
+
+        let credential = s3.config.get_credential().await?;
+
+        let acquire = Instant::now();
+        match self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.PutItem", req)
+            .await
+        {
+            Ok(_) => Ok(TryLockResult::Ok(Lease {
+                acquire,
+                generation: next_gen,
+                timeout: Duration::from_millis(self.timeout),
+            })),
+            Err(e) => match parse_error_response(&e) {
+                Some(e) if e.error.ends_with(CONFLICT) => match extract_lease(&e.item) {
+                    Some(lease) => Ok(TryLockResult::Conflict(lease)),
+                    // ReturnValuesOnConditionCheckFailure is a relatively recent addition
+                    // to DynamoDB and is not supported by dynamodb-local, which is used
+                    // by localstack. In such cases the conflict error will not contain
+                    // the conflicting item, and we must instead perform a get request
+                    //
+                    // There is a potential race here if the conflicting record is removed
+                    // before we retrieve it. We could retry the transaction in such a scenario,
+                    // but as this only occurs for emulators, we simply abort with a
+                    // not found error
+                    //
+                    // <https://aws.amazon.com/about-aws/whats-new/2023/06/amazon-dynamodb-cost-failed-conditional-writes/>
+                    // <https://repost.aws/questions/QUNfADrK4RT6WHe61RzTK8aw/dynamodblocal-support-for-returnvaluesonconditioncheckfailure-for-single-write-operations>
+                    // <https://github.com/localstack/localstack/issues/9040>
+                    None => Ok(TryLockResult::Conflict(self.get_lock(s3, key).await?)),
+                },
+                _ => Err(Error::Generic {
+                    store: STORE,
+                    source: Box::new(e),
+                }),
+            },
+        }
+    }
+
+    async fn request<R: Serialize + Send + Sync>(
+        &self,
+        s3: &S3Client,
+        cred: Option<&AwsCredential>,
+        target: &str,
+        req: R,
+    ) -> Result<Response, RetryError> {
+        let region = &s3.config.region;
+
+        let builder = match &s3.config.endpoint {
+            Some(e) => s3.client.post(e),
+            None => {
+                let url = format!("https://dynamodb.{region}.amazonaws.com");
+                s3.client.post(url)
+            }
+        };
+
+        builder
+            .timeout(Duration::from_millis(self.timeout))
+            .json(&req)
+            .header("X-Amz-Target", target)
+            .with_aws_sigv4(cred, region, "dynamodb", true, None)
+            .send_retry(&s3.config.retry_config)
+            .await
+    }
+}
+
+#[derive(Debug)]
+enum TryLockResult {
+    /// Successfully acquired a lease
+    Ok(Lease),
+    /// An existing lease was found
+    Conflict(Lease),
+}
+
+/// Returns an [`Error::AlreadyExists`] if `path` exists
+async fn check_not_exists(client: &S3Client, path: &Path) -> Result<()> {
+    let options = GetOptions {
+        head: true,
+        ..Default::default()
+    };
+    match client.get_opts(path, options).await {
+        Ok(_) => Err(Error::AlreadyExists {
+            path: path.to_string(),
+            source: "Already Exists".to_string().into(),
+        }),
+        Err(Error::NotFound { .. }) => Ok(()),
+        Err(e) => Err(e),
+    }
+}
+
+/// Parses the error response if any
+fn parse_error_response(e: &RetryError) -> Option<ErrorResponse<'_>> {
+    match e {
+        RetryError::Client {
+            status: StatusCode::BAD_REQUEST,
+            body: Some(b),
+        } => serde_json::from_str(b).ok(),
+        _ => None,
+    }
+}
+
+/// Extracts a lease from `item`, returning `None` on error
+fn extract_lease(item: &HashMap<&str, AttributeValue<'_>>) -> Option<Lease> {
+    let generation = match item.get("generation") {
+        Some(AttributeValue::Number(generation)) => generation,
+        _ => return None,
+    };
+
+    let timeout = match item.get("timeout") {
+        Some(AttributeValue::Number(timeout)) => *timeout,
+        _ => return None,
+    };
+
+    Some(Lease {
+        acquire: Instant::now(),

Review Comment:
   This instant should be measured BEFORE the dynamo HTTP request, not after. Otherwise your "clock skew" kinda includes HTTP roundtrip times.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1361180987


##########
object_store/src/aws/client.rs:
##########
@@ -200,15 +198,14 @@ impl From<DeleteError> for Error {
 #[derive(Debug)]
 pub struct S3Config {
     pub region: String,
-    pub endpoint: String,
+    pub endpoint: Option<String>,

Review Comment:
   I double checked that this is not a (breaking) API change, as it changes the type of a pub field because the module is not pub:
   
   https://github.com/apache/arrow-rs/blob/95b015cf7b5d57c7fe66a8feada4f48a987cb020/object_store/src/aws/mod.rs#L66
   
   https://docs.rs/object_store/latest/object_store/struct.ObjectMeta.html?search=S3Config#structfield.e_tag



##########
object_store/src/aws/copy.rs:
##########
@@ -39,12 +39,64 @@ pub enum S3CopyIfNotExists {
     ///
     /// [`ObjectStore::copy_if_not_exists`]: crate::ObjectStore::copy_if_not_exists
     Header(String, String),
+    /// The name of a DynamoDB table to use for coordination
+    ///
+    /// Encoded as `dynamodb:<TABLE_NAME>` ignoring whitespace
+    ///
+    /// This will use the same region, credentials and endpoint as configured for S3
+    ///
+    /// ## Limitations
+    ///
+    /// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+    /// therefore race with non-conditional operations, e.g. `put`, `copy`, or conditional
+    /// operations performed by writers not configured to synchronize with DynamoDB.
+    ///
+    /// Workloads making use of this mechanism **must** ensure:
+    ///
+    /// * Conditional and non-conditional operations are not performed on the same paths
+    /// * Conditional operations are only performed via similarly configured clients
+    ///
+    /// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+    /// performance will be poor for systems that frequently rewrite the same path, instead
+    /// being optimised for systems that primarily create files with paths never used before.
+    ///
+    /// ## Locking Protocol
+    ///
+    /// The DynamoDB schema is as follows:
+    ///
+    /// * A string hash key named `"key"`
+    /// * A numeric [TTL] attribute named `"ttl"`
+    /// * A numeric attribute named `"generation"`
+    ///
+    /// The lock procedure is as follows:
+    ///
+    /// * Error if file exists in S3
+    /// * Create a corresponding record in DynamoDB with the path as the `"key"`
+    ///     * On Success: Create object in S3
+    ///     * On Conflict:
+    ///         * Periodically check if file exists in S3
+    ///         * After a 60 second timeout attempt to "claim" the lock by incrementing `"generation"`
+    ///         * GOTO start
+    ///
+    /// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+    /// requirements of synchronizing object storage.
+    ///
+    /// The major changes are:
+    ///
+    /// * Uses a monotonic generation count instead of a UUID rvn
+    /// * Relies on [TTL] to eventually clean up old locks
+    /// * Uses a hard-coded lease duration of 20 seconds
+    ///
+    /// [TTL]: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html
+    /// [DynamoDB Lock Client]: https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
+    Dynamo(String),

Review Comment:
   I recommend also adding in the parameters here for TTL, and LEASE_EXPIRY rather than hard coding it or having to make backwards incompatible changes in the future



##########
object_store/src/aws/copy.rs:
##########
@@ -39,12 +39,64 @@ pub enum S3CopyIfNotExists {
     ///
     /// [`ObjectStore::copy_if_not_exists`]: crate::ObjectStore::copy_if_not_exists
     Header(String, String),
+    /// The name of a DynamoDB table to use for coordination
+    ///
+    /// Encoded as `dynamodb:<TABLE_NAME>` ignoring whitespace
+    ///
+    /// This will use the same region, credentials and endpoint as configured for S3
+    ///
+    /// ## Limitations
+    ///
+    /// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+    /// therefore race with non-conditional operations, e.g. `put`, `copy`, or conditional
+    /// operations performed by writers not configured to synchronize with DynamoDB.
+    ///
+    /// Workloads making use of this mechanism **must** ensure:
+    ///
+    /// * Conditional and non-conditional operations are not performed on the same paths
+    /// * Conditional operations are only performed via similarly configured clients
+    ///
+    /// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+    /// performance will be poor for systems that frequently rewrite the same path, instead
+    /// being optimised for systems that primarily create files with paths never used before.
+    ///
+    /// ## Locking Protocol
+    ///
+    /// The DynamoDB schema is as follows:
+    ///
+    /// * A string hash key named `"key"`
+    /// * A numeric [TTL] attribute named `"ttl"`
+    /// * A numeric attribute named `"generation"`
+    ///
+    /// The lock procedure is as follows:
+    ///
+    /// * Error if file exists in S3
+    /// * Create a corresponding record in DynamoDB with the path as the `"key"`
+    ///     * On Success: Create object in S3
+    ///     * On Conflict:
+    ///         * Periodically check if file exists in S3
+    ///         * After a 60 second timeout attempt to "claim" the lock by incrementing `"generation"`
+    ///         * GOTO start
+    ///
+    /// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+    /// requirements of synchronizing object storage.
+    ///
+    /// The major changes are:
+    ///
+    /// * Uses a monotonic generation count instead of a UUID rvn

Review Comment:
   A monotonic generation can have collisions between multiple client writers who are claiming expired locks, right? Why not use the UUID?



##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   What is the rationale for such long timeouts?
   
   The lease time to live is an hour which seems like a long time, especially given the lease expiry is for 60 seconds but the actual operation being performed (copy) likely takes much less. 
   
   I strongly suggest these values can be specified via configuration values rather than hard coded



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362816581


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   Thank you for the clarification -- ~perhaps this could be encoded in comments.~
   
   The new wording makes it clearer
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362748081


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   > this is the scenario when the whole table would be locked
   
   For 60 seconds and then the other writer will detect a stale lock, and reclaim it? Is that very bad?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#issuecomment-1867995983

   @roeap perhaps you might have time to give this a once over?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1379936716


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,567 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+use chrono::Utc;
+use reqwest::{Response, StatusCode};
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::aws::AwsCredential;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "ConditionalCheckFailedException";
+
+const STORE: &str = "DynamoDB";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, `delete`, or
+/// conditional operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently delete and then create
+/// objects at the same path, instead being optimised for systems that primarily create
+/// files with paths never used before, or perform conditional updates to existing files
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),
+/// the commit protocol is as follows:
+///
+/// 1. Perform HEAD request on `path` and error on precondition mismatch
+/// 2. Create record in DynamoDB with key `{path}#{etag}` with the configured timeout
+///     1. On Success: Perform operation with the configured timeout
+///     2. On Conflict:
+///         1. Periodically re-perform HEAD request on `path` and error on precondition mismatch
+///         2. If `timeout * max_skew_rate` passed, replace the record incrementing the `"generation"`
+///             1. On Success: GOTO 2.1
+///             2. On Conflict: GOTO 2.2
+///
+/// Provided no writer modifies an object with a given `path` and `etag` without first adding a
+/// corresponding record to DynamoDB, we are guaranteed that only one writer will ever commit.
+///
+/// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+/// requirements of synchronizing object storage. The major changes are:
+///
+/// * Uses a monotonic generation count instead of a UUID rvn, as this is:
+///     * Cheaper to generate, serialize and compare
+///     * Cannot collide
+///     * More human readable / interpretable
+/// * Relies on [TTL] to eventually clean up old locks
+///
+/// It also draws inspiration from the DeltaLake [S3 Multi-Cluster] commit protocol, but
+/// generalised to not make assumptions about the workload and not rely on first writing
+/// to a temporary path.
+///
+/// [TTL]: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html
+/// [DynamoDB Lock Client]: https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
+/// [S3 Multi-Cluster]: https://docs.google.com/document/d/1Gs4ZsTH19lMxth4BSdwlWjUNR-XhKHicDvBjd2RqNd8/edit#heading=h.mjjuxw9mcz9h
+#[derive(Debug, Clone)]
+pub struct DynamoCommit {
+    table_name: String,
+    /// The number of milliseconds a lease is valid for
+    timeout: u64,
+    /// The maximum clock skew rate tolerated by the system
+    max_clock_skew_rate: u32,
+    /// The length of time a record will be retained in DynamoDB before being cleaned up
+    ///
+    /// This is purely an optimisation to avoid indefinite growth of the DynamoDB table
+    /// and does not impact how long clients may wait to acquire a lock
+    ttl: Duration,
+    /// The backoff duration before retesting a condition
+    test_interval: Duration,
+}
+
+impl DynamoCommit {
+    /// Create a new [`DynamoCommit`] with a given table name
+    pub fn new(table_name: String) -> Self {
+        Self {
+            table_name,
+            timeout: 20_000,
+            max_clock_skew_rate: 3,
+            ttl: Duration::from_secs(60 * 60),
+            test_interval: Duration::from_millis(100),
+        }
+    }
+
+    /// Overrides the lock timeout.
+    ///
+    /// A longer lock timeout reduces the probability of spurious commit failures and multi-writer
+    /// races, but will increase the time that writers must wait to reclaim a lock lost. The
+    /// default value of 20 seconds should be appropriate for must use-cases.
+    pub fn with_timeout(mut self, millis: u64) -> Self {
+        self.timeout = millis;
+        self
+    }
+
+    /// The maximum clock skew rate tolerated by the system.
+    ///
+    /// An environment in which the clock on the fastest node ticks twice as fast as the slowest
+    /// node, would have a clock skew rate of 2. The default value of 3 should be appropriate
+    /// for most environments.
+    pub fn with_max_clock_skew_rate(mut self, rate: u32) -> Self {
+        self.max_clock_skew_rate = rate;
+        self
+    }
+
+    /// The length of time a record should be retained in DynamoDB before being cleaned up
+    ///
+    /// This should be significantly larger than the configured lock timeout, with the default
+    /// value of 1 hour appropriate for most use-cases.
+    pub fn with_ttl(mut self, ttl: Duration) -> Self {
+        self.ttl = ttl;
+        self
+    }
+
+    /// Returns the name of the DynamoDB table.
+    pub(crate) fn table_name(&self) -> &str {
+        &self.table_name
+    }
+
+    pub(crate) async fn copy_if_not_exists(
+        &self,
+        client: &S3Client,
+        from: &Path,
+        to: &Path,
+    ) -> Result<()> {
+        check_not_exists(client, to).await?;
+
+        let mut previous_lease = None;
+
+        loop {
+            let existing = previous_lease.as_ref();
+            match self.try_lock(client, to.as_ref(), existing).await? {
+                TryLockResult::Ok(lease) => {
+                    let fut = client.copy_request(from, to).send();
+                    let expiry = lease.acquire + lease.timeout;
+                    return match tokio::time::timeout_at(expiry.into(), fut).await {
+                        Ok(Ok(_)) => Ok(()),
+                        Ok(Err(e)) => Err(e),
+                        Err(_) => Err(Error::Generic {
+                            store: "DynamoDB",
+                            source: format!(
+                                "Failed to perform copy operation in {} milliseconds",
+                                self.timeout
+                            )
+                            .into(),
+                        }),
+                    };
+                }
+                TryLockResult::Conflict(conflict) => {
+                    let mut interval = tokio::time::interval(self.test_interval);
+                    let expiry = conflict.timeout * self.max_clock_skew_rate;
+                    loop {
+                        interval.tick().await;
+                        check_not_exists(client, to).await?;
+                        if conflict.acquire.elapsed() > expiry {
+                            previous_lease = Some(conflict);
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    /// Retrieve a lock, returning an error if it doesn't exist
+    async fn get_lock(&self, s3: &S3Client, key: &str) -> Result<Lease> {
+        let key_attributes = [("key", AttributeValue::String(key))];
+        let req = GetItem {
+            table_name: &self.table_name,
+            key: Map(&key_attributes),
+        };
+        let credential = s3.config.get_credential().await?;
+
+        let resp = self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.GetItem", req)
+            .await
+            .map_err(|e| e.error(STORE, key.to_string()))?;
+
+        let body = resp.bytes().await.map_err(|e| Error::Generic {
+            store: STORE,
+            source: Box::new(e),
+        })?;
+
+        let response: GetItemResponse<'_> =
+            serde_json::from_slice(body.as_ref()).map_err(|e| Error::Generic {
+                store: STORE,
+                source: Box::new(e),
+            })?;
+
+        extract_lease(&response.item).ok_or_else(|| Error::NotFound {
+            path: key.into(),
+            source: "DynamoDB GetItem returned no items".to_string().into(),
+        })
+    }
+
+    /// Attempt to acquire a lock, reclaiming an existing lease if provided
+    async fn try_lock(
+        &self,
+        s3: &S3Client,
+        key: &str,
+        existing: Option<&Lease>,
+    ) -> Result<TryLockResult> {
+        let attributes;
+        let (next_gen, condition_expression, expression_attribute_values) = match existing {
+            None => (0_u64, "attribute_not_exists(#pk)", Map(&[])),
+            Some(existing) => {
+                attributes = [(":g", AttributeValue::Number(existing.generation))];
+                (
+                    existing.generation.checked_add(1).unwrap(),
+                    "attribute_exists(#pk) AND generation = :g",
+                    Map(attributes.as_slice()),
+                )
+            }
+        };
+
+        let ttl = (Utc::now() + self.ttl).timestamp();
+        let items = [
+            ("key", AttributeValue::String(key)),
+            ("generation", AttributeValue::Number(next_gen)),
+            ("timeout", AttributeValue::Number(self.timeout)),
+            ("ttl", AttributeValue::Number(ttl as _)),
+        ];
+        let names = [("#pk", "key")];
+
+        let req = PutItem {
+            table_name: &self.table_name,
+            condition_expression,
+            expression_attribute_values,
+            expression_attribute_names: Map(&names),
+            item: Map(&items),
+            return_values: None,
+            return_values_on_condition_check_failure: Some(ReturnValues::AllOld),
+        };
+
+        let credential = s3.config.get_credential().await?;
+
+        let acquire = Instant::now();
+        match self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.PutItem", req)
+            .await
+        {
+            Ok(_) => Ok(TryLockResult::Ok(Lease {
+                acquire,
+                generation: next_gen,
+                timeout: Duration::from_millis(self.timeout),
+            })),
+            Err(e) => match parse_error_response(&e) {
+                Some(e) if e.error.ends_with(CONFLICT) => match extract_lease(&e.item) {
+                    Some(lease) => Ok(TryLockResult::Conflict(lease)),
+                    // ReturnValuesOnConditionCheckFailure is a relatively recent addition
+                    // to DynamoDB and is not supported by dynamodb-local, which is used
+                    // by localstack. In such cases the conflict error will not contain
+                    // the conflicting item, and we must instead perform a get request
+                    //
+                    // There is a potential race here if the conflicting record is removed
+                    // before we retrieve it. We could retry the transaction in such a scenario,
+                    // but as this only occurs for emulators, we simply abort with a
+                    // not found error
+                    //
+                    // <https://aws.amazon.com/about-aws/whats-new/2023/06/amazon-dynamodb-cost-failed-conditional-writes/>
+                    // <https://repost.aws/questions/QUNfADrK4RT6WHe61RzTK8aw/dynamodblocal-support-for-returnvaluesonconditioncheckfailure-for-single-write-operations>
+                    // <https://github.com/localstack/localstack/issues/9040>
+                    None => Ok(TryLockResult::Conflict(self.get_lock(s3, key).await?)),
+                },
+                _ => Err(Error::Generic {
+                    store: STORE,
+                    source: Box::new(e),
+                }),
+            },
+        }
+    }
+
+    async fn request<R: Serialize + Send + Sync>(
+        &self,
+        s3: &S3Client,
+        cred: Option<&AwsCredential>,
+        target: &str,
+        req: R,
+    ) -> Result<Response, RetryError> {
+        let region = &s3.config.region;
+
+        let builder = match &s3.config.endpoint {
+            Some(e) => s3.client.post(e),
+            None => {
+                let url = format!("https://dynamodb.{region}.amazonaws.com");
+                s3.client.post(url)
+            }
+        };
+
+        builder
+            .timeout(Duration::from_millis(self.timeout))
+            .json(&req)
+            .header("X-Amz-Target", target)
+            .with_aws_sigv4(cred, region, "dynamodb", true, None)
+            .send_retry(&s3.config.retry_config)
+            .await
+    }
+}
+
+#[derive(Debug)]
+enum TryLockResult {
+    /// Successfully acquired a lease
+    Ok(Lease),
+    /// An existing lease was found
+    Conflict(Lease),
+}
+
+/// Returns an [`Error::AlreadyExists`] if `path` exists
+async fn check_not_exists(client: &S3Client, path: &Path) -> Result<()> {
+    let options = GetOptions {
+        head: true,
+        ..Default::default()
+    };
+    match client.get_opts(path, options).await {
+        Ok(_) => Err(Error::AlreadyExists {
+            path: path.to_string(),
+            source: "Already Exists".to_string().into(),
+        }),
+        Err(Error::NotFound { .. }) => Ok(()),
+        Err(e) => Err(e),
+    }
+}
+
+/// Parses the error response if any
+fn parse_error_response(e: &RetryError) -> Option<ErrorResponse<'_>> {
+    match e {
+        RetryError::Client {
+            status: StatusCode::BAD_REQUEST,
+            body: Some(b),
+        } => serde_json::from_str(b).ok(),
+        _ => None,
+    }
+}
+
+/// Extracts a lease from `item`, returning `None` on error
+fn extract_lease(item: &HashMap<&str, AttributeValue<'_>>) -> Option<Lease> {
+    let generation = match item.get("generation") {
+        Some(AttributeValue::Number(generation)) => generation,
+        _ => return None,
+    };
+
+    let timeout = match item.get("timeout") {
+        Some(AttributeValue::Number(timeout)) => *timeout,
+        _ => return None,
+    };
+
+    Some(Lease {
+        acquire: Instant::now(),

Review Comment:
   This method is for extracting someone else's lease, i.e. for detecting lock timeouts, and therefore should be pessimistic, i.e. start measuring the timeout from after the response.
   
   When acquiring a lease it uses an instant from before the request - https://github.com/apache/arrow-rs/pull/4918/files/d9aae852961a346181b2fbf26696cc9ae29185f0#diff-5a8585cdad662383c911426918d89de6d4b7ed13b975767c96ecac30d6e0c227R285



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] DynamoDB Coordination for AmazonS3 (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1354662376


##########
object_store/src/aws/copy.rs:
##########
@@ -39,12 +39,64 @@ pub enum S3CopyIfNotExists {
     ///
     /// [`ObjectStore::copy_if_not_exists`]: crate::ObjectStore::copy_if_not_exists
     Header(String, String),
+    /// The name of a DynamoDB table to use for coordination
+    ///
+    /// Encoded as `dynamodb:<TABLE_NAME>` ignoring whitespace
+    ///
+    /// This will use the same region, credentials and endpoint as configured for S3
+    ///
+    /// ## Limitations
+    ///
+    /// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can

Review Comment:
   This language talks about conditional operations in general, as I intend to add a `put_if_not_exists` / `create` API call as part of #4879 



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1361218038


##########
object_store/src/aws/copy.rs:
##########
@@ -39,12 +39,64 @@ pub enum S3CopyIfNotExists {
     ///
     /// [`ObjectStore::copy_if_not_exists`]: crate::ObjectStore::copy_if_not_exists
     Header(String, String),
+    /// The name of a DynamoDB table to use for coordination
+    ///
+    /// Encoded as `dynamodb:<TABLE_NAME>` ignoring whitespace
+    ///
+    /// This will use the same region, credentials and endpoint as configured for S3
+    ///
+    /// ## Limitations
+    ///
+    /// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+    /// therefore race with non-conditional operations, e.g. `put`, `copy`, or conditional
+    /// operations performed by writers not configured to synchronize with DynamoDB.
+    ///
+    /// Workloads making use of this mechanism **must** ensure:
+    ///
+    /// * Conditional and non-conditional operations are not performed on the same paths
+    /// * Conditional operations are only performed via similarly configured clients
+    ///
+    /// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+    /// performance will be poor for systems that frequently rewrite the same path, instead
+    /// being optimised for systems that primarily create files with paths never used before.
+    ///
+    /// ## Locking Protocol
+    ///
+    /// The DynamoDB schema is as follows:
+    ///
+    /// * A string hash key named `"key"`
+    /// * A numeric [TTL] attribute named `"ttl"`
+    /// * A numeric attribute named `"generation"`
+    ///
+    /// The lock procedure is as follows:
+    ///
+    /// * Error if file exists in S3
+    /// * Create a corresponding record in DynamoDB with the path as the `"key"`
+    ///     * On Success: Create object in S3
+    ///     * On Conflict:
+    ///         * Periodically check if file exists in S3
+    ///         * After a 60 second timeout attempt to "claim" the lock by incrementing `"generation"`
+    ///         * GOTO start
+    ///
+    /// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+    /// requirements of synchronizing object storage.
+    ///
+    /// The major changes are:
+    ///
+    /// * Uses a monotonic generation count instead of a UUID rvn

Review Comment:
   A UUID approach would still collide, that's the whole purpose :smile: 
   
   A monotonic generation count is beneficial as it can also act as a fencing token, as a higher generation should win over a lower generation, admittedly this isn't used here but is generally good practice. Other less good reasons are a UUID is more expensive to generate, adds a dependency, and has a more expensive encoding.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362746758


##########
object_store/src/aws/copy.rs:
##########
@@ -39,12 +39,64 @@ pub enum S3CopyIfNotExists {
     ///
     /// [`ObjectStore::copy_if_not_exists`]: crate::ObjectStore::copy_if_not_exists
     Header(String, String),
+    /// The name of a DynamoDB table to use for coordination
+    ///
+    /// Encoded as `dynamodb:<TABLE_NAME>` ignoring whitespace
+    ///
+    /// This will use the same region, credentials and endpoint as configured for S3
+    ///
+    /// ## Limitations
+    ///
+    /// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+    /// therefore race with non-conditional operations, e.g. `put`, `copy`, or conditional
+    /// operations performed by writers not configured to synchronize with DynamoDB.
+    ///
+    /// Workloads making use of this mechanism **must** ensure:
+    ///
+    /// * Conditional and non-conditional operations are not performed on the same paths
+    /// * Conditional operations are only performed via similarly configured clients
+    ///
+    /// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+    /// performance will be poor for systems that frequently rewrite the same path, instead
+    /// being optimised for systems that primarily create files with paths never used before.
+    ///
+    /// ## Locking Protocol
+    ///
+    /// The DynamoDB schema is as follows:
+    ///
+    /// * A string hash key named `"key"`
+    /// * A numeric [TTL] attribute named `"ttl"`
+    /// * A numeric attribute named `"generation"`
+    ///
+    /// The lock procedure is as follows:
+    ///
+    /// * Error if file exists in S3
+    /// * Create a corresponding record in DynamoDB with the path as the `"key"`
+    ///     * On Success: Create object in S3
+    ///     * On Conflict:
+    ///         * Periodically check if file exists in S3
+    ///         * After a 60 second timeout attempt to "claim" the lock by incrementing `"generation"`
+    ///         * GOTO start
+    ///
+    /// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+    /// requirements of synchronizing object storage.
+    ///
+    /// The major changes are:
+    ///
+    /// * Uses a monotonic generation count instead of a UUID rvn

Review Comment:
   DynamoDB will ensure only a single one succeeds at claiming the lock



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1361232572


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   Oh no, this is just to clean up afterwards, the lease timeout is 60 seconds and is the longest anyone would have to wait in the event of a failure where a writer fails to persist following creating the lock



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362810361


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   The 1 hour timeout is just a garbage collection process that cleans out records that are no longer needed, think of it like a GC, it could be removed and the only impact would be a slightly larger DynamoDb storage bill. I reworded things in the latest PR to hopefully make this a bit clearer



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362810361


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   The 1 hour timeout is just a garbage collection process that cleans out locks that are no longer needed, think of it like a GC, it could be removed and the only impact would be a slightly larger DynamoDb storage bill. I reworded things in the latest PR to hopefully make this a bit clearer



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1435293828


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,567 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+use chrono::Utc;
+use reqwest::{Response, StatusCode};
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::aws::AwsCredential;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "ConditionalCheckFailedException";
+
+const STORE: &str = "DynamoDB";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, `delete`, or
+/// conditional operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently delete and then create
+/// objects at the same path, instead being optimised for systems that primarily create
+/// files with paths never used before, or perform conditional updates to existing files
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),

Review Comment:
   The `etag` functionality will be utilised in a follow up PR to add condition PUT



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1435277993


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,567 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+use chrono::Utc;
+use reqwest::{Response, StatusCode};
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::aws::AwsCredential;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "ConditionalCheckFailedException";
+
+const STORE: &str = "DynamoDB";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, `delete`, or
+/// conditional operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently delete and then create
+/// objects at the same path, instead being optimised for systems that primarily create
+/// files with paths never used before, or perform conditional updates to existing files
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),
+/// the commit protocol is as follows:
+///
+/// 1. Perform HEAD request on `path` and error on precondition mismatch
+/// 2. Create record in DynamoDB with key `{path}#{etag}` with the configured timeout
+///     1. On Success: Perform operation with the configured timeout
+///     2. On Conflict:
+///         1. Periodically re-perform HEAD request on `path` and error on precondition mismatch
+///         2. If `timeout * max_skew_rate` passed, replace the record incrementing the `"generation"`
+///             1. On Success: GOTO 2.1
+///             2. On Conflict: GOTO 2.2
+///
+/// Provided no writer modifies an object with a given `path` and `etag` without first adding a
+/// corresponding record to DynamoDB, we are guaranteed that only one writer will ever commit.
+///
+/// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+/// requirements of synchronizing object storage. The major changes are:
+///
+/// * Uses a monotonic generation count instead of a UUID rvn, as this is:
+///     * Cheaper to generate, serialize and compare
+///     * Cannot collide
+///     * More human readable / interpretable
+/// * Relies on [TTL] to eventually clean up old locks
+///
+/// It also draws inspiration from the DeltaLake [S3 Multi-Cluster] commit protocol, but
+/// generalised to not make assumptions about the workload and not rely on first writing
+/// to a temporary path.
+///
+/// [TTL]: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html
+/// [DynamoDB Lock Client]: https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
+/// [S3 Multi-Cluster]: https://docs.google.com/document/d/1Gs4ZsTH19lMxth4BSdwlWjUNR-XhKHicDvBjd2RqNd8/edit#heading=h.mjjuxw9mcz9h
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct DynamoCommit {
+    table_name: String,
+    /// The number of milliseconds a lease is valid for
+    timeout: u64,
+    /// The maximum clock skew rate tolerated by the system
+    max_clock_skew_rate: u32,
+    /// The length of time a record will be retained in DynamoDB before being cleaned up
+    ///
+    /// This is purely an optimisation to avoid indefinite growth of the DynamoDB table
+    /// and does not impact how long clients may wait to acquire a lock
+    ttl: Duration,
+    /// The backoff duration before retesting a condition
+    test_interval: Duration,
+}
+
+impl DynamoCommit {
+    /// Create a new [`DynamoCommit`] with a given table name
+    pub fn new(table_name: String) -> Self {
+        Self {
+            table_name,
+            timeout: 20_000,
+            max_clock_skew_rate: 3,
+            ttl: Duration::from_secs(60 * 60),
+            test_interval: Duration::from_millis(100),
+        }
+    }
+
+    /// Overrides the lock timeout.
+    ///
+    /// A longer lock timeout reduces the probability of spurious commit failures and multi-writer
+    /// races, but will increase the time that writers must wait to reclaim a lock lost. The
+    /// default value of 20 seconds should be appropriate for must use-cases.
+    pub fn with_timeout(mut self, millis: u64) -> Self {
+        self.timeout = millis;
+        self
+    }
+
+    /// The maximum clock skew rate tolerated by the system.
+    ///
+    /// An environment in which the clock on the fastest node ticks twice as fast as the slowest
+    /// node, would have a clock skew rate of 2. The default value of 3 should be appropriate
+    /// for most environments.
+    pub fn with_max_clock_skew_rate(mut self, rate: u32) -> Self {
+        self.max_clock_skew_rate = rate;
+        self
+    }
+
+    /// The length of time a record should be retained in DynamoDB before being cleaned up
+    ///
+    /// This should be significantly larger than the configured lock timeout, with the default
+    /// value of 1 hour appropriate for most use-cases.
+    pub fn with_ttl(mut self, ttl: Duration) -> Self {
+        self.ttl = ttl;
+        self
+    }
+
+    /// Returns the name of the DynamoDB table.
+    pub(crate) fn table_name(&self) -> &str {
+        &self.table_name
+    }
+
+    pub(crate) async fn copy_if_not_exists(
+        &self,
+        client: &S3Client,
+        from: &Path,
+        to: &Path,
+    ) -> Result<()> {
+        check_not_exists(client, to).await?;
+
+        let mut previous_lease = None;
+
+        loop {
+            let existing = previous_lease.as_ref();
+            match self.try_lock(client, to.as_ref(), existing).await? {
+                TryLockResult::Ok(lease) => {
+                    let fut = client.copy_request(from, to).send();
+                    let expiry = lease.acquire + lease.timeout;
+                    return match tokio::time::timeout_at(expiry.into(), fut).await {
+                        Ok(Ok(_)) => Ok(()),
+                        Ok(Err(e)) => Err(e.into()),
+                        Err(_) => Err(Error::Generic {
+                            store: "DynamoDB",
+                            source: format!(
+                                "Failed to perform copy operation in {} milliseconds",
+                                self.timeout
+                            )
+                            .into(),
+                        }),
+                    };
+                }
+                TryLockResult::Conflict(conflict) => {
+                    let mut interval = tokio::time::interval(self.test_interval);
+                    let expiry = conflict.timeout * self.max_clock_skew_rate;
+                    loop {
+                        interval.tick().await;
+                        check_not_exists(client, to).await?;
+                        if conflict.acquire.elapsed() > expiry {
+                            previous_lease = Some(conflict);
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    /// Retrieve a lock, returning an error if it doesn't exist
+    async fn get_lock(&self, s3: &S3Client, key: &str) -> Result<Lease> {
+        let key_attributes = [("key", AttributeValue::String(key))];
+        let req = GetItem {
+            table_name: &self.table_name,
+            key: Map(&key_attributes),
+        };
+        let credential = s3.config.get_credential().await?;
+
+        let resp = self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.GetItem", req)
+            .await
+            .map_err(|e| e.error(STORE, key.to_string()))?;
+
+        let body = resp.bytes().await.map_err(|e| Error::Generic {
+            store: STORE,
+            source: Box::new(e),
+        })?;
+
+        let response: GetItemResponse<'_> =
+            serde_json::from_slice(body.as_ref()).map_err(|e| Error::Generic {
+                store: STORE,
+                source: Box::new(e),
+            })?;
+
+        extract_lease(&response.item).ok_or_else(|| Error::NotFound {
+            path: key.into(),
+            source: "DynamoDB GetItem returned no items".to_string().into(),
+        })
+    }
+
+    /// Attempt to acquire a lock, reclaiming an existing lease if provided
+    async fn try_lock(
+        &self,
+        s3: &S3Client,
+        key: &str,
+        existing: Option<&Lease>,
+    ) -> Result<TryLockResult> {
+        let attributes;
+        let (next_gen, condition_expression, expression_attribute_values) = match existing {
+            None => (0_u64, "attribute_not_exists(#pk)", Map(&[])),
+            Some(existing) => {
+                attributes = [(":g", AttributeValue::Number(existing.generation))];
+                (
+                    existing.generation.checked_add(1).unwrap(),
+                    "attribute_exists(#pk) AND generation = :g",
+                    Map(attributes.as_slice()),
+                )
+            }
+        };
+
+        let ttl = (Utc::now() + self.ttl).timestamp();
+        let items = [
+            ("key", AttributeValue::String(key)),
+            ("generation", AttributeValue::Number(next_gen)),
+            ("timeout", AttributeValue::Number(self.timeout)),
+            ("ttl", AttributeValue::Number(ttl as _)),
+        ];
+        let names = [("#pk", "key")];
+
+        let req = PutItem {
+            table_name: &self.table_name,
+            condition_expression,
+            expression_attribute_values,
+            expression_attribute_names: Map(&names),
+            item: Map(&items),
+            return_values: None,
+            return_values_on_condition_check_failure: Some(ReturnValues::AllOld),
+        };
+
+        let credential = s3.config.get_credential().await?;
+
+        let acquire = Instant::now();
+        match self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.PutItem", req)
+            .await
+        {
+            Ok(_) => Ok(TryLockResult::Ok(Lease {
+                acquire,
+                generation: next_gen,
+                timeout: Duration::from_millis(self.timeout),
+            })),
+            Err(e) => match parse_error_response(&e) {
+                Some(e) if e.error.ends_with(CONFLICT) => match extract_lease(&e.item) {
+                    Some(lease) => Ok(TryLockResult::Conflict(lease)),
+                    // ReturnValuesOnConditionCheckFailure is a relatively recent addition

Review Comment:
   An update here is that dynamodb-local does finally support this - https://aws.amazon.com/about-aws/whats-new/2023/12/amazon-dynamodb-local-two-api-features/
   
   However, it would appear localstack still does not



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold merged PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1361218707


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   The problem with such a long timeout is it will render the object effectively read only for an hour on failure scenarios -- if this was used as a table provider or something similar, I think it would result in a substantial and prolonged outage



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362817646


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,416 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "com.amazonaws.dynamodb.v20120810#ConditionalCheckFailedException";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, or conditional
+/// operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently rewrite the same path, instead
+/// being optimised for systems that primarily create files with paths never used before.
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),
+/// the commit protocol is as follows:
+///
+/// 1. Perform HEAD request on `path` and error on precondition mismatch
+/// 2. Create record in DynamoDB with key `{path}#{etag}` with the configured timeout
+///     1. On Success: Perform operation with the configured timeout
+///     2. On Conflict:
+///         1. Periodically re-perform HEAD request on `path` and error on precondition mismatch
+///         2. If etag changed, GOTO 2.
+///         3. If `timeout * max_skew_rate` passed, replace the record incrementing the `"generation"`
+///             1. On Success: GOTO 2.1
+///             2. On Conflict: GOTO 2.2
+///
+/// Provided no writer modifies an object with a given `path` and `etag` without first adding a
+/// corresponding record to DynamoDB, we are guaranteed that only one writer will ever commit.
+///
+/// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+/// requirements of synchronizing object storage. The major changes are:
+///
+/// * Uses a monotonic generation count instead of a UUID rvn, as this is:
+///     * Cheaper to generate, serialize and compare
+///     * Cannot collide
+///     * More human readable / interpretable
+/// * Relies on [TTL] to eventually clean up old locks
+///
+/// It also draws inspiration from the DeltaLake [S3 Multi-Cluster] commit protocol, but
+/// generalised to not make assumptions about the workload and not rely on first writing
+/// to a temporary path.
+///
+/// [TTL]: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html
+/// [DynamoDB Lock Client]: https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
+/// [S3 Multi-Cluster]: https://docs.google.com/document/d/1Gs4ZsTH19lMxth4BSdwlWjUNR-XhKHicDvBjd2RqNd8/edit#heading=h.mjjuxw9mcz9h
+#[derive(Debug, Clone)]
+pub struct DynamoCommit {
+    table_name: String,
+    /// The number of seconds a lease is valid for
+    timeout: usize,
+    /// The maximum clock skew rate tolerated by the system
+    max_clock_skew_rate: u32,
+    /// The length of time a record will be retained in DynamoDB before being cleaned up
+    ///
+    /// This is purely an optimisation to avoid indefinite growth of the DynamoDB table

Review Comment:
   👍 



##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,416 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "com.amazonaws.dynamodb.v20120810#ConditionalCheckFailedException";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, or conditional
+/// operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently rewrite the same path, instead
+/// being optimised for systems that primarily create files with paths never used before.
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),
+/// the commit protocol is as follows:
+///
+/// 1. Perform HEAD request on `path` and error on precondition mismatch
+/// 2. Create record in DynamoDB with key `{path}#{etag}` with the configured timeout
+///     1. On Success: Perform operation with the configured timeout
+///     2. On Conflict:
+///         1. Periodically re-perform HEAD request on `path` and error on precondition mismatch
+///         2. If etag changed, GOTO 2.
+///         3. If `timeout * max_skew_rate` passed, replace the record incrementing the `"generation"`
+///             1. On Success: GOTO 2.1
+///             2. On Conflict: GOTO 2.2
+///
+/// Provided no writer modifies an object with a given `path` and `etag` without first adding a
+/// corresponding record to DynamoDB, we are guaranteed that only one writer will ever commit.
+///
+/// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+/// requirements of synchronizing object storage. The major changes are:
+///
+/// * Uses a monotonic generation count instead of a UUID rvn, as this is:
+///     * Cheaper to generate, serialize and compare
+///     * Cannot collide
+///     * More human readable / interpretable
+/// * Relies on [TTL] to eventually clean up old locks
+///
+/// It also draws inspiration from the DeltaLake [S3 Multi-Cluster] commit protocol, but
+/// generalised to not make assumptions about the workload and not rely on first writing
+/// to a temporary path.
+///
+/// [TTL]: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html
+/// [DynamoDB Lock Client]: https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
+/// [S3 Multi-Cluster]: https://docs.google.com/document/d/1Gs4ZsTH19lMxth4BSdwlWjUNR-XhKHicDvBjd2RqNd8/edit#heading=h.mjjuxw9mcz9h
+#[derive(Debug, Clone)]
+pub struct DynamoCommit {
+    table_name: String,
+    /// The number of seconds a lease is valid for
+    timeout: usize,
+    /// The maximum clock skew rate tolerated by the system
+    max_clock_skew_rate: u32,
+    /// The length of time a record will be retained in DynamoDB before being cleaned up
+    ///
+    /// This is purely an optimisation to avoid indefinite growth of the DynamoDB table

Review Comment:
   👍 



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1361232572


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   Oh no, this is just to clean up afterwards, the lease timeout is 60 seconds and is the longest anyone would have to wait



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362810361


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   The 1 hour timeout is just a garbage collection process that cleans out locks that sre no longer needed, think of it like a GC, it coukd be removed and the only impact would be a slightly larger DynamoDb storage bill



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1374884987


##########
object_store/src/aws/client.rs:
##########
@@ -58,30 +58,12 @@ const VERSION_HEADER: &str = "x-amz-version-id";
 #[derive(Debug, Snafu)]
 #[allow(missing_docs)]
 pub(crate) enum Error {
-    #[snafu(display("Error performing get request {}: {}", path, source))]

Review Comment:
   These variants simply acted as an indirection to source.error, see https://github.com/apache/arrow-rs/pull/4918/commits/e4af13759dcff891b29789e0d9ea8c259c5887a2#diff-0feb099a0931110c214fa9b9c8c5528512f38ebf22448772a815baee5973b8c4L147
   
   It is simpler to skip this indirection



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1376152494


##########
.github/workflows/object_store.yml:
##########
@@ -112,6 +112,7 @@ jobs:
       AWS_SECRET_ACCESS_KEY: test
       AWS_ENDPOINT: http://localhost:4566
       AWS_ALLOW_HTTP: true
+      AWS_COPY_IF_NOT_EXISTS: dynamo:test-table:2000

Review Comment:
   I originally wanted to use a much lower timeout, e.g. 100ms, but in CI this resulted in timeouts. Likely Github are significantly over-provisioning CPU on these instances, resulting in very poor predictability



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362816581


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   Thank you for the clarification -- perhaps this could be encoded in comments. 
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362746758


##########
object_store/src/aws/copy.rs:
##########
@@ -39,12 +39,64 @@ pub enum S3CopyIfNotExists {
     ///
     /// [`ObjectStore::copy_if_not_exists`]: crate::ObjectStore::copy_if_not_exists
     Header(String, String),
+    /// The name of a DynamoDB table to use for coordination
+    ///
+    /// Encoded as `dynamodb:<TABLE_NAME>` ignoring whitespace
+    ///
+    /// This will use the same region, credentials and endpoint as configured for S3
+    ///
+    /// ## Limitations
+    ///
+    /// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+    /// therefore race with non-conditional operations, e.g. `put`, `copy`, or conditional
+    /// operations performed by writers not configured to synchronize with DynamoDB.
+    ///
+    /// Workloads making use of this mechanism **must** ensure:
+    ///
+    /// * Conditional and non-conditional operations are not performed on the same paths
+    /// * Conditional operations are only performed via similarly configured clients
+    ///
+    /// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+    /// performance will be poor for systems that frequently rewrite the same path, instead
+    /// being optimised for systems that primarily create files with paths never used before.
+    ///
+    /// ## Locking Protocol
+    ///
+    /// The DynamoDB schema is as follows:
+    ///
+    /// * A string hash key named `"key"`
+    /// * A numeric [TTL] attribute named `"ttl"`
+    /// * A numeric attribute named `"generation"`
+    ///
+    /// The lock procedure is as follows:
+    ///
+    /// * Error if file exists in S3
+    /// * Create a corresponding record in DynamoDB with the path as the `"key"`
+    ///     * On Success: Create object in S3
+    ///     * On Conflict:
+    ///         * Periodically check if file exists in S3
+    ///         * After a 60 second timeout attempt to "claim" the lock by incrementing `"generation"`
+    ///         * GOTO start
+    ///
+    /// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+    /// requirements of synchronizing object storage.
+    ///
+    /// The major changes are:
+    ///
+    /// * Uses a monotonic generation count instead of a UUID rvn

Review Comment:
   DynamoDB will ensure only a single one succeeds at claiming the lock, as whichever wins will then increment the generation breaking the conditional expression of the other.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362748081


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   > this is the scenario when the whole table would be locked
   
   For 60 seconds and then the other writer will detect a stale lock, and reclaim it?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362745234


##########
object_store/src/aws/copy.rs:
##########
@@ -39,12 +39,64 @@ pub enum S3CopyIfNotExists {
     ///
     /// [`ObjectStore::copy_if_not_exists`]: crate::ObjectStore::copy_if_not_exists
     Header(String, String),
+    /// The name of a DynamoDB table to use for coordination
+    ///
+    /// Encoded as `dynamodb:<TABLE_NAME>` ignoring whitespace
+    ///
+    /// This will use the same region, credentials and endpoint as configured for S3
+    ///
+    /// ## Limitations
+    ///
+    /// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+    /// therefore race with non-conditional operations, e.g. `put`, `copy`, or conditional
+    /// operations performed by writers not configured to synchronize with DynamoDB.
+    ///
+    /// Workloads making use of this mechanism **must** ensure:
+    ///
+    /// * Conditional and non-conditional operations are not performed on the same paths
+    /// * Conditional operations are only performed via similarly configured clients
+    ///
+    /// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+    /// performance will be poor for systems that frequently rewrite the same path, instead
+    /// being optimised for systems that primarily create files with paths never used before.
+    ///
+    /// ## Locking Protocol
+    ///
+    /// The DynamoDB schema is as follows:
+    ///
+    /// * A string hash key named `"key"`
+    /// * A numeric [TTL] attribute named `"ttl"`
+    /// * A numeric attribute named `"generation"`
+    ///
+    /// The lock procedure is as follows:
+    ///
+    /// * Error if file exists in S3
+    /// * Create a corresponding record in DynamoDB with the path as the `"key"`
+    ///     * On Success: Create object in S3
+    ///     * On Conflict:
+    ///         * Periodically check if file exists in S3
+    ///         * After a 60 second timeout attempt to "claim" the lock by incrementing `"generation"`
+    ///         * GOTO start
+    ///
+    /// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+    /// requirements of synchronizing object storage.
+    ///
+    /// The major changes are:
+    ///
+    /// * Uses a monotonic generation count instead of a UUID rvn

Review Comment:
   I was thinking collision of concurrent writers (different processes)



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1362746511


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,333 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, Result};
+use chrono::Utc;
+use reqwest::StatusCode;
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+/// The timeout for a lease operation
+const LEASE_TIMEOUT: Duration = Duration::from_secs(20);
+
+/// The length of time a lease is valid for
+///
+/// This should be a multiple of [`LEASE_TIMEOUT`] where the multiple determines the maximum
+/// clock skew rate tolerated by the system
+const LEASE_EXPIRY: Duration = Duration::from_secs(60);
+
+/// The TTL offset to encode in DynamoDB
+///
+/// This should be significantly larger than [`LEASE_EXPIRY`] to allow for clock skew
+const LEASE_TTL: Duration = Duration::from_secs(60 * 60);

Review Comment:
   >  failure where a writer fails to persist following creating the lock
   
   Right, exactly -- this is the scenario when the whole table would be locked -- it requires a failure at the "right" time but it would be very bad



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "roeap (via GitHub)" <gi...@apache.org>.
roeap commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1435322170


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,567 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+use chrono::Utc;
+use reqwest::{Response, StatusCode};
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::aws::AwsCredential;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "ConditionalCheckFailedException";
+
+const STORE: &str = "DynamoDB";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, `delete`, or
+/// conditional operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently delete and then create
+/// objects at the same path, instead being optimised for systems that primarily create
+/// files with paths never used before, or perform conditional updates to existing files
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),

Review Comment:
   whenever we did copy_if_not exists, conditional `PUT` is the thing we actually wanted to do 😆 



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] Implement `copy_if_not_exist` for `AmazonS3` using DynamoDB (#4880) [arrow-rs]

Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #4918:
URL: https://github.com/apache/arrow-rs/pull/4918#discussion_r1435276250


##########
object_store/src/aws/dynamo.rs:
##########
@@ -0,0 +1,567 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! A DynamoDB based lock system
+
+use std::collections::HashMap;
+use std::time::{Duration, Instant};
+
+use chrono::Utc;
+use reqwest::{Response, StatusCode};
+use serde::ser::SerializeMap;
+use serde::{Deserialize, Serialize, Serializer};
+
+use crate::aws::client::S3Client;
+use crate::aws::credential::CredentialExt;
+use crate::aws::AwsCredential;
+use crate::client::get::GetClientExt;
+use crate::client::retry::Error as RetryError;
+use crate::client::retry::RetryExt;
+use crate::path::Path;
+use crate::{Error, GetOptions, Result};
+
+/// The exception returned by DynamoDB on conflict
+const CONFLICT: &str = "ConditionalCheckFailedException";
+
+const STORE: &str = "DynamoDB";
+
+/// A DynamoDB-based commit protocol, used to provide conditional write support for S3
+///
+/// ## Limitations
+///
+/// Only conditional operations, e.g. `copy_if_not_exists` will be synchronized, and can
+/// therefore race with non-conditional operations, e.g. `put`, `copy`, `delete`, or
+/// conditional operations performed by writers not configured to synchronize with DynamoDB.
+///
+/// Workloads making use of this mechanism **must** ensure:
+///
+/// * Conditional and non-conditional operations are not performed on the same paths
+/// * Conditional operations are only performed via similarly configured clients
+///
+/// Additionally as the locking mechanism relies on timeouts to detect stale locks,
+/// performance will be poor for systems that frequently delete and then create
+/// objects at the same path, instead being optimised for systems that primarily create
+/// files with paths never used before, or perform conditional updates to existing files
+///
+/// ## Commit Protocol
+///
+/// The DynamoDB schema is as follows:
+///
+/// * A string hash key named `"key"`
+/// * A numeric [TTL] attribute named `"ttl"`
+/// * A numeric attribute named `"generation"`
+/// * A numeric attribute named `"timeout"`
+///
+/// To perform a conditional operation on an object with a given `path` and `etag` (if exists),
+/// the commit protocol is as follows:
+///
+/// 1. Perform HEAD request on `path` and error on precondition mismatch
+/// 2. Create record in DynamoDB with key `{path}#{etag}` with the configured timeout
+///     1. On Success: Perform operation with the configured timeout
+///     2. On Conflict:
+///         1. Periodically re-perform HEAD request on `path` and error on precondition mismatch
+///         2. If `timeout * max_skew_rate` passed, replace the record incrementing the `"generation"`
+///             1. On Success: GOTO 2.1
+///             2. On Conflict: GOTO 2.2
+///
+/// Provided no writer modifies an object with a given `path` and `etag` without first adding a
+/// corresponding record to DynamoDB, we are guaranteed that only one writer will ever commit.
+///
+/// This is inspired by the [DynamoDB Lock Client] but simplified for the more limited
+/// requirements of synchronizing object storage. The major changes are:
+///
+/// * Uses a monotonic generation count instead of a UUID rvn, as this is:
+///     * Cheaper to generate, serialize and compare
+///     * Cannot collide
+///     * More human readable / interpretable
+/// * Relies on [TTL] to eventually clean up old locks
+///
+/// It also draws inspiration from the DeltaLake [S3 Multi-Cluster] commit protocol, but
+/// generalised to not make assumptions about the workload and not rely on first writing
+/// to a temporary path.
+///
+/// [TTL]: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html
+/// [DynamoDB Lock Client]: https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
+/// [S3 Multi-Cluster]: https://docs.google.com/document/d/1Gs4ZsTH19lMxth4BSdwlWjUNR-XhKHicDvBjd2RqNd8/edit#heading=h.mjjuxw9mcz9h
+#[derive(Debug, Clone)]
+pub struct DynamoCommit {
+    table_name: String,
+    /// The number of milliseconds a lease is valid for
+    timeout: u64,
+    /// The maximum clock skew rate tolerated by the system
+    max_clock_skew_rate: u32,
+    /// The length of time a record will be retained in DynamoDB before being cleaned up
+    ///
+    /// This is purely an optimisation to avoid indefinite growth of the DynamoDB table
+    /// and does not impact how long clients may wait to acquire a lock
+    ttl: Duration,
+    /// The backoff duration before retesting a condition
+    test_interval: Duration,
+}
+
+impl DynamoCommit {
+    /// Create a new [`DynamoCommit`] with a given table name
+    pub fn new(table_name: String) -> Self {
+        Self {
+            table_name,
+            timeout: 20_000,
+            max_clock_skew_rate: 3,
+            ttl: Duration::from_secs(60 * 60),
+            test_interval: Duration::from_millis(100),
+        }
+    }
+
+    /// Overrides the lock timeout.
+    ///
+    /// A longer lock timeout reduces the probability of spurious commit failures and multi-writer
+    /// races, but will increase the time that writers must wait to reclaim a lock lost. The
+    /// default value of 20 seconds should be appropriate for must use-cases.
+    pub fn with_timeout(mut self, millis: u64) -> Self {
+        self.timeout = millis;
+        self
+    }
+
+    /// The maximum clock skew rate tolerated by the system.
+    ///
+    /// An environment in which the clock on the fastest node ticks twice as fast as the slowest
+    /// node, would have a clock skew rate of 2. The default value of 3 should be appropriate
+    /// for most environments.
+    pub fn with_max_clock_skew_rate(mut self, rate: u32) -> Self {
+        self.max_clock_skew_rate = rate;
+        self
+    }
+
+    /// The length of time a record should be retained in DynamoDB before being cleaned up
+    ///
+    /// This should be significantly larger than the configured lock timeout, with the default
+    /// value of 1 hour appropriate for most use-cases.
+    pub fn with_ttl(mut self, ttl: Duration) -> Self {
+        self.ttl = ttl;
+        self
+    }
+
+    /// Returns the name of the DynamoDB table.
+    pub(crate) fn table_name(&self) -> &str {
+        &self.table_name
+    }
+
+    pub(crate) async fn copy_if_not_exists(
+        &self,
+        client: &S3Client,
+        from: &Path,
+        to: &Path,
+    ) -> Result<()> {
+        check_not_exists(client, to).await?;
+
+        let mut previous_lease = None;
+
+        loop {
+            let existing = previous_lease.as_ref();
+            match self.try_lock(client, to.as_ref(), existing).await? {
+                TryLockResult::Ok(lease) => {
+                    let fut = client.copy_request(from, to).send();
+                    let expiry = lease.acquire + lease.timeout;
+                    return match tokio::time::timeout_at(expiry.into(), fut).await {
+                        Ok(Ok(_)) => Ok(()),
+                        Ok(Err(e)) => Err(e),
+                        Err(_) => Err(Error::Generic {
+                            store: "DynamoDB",
+                            source: format!(
+                                "Failed to perform copy operation in {} milliseconds",
+                                self.timeout
+                            )
+                            .into(),
+                        }),
+                    };
+                }
+                TryLockResult::Conflict(conflict) => {
+                    let mut interval = tokio::time::interval(self.test_interval);
+                    let expiry = conflict.timeout * self.max_clock_skew_rate;
+                    loop {
+                        interval.tick().await;
+                        check_not_exists(client, to).await?;
+                        if conflict.acquire.elapsed() > expiry {
+                            previous_lease = Some(conflict);
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    /// Retrieve a lock, returning an error if it doesn't exist
+    async fn get_lock(&self, s3: &S3Client, key: &str) -> Result<Lease> {
+        let key_attributes = [("key", AttributeValue::String(key))];
+        let req = GetItem {
+            table_name: &self.table_name,
+            key: Map(&key_attributes),
+        };
+        let credential = s3.config.get_credential().await?;
+
+        let resp = self
+            .request(s3, credential.as_deref(), "DynamoDB_20120810.GetItem", req)
+            .await
+            .map_err(|e| e.error(STORE, key.to_string()))?;
+
+        let body = resp.bytes().await.map_err(|e| Error::Generic {
+            store: STORE,
+            source: Box::new(e),
+        })?;
+
+        let response: GetItemResponse<'_> =
+            serde_json::from_slice(body.as_ref()).map_err(|e| Error::Generic {
+                store: STORE,
+                source: Box::new(e),
+            })?;
+
+        extract_lease(&response.item).ok_or_else(|| Error::NotFound {
+            path: key.into(),
+            source: "DynamoDB GetItem returned no items".to_string().into(),
+        })
+    }
+
+    /// Attempt to acquire a lock, reclaiming an existing lease if provided
+    async fn try_lock(
+        &self,
+        s3: &S3Client,
+        key: &str,
+        existing: Option<&Lease>,
+    ) -> Result<TryLockResult> {
+        let attributes;
+        let (next_gen, condition_expression, expression_attribute_values) = match existing {
+            None => (0_u64, "attribute_not_exists(#pk)", Map(&[])),
+            Some(existing) => {
+                attributes = [(":g", AttributeValue::Number(existing.generation))];
+                (
+                    existing.generation.checked_add(1).unwrap(),
+                    "attribute_exists(#pk) AND generation = :g",
+                    Map(attributes.as_slice()),
+                )
+            }
+        };
+
+        let ttl = (Utc::now() + self.ttl).timestamp();
+        let items = [
+            ("key", AttributeValue::String(key)),
+            ("generation", AttributeValue::Number(next_gen)),
+            ("timeout", AttributeValue::Number(self.timeout)),
+            ("ttl", AttributeValue::Number(ttl as _)),

Review Comment:
   It is documented here - https://github.com/apache/arrow-rs/pull/4918/files#diff-5a8585cdad662383c911426918d89de6d4b7ed13b975767c96ecac30d6e0c227R62



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org