<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Andréas Saudemont on Medium]]></title>
        <description><![CDATA[Stories by Andréas Saudemont on Medium]]></description>
        <link>https://medium.com/@asaudemont?source=rss-5aac9b3c78e5------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*-fkMFwDAlzNM_vtD.jpg</url>
            <title>Stories by Andréas Saudemont on Medium</title>
            <link>https://medium.com/@asaudemont?source=rss-5aac9b3c78e5------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 02:10:34 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@asaudemont/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com" rel="hub"/>
        <item>
            <title><![CDATA[ScyllaDB implementation: Lists in Medium’s feature store, Part 2]]></title>
            <link>https://medium.engineering/scylladb-implementation-lists-in-mediums-feature-store-part-2-905299c89392?source=rss-5aac9b3c78e5------2</link>
            <guid isPermaLink="false">https://medium.com/p/905299c89392</guid>
            <category><![CDATA[scylladb]]></category>
            <category><![CDATA[medium-engineering]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[data-modeling]]></category>
            <category><![CDATA[database-design]]></category>
            <dc:creator><![CDATA[Andréas Saudemont]]></dc:creator>
            <pubDate>Mon, 23 Sep 2024 11:25:47 GMT</pubDate>
            <atom:updated>2025-10-28T14:13:04.739Z</atom:updated>
            <content:encoded><![CDATA[<h4>Learn how we’re using ScyllaDB to build a fast and scalable data layer for lists in our feature store.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-Rl2rixzUQxMS9BThC7B_w.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/time-lapse-photography-of-tunnel-sb7RUrRMaC4">Mathew Schwartz</a> on <a href="https://unsplash.com?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h3>tl;dr</h3><p>This is the second installment of our series on the new list feature type in Medium’s feature store, which describes how we implemented the lists data layer using ScyllaDB. See <a href="https://medium.com/medium-eng/laying-the-foundations-lists-in-mediums-feature-store-part-1-8fc075b5d355"><strong>Part 1: Laying the foundations</strong></a>, the previous installment, for an introduction to the feature store and the list feature type.</p><p>We’ll first introduce ScyllaDB, a database designed for high performance and scalability, and go over the ScyllaDB concepts needed to understand the rest of this article: clusters, nodes, tables, rows, columns, partitions, secondary indexes, and time-to-live.</p><p>Then we’ll describe the ScyllaDB data model we’ve defined for lists in order to support the significant load that will come from list operations. This data model is based on a single table storing all items for all the lists managed by the feature store. The primary key of this table is designed so that most list operations can rely on a single, efficient ScyllaDB query.</p><p>Finally we’ll go over each identified list operation and detail the ScyllaDB query/queries implementing it, and describe how these queries are efficient thanks to our data model.</p><p>Let’s get started!</p><h3>About ScyllaDB</h3><p><a href="https://www.scylladb.com/">ScyllaDB</a> is a database designed for use cases that require high throughput, low latency, and high scalability, which makes it well-suited for use as the data layer of Medium’s feature store. In this section we’ll cover a few ScyllaDB concepts that you must be aware of in order to understand the rest of this article. Please refer to the following documentations to learn more:</p><ul><li><a href="https://opensource.docs.scylladb.com/stable/index.html">ScyllaDB User Guide</a> covers a wide range of topics, including <a href="https://docs.scylladb.com/stable/get-started/data-modeling/index.html">data modeling</a>, <a href="https://docs.scylladb.com/stable/get-started/query-data/index.html">queries</a>, <a href="https://opensource.docs.scylladb.com/stable/using-scylla/features.html">features</a>, etc.</li><li><a href="https://www.scylladb.com/product/technology/">ScyllaDB Architecture</a> goes deep into how ScyllaDB achieves its performance goals.</li></ul><h4>Fundamental concepts</h4><p>A <strong>cluster</strong> is the highest-level structure of a ScyllaDB database. It is a collection of interconnected <strong>nodes</strong>, each of which is a physical or virtual server storing and managing portions of the cluster’s data in order to provide high availability, scalability, performance, and fault tolerance.</p><p>A <strong>table</strong> is a two-dimensional data structure comprised of rows and columns. On the surface this is similar to tables in relational SQL databases like MySQL or PostgreSQL. One important difference, however, is that with ScyllaDB you must know your access patterns upfront in order to define a data model that’s suited for these access patterns, as ScyllaDB doesn’t support ad-hoc queries in the same way as relational databases. In particular, defining the right primary key (see below) is central to enabling efficient queries on a table.</p><p>A <strong>row</strong> represents a single record in a table. A row is a collection of one or more columns storing data related to the record. For instance, one row of the orders table could represent an order made by the “Alice” user on 2024–09–03 while another could represent an order made by the “Bob” user on 2024–08–30. Each row in a table is uniquely identified by its primary key (see below), which is composed of one or more of the row’s columns.</p><p>A <strong>column</strong> stores a single piece of data in a row. Each column in a table has an associated name and data type (BOOLEAN, INT, TEXT, etc.; <a href="https://opensource.docs.scylladb.com/stable/cql/types.html">full list here</a>) specified when the table was created. The data type of a given column is the same for all the rows with a value for that column. For instance, the orders table might have the following columns:</p><ul><li>A user_id column of type TEXT.</li><li>A date column of type TIMESTAMP.</li><li>A value column of type FLOAT.</li></ul><p>(The table likely would have some more columns, like the product that was ordered, for instance. We’ve omitted them here for readability.)</p><p>The row for an order made by the “Alice” user on Sep. 3, 2024 might then have the following column values: user_id:&quot;Alice&quot;, date:2024-09-03, and value:43.21.</p><p>The following schemas illustrate what we’ve covered so far:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3WJX6DgBrecptbGb_Gar3Q.png" /><figcaption>The fundamental ScyllaDB concepts and their relationships</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xoP-nK7CmZOrJZb8bsBMqQ.png" /><figcaption>Sample rows and columns for the ‘orders’ table</figcaption></figure><h4>Partitions and primary/partition/clustering keys</h4><p>A table is divided into multiple <strong>partitions</strong>, where each partition is mapped to a specific node of the cluster via consistent hashing. Each row of the table is stored in one of the table’s partitions, according to its partition key (see below). This allows a ScyllaDB table to store large quantities of data (think terabytes) in a scalable and efficient manner. One of the goals when defining a ScyllaDB data model is to spread your data as evenly as possible across the partitions of the table, so that requests to the table are balanced across the nodes of the cluster.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vBOa_2pGi8rp8fmrHm05Cw.png" /><figcaption>The partitions of a table are spread across the nodes of the cluster</figcaption></figure><p>The <strong>primary key</strong> of a row is used to uniquely identify the row within its table. It is composed of two parts:</p><ul><li>The <strong>partition key</strong> is used to determine the partition the row belongs to. It is mandatory and composed of one or more columns. All rows in a given partition share the same partition key value. For instance, the partition key of the orders table might be composed of the user_id column; this way all orders made by a given user are stored in the same partition, and we can expect that user_id values are diverse enough to allow data to be spread evenly across partitions.</li><li>The <strong>clustering key</strong> is used to sort the rows within their partition. It is optional and composed of zero (when absent), one, or more columns. For instance, the clustering key of the orders table might be composed of the date column, so that we can efficiently retrieve the orders of a given user between two dates.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lHQjXZX4iORV_Qlx_9BOJQ.png" /><figcaption>A sample partition for the ‘orders’ table</figcaption></figure><h4>Secondary indexes</h4><p>By default, ScyllaDB rejects queries based on a column that isn’t part of the table’s primary key, as these queries don’t have predictable performance (worst case is that they would end up scanning the whole table). A <strong>secondary index</strong> is an additional data structure attached to a table that enables efficient querying on a non-primary key column of that table. Once a secondary index has been created, ScyllaDB transparently updates this index each time a row with a value for the indexed column is inserted into, updated, or deleted from the table.</p><p>ScyllaDB supports two types of secondary indexes:</p><ul><li>A <strong>global secondary index (GSI)</strong> is managed independently of its base table. Its data is distributed across potentially different nodes from the ones storing the table’s data. GSIs are used to query data independently from the table’s partition key.</li><li>A <strong>local secondary index (LSI)</strong> is an index sharing the same partition key as its table, which results in the index data being stored in the same nodes as its table. An LSI is more efficient than a GSI for queries relying on the table’s partition key in addition to a non-primary key column, as such queries can be executed by a single node.</li></ul><p>For instance, a GSI on the orders table’s value column would allow queries like “fetch all orders with a given value” to be executed efficiently. And an LSI on the table’s partition key plus the value column would be appropriate for queries like “fetch all orders for a given user with a given value”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wBfMF45n7_qGzOF8BPFAoA.png" /><figcaption>A sample secondary index on the ‘value’ column of the ‘orders’ table</figcaption></figure><h4>Time-to-live (TTL)</h4><p>In any given row, each column that is not part of the table’s primary key can have an associated <strong>time-to-live (TTL)</strong>, defined as the time, in seconds, until the column value expires. The TTL of a column value can be set when the value is inserted or updated. Once the TTL of a column value reaches zero, ScyllaDB automatically deletes that value from the row. If all non-primary key column values in a row have been deleted via their TTL, then ScyllaDB also automatically deletes the row itself.</p><p>TTLs are especially useful when dealing with huge amounts of data in a table: by setting a TTL on each row, we help reduce the size (and thus the price) of the storage used by the table, which might otherwise grow out of control over the long run with data that we don’t actually care about.</p><h3>ScyllaDB data model for lists</h3><p>Now that we have a better understanding of ScyllaDB, let’s dive into the data model we’re using for lists. This section builds up on the notions defined in <a href="https://medium.com/medium-eng/laying-the-foundations-lists-in-mediums-feature-store-part-1-8fc075b5d355">Part 1: Laying the foundations</a>; please refer to it if you need a refresher on these.</p><h4>Goals and requirements</h4><p>The goal here is to define a ScyllaDB data model with which to store list items and that makes it possible to implement list operations in an efficient and scalable way. In particular, the data model must be able to support the significant load that will come from the Get List Items and Add List Items operations; as we’ve seen in part 1, we expect 100k to 1 million items to be fetched each second for Get List Items and 10k to 100k items to be stored each second for Add List Items.</p><p>The analysis of our use cases for lists also identified the following requirement: the data model must allow a given list to hold multiple items with the same timestamp as long as these items all have distinct values. This is needed for instance by the story_presented list feature for the user entity, which lists the IDs of the stories that were presented (via a story preview for instance) to a given user. There are various UI surfaces throughout Medium presenting multiple stories at once (the homepage for instance); clients can thus report multiple story presentations with the same timestamp.</p><h4>The ‘list_items’ table</h4><p>Our ScyllaDB data model for lists relies on the following <strong>list_items table</strong>:</p><pre>CREATE TABLE list_items (<br>  feature_key TEXT,<br>  entity_id TEXT,<br>  item_key TEXT,<br>  value BLOB,<br>  PRIMARY KEY ((feature_key, entity_id), item_key)<br>)<br>WITH CLUSTERING ORDER BY (item_key DESC)<br>  AND DEFAULT_TIME_TO_LIVE = $defaultTTL;</pre><p>This table stores all the list items for all the list features managed by the feature store. It has the following columns:</p><ul><li>feature_key: The key identifying the list feature, resulting from the concatenation of the list’s entity type, feature name, and feature version: &quot;$entityType#$featureName|$featureVersion&quot;.</li><li>entity_id: The ID of the entity the list belongs to.</li><li>item_key: The key identifying the item in the list. See below for details.</li><li>value: The bytes representation of the value of the list item. The meaning of these bytes is opaque to the data model.</li></ul><p>The <strong>partition key</strong> of the table is composed of the feature_key and entity_id columns, so that all the items of a given list are stored in the same ScyllaDB partition. The item_key column is used as the table’s <strong>clustering key</strong>, which, along with the <a href="https://opensource.docs.scylladb.com/stable/cql/ddl.html#reversing-the-clustering-order">CLUSTERING ORDER</a> option, enables efficient retrieval of list items in reverse-chronological order.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QeM6-dFNamsDtneR1BWWtw.png" /><figcaption>The structure of the ‘list_items’ table</figcaption></figure><h4>The ‘item_key’ column</h4><p>The item_key column of the list_items table holds the key identifying the item in the list it belongs to. This key is a concatenated string comprised of the following parts:</p><ul><li>The first part of the key is the string representation, in base 10, of the item’s timestamp as a number of nanoseconds since the <a href="https://en.wikipedia.org/wiki/Unix_time">Unix epoch</a>. This string is left-padded with zeroes if needed in order to reach 19 characters. (19 digits for Unix timestamps in nanoseconds cover up to November 11, 2286, which should hopefully be enough for our use cases).</li><li>The second part is the one-character separator ‘#’.</li><li>The third and last part is the <a href="https://en.wikipedia.org/wiki/MD5">MD5 hash</a> of the item’s value, encoded into <a href="https://en.wikipedia.org/wiki/Base64">Base64</a>.</li></ul><p>For instance, the following item_key value:</p><pre>1724949845430000000#cUEirgoj2hOWvLLGgJ8hrQ==</pre><p>identifies a list item with a timestamp set to August 29, 2024 at 16:44:05 UTC and a value which MD5 hash is cUEirgoj2hOWvLLGgJ8hrQ== when encoded into Base64.</p><p>The format of item_key values is designed so that <strong>items in a list are sorted following the order of their timestamp</strong> (thanks to the clustering key of the list_items table). The Get List Items operation (see below) relies on this to discard items with a timestamp older than its minTimestamp parameter; this is achieved by adding a WHERE item_key &gt;= $minTimestampStr clause, where $minTimestampStr is the string representation, as defined above, of minTimestamp.</p><p>As the item_key column is part of the table’s primary key, this format also also allows multiple items to have the same timestamp as long as the items all have distinct values — a key requirement for our system. The first part of the item_key column for these items will all have the same value (their timestamp); their last part (the MD5 hash of their value) will always be distinct.</p><p>In the pseudo-code samples below we’ll use the following functions related to the item_key column:</p><ul><li><strong>buildItemKeyTimestamp</strong> takes an item timestamp on input and returns on output the string representation of this timestamp for item_key values, as defined above.</li><li><strong>buildItemKey</strong> takes an item on input and returns on output the item_key value for this item, also as defined above.</li></ul><h4>The ‘list_items_by_value’ local secondary index</h4><p>Our ScyllaDB data model also relies on a <strong>list_items_by_value local secondary index (LSI)</strong> on the list_items table:</p><pre>CREATE INDEX list_items_by_value<br>ON list_items((feature_key, entity_id), value);</pre><p>This index on the value column is used to implement the Remove List Items with Value operation (see details on this operation below). Using a local secondary index rather than a global one ensures that the data for that index is stored on the same node as the data for the base table, which is expected to be faster than relying on a global secondary index, as noted in <a href="https://opensource.docs.scylladb.com/stable/using-scylla/local-secondary-indexes.html">the ScyllaDB documentation</a>.</p><h4>Handling TTLs for list items</h4><p>Each row of the list_items table has an associated time-to-live (TTL) value set to the duration between the expiration date of the associated item and the time at which the row was inserted into the table. An item’s expiration date is equal to the timestamp of the item shifted by the TTL of its list feature. ScyllaDB will automatically delete the rows with an expired TTL, thus ensuring that the size of the list_items table does not grow out of control.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BR27yjldbDK_Vu9XcvFAEw.png" /><figcaption>How TTL helps us control storage usage during and after the lifetime of a list feature</figcaption></figure><p>The list_items table is also configured with a default TTL value (represented by $defaultTTL in the <a href="https://opensource.docs.scylladb.com/stable/cql/ddl.html#create-table-statement">CREATE</a> statement above). This default TTL acts as a safeguard preventing us from inadvertently inserting rows without a TTL (when running backfill operations for instance), which might then end up living forever in the table.</p><h4>Side notes on the ScyllaDB data model</h4><p>We collaborated with the team at ScyllaDB to define this data model. One of their solutions architects reviewed the first draft of the list_items table definition and provided useful feedback on the following topics:</p><ul><li>There is no advantage to using short column names with ScyllaDB. As we’ll see in part 3 of this series, this is different with DynamoDB.</li><li>Using a single feature_key column concatenating the entity type, feature name, and feature version is expected to be slightly faster than using distinct entity_type, feature_name, and feature_version columns.</li><li>The list_items_by_value local secondary index (LSI) will be more efficient than a plain scan of the whole table as long as we’re fetching less than 60% of the table rows via the LSI. If we go past this 60% threshold then a scan might be more appropriate.</li><li>Our data model uses both automatic row deletion via the time-to-live (TTL) feature and explicit row deletion via <a href="https://opensource.docs.scylladb.com/stable/cql/dml/delete.html">DELETE</a> queries. In some circumstances this can lead to bad performance. ScyllaDB offered to work together with us to tune table compaction once we had enough production data to work with.</li></ul><h3>Implementing list operations with ScyllaDB</h3><p>Let’s now review how each list operation is implemented on top of the ScyllaDB data model for lists we’ve just defined. See <a href="https://medium.com/medium-eng/laying-the-foundations-lists-in-mediums-feature-store-part-1-8fc075b5d355">Part 1: Laying the foundations</a> for more details on each of these operations and on their expected call rates.</p><h4>Metadata-related operations</h4><p>The <strong>Create List Feature</strong> and <strong>Create List Feature Version</strong> operations are fully handled by the existing metadata layer of the feature store; they are independent from the lists data model, so we won’t talk about them here.</p><p>The <strong>Delete List Feature</strong> and <strong>Delete List Feature Version</strong> operations also primarily concern the metadata layer of the feature store. Ideally these operations would initiate the deletion of the associated items from the list_items table (i.e. all items for all lists for all entities for a given feature name and optional version). These item deletions have however no efficient implementation in our data model, so the Delete List Feature and Delete List Feature Version operations do not initiate them. This is an accepted limitation: the time-to-live associated with each item in the list_items table ensures that items from deleted lists will be automatically expunged from the table at some point.</p><h4>Get List Items</h4><p>This operation retrieves items in a given list. It has the following input parameters:</p><ul><li>entityType: The type of the entity the list belongs to.</li><li>entityID: The identifier of the entity the list belongs to.</li><li>featureName: The name of the list feature.</li><li>featureVersion: The version of the list feature (optional, defaults to &quot;&quot;).</li><li>minTimestamp: The lower bound for the timestamp of list items to retrieve.</li><li>limit: The maximum number of list items to retrieve.</li></ul><p>On output, this operation returns the items of the list identified by the entityType, entityID, featureName, and featureVersion parameters. Items are returned in the reverse chronological order of their timestamps, starting with the item with highest timestamp. Items with a timestamp older than minTimestamp are discarded. And the operation returns at most limit items.</p><p>The ScyllaDB query for the Get List Items operation is as follows (where $<em>param</em> placeholders are expanded to the value of the corresponding <em>param</em> input parameter):</p><pre>SELECT value, item_key<br>FROM list_items<br>WHERE feature_key = &#39;$entityType#$featureName|$featureVersion&#39;<br>  AND entity_id = $entityID<br>  AND item_key &gt;= ${buildItemKeyTimestamp(minTimestamp)}<br>ORDER BY item_key DESC<br>LIMIT $limit;</pre><p>The partition key of the list_items table (feature_key + entity_id) ensures that this query hits a single ScyllaDB partition for maximum efficiency. And the table’s clustering key (item_key, which value starts with the item’s timestamp) is used to both (a) sort items following the reverse chronological order of their timestamps, taking advantage of the “CLUSTERING ORDER” table option (see the list_items table definition above), and (b) discard items older than minTimestamp.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*USgCnftl98-91GrXvZQ5CQ.png" /><figcaption>Sample Get List Items operation</figcaption></figure><h4>Add List Items</h4><p>This operation adds a set of items to a given list. It has the following input parameters:</p><ul><li>entityType: The type of the entity the list belongs to.</li><li>entityID: The identifier of the entity the list belongs to.</li><li>featureName: The name of the list feature.</li><li>featureVersion: The version of the list feature (optional, defaults to &quot;&quot;).</li><li>items: The set of items to add. Each item is described by its value and timestamp.</li></ul><p>The Add List Items operation returns nothing.</p><p>It is implemented as follows:</p><pre>BEGIN BATCH<br>  -- for each $item in $items:<br>  INSERT INTO list_items(feature_key, entity_id, item_key, value)<br>  VALUES (<br>    &#39;$entityType#$featureName|$featureVersion&#39;,<br>    $entityID,<br>    ${buildItemKey(item)},<br>    ${item.Value},<br>  )<br>  USING TTL ${item.Timestamp + ttl - now};<br>APPLY BATCH;</pre><p>Each item is added to the table with an <a href="https://opensource.docs.scylladb.com/stable/cql/dml/insert.html">INSERT</a> statement. All the INSERT statements are sent and executed through a single <a href="https://opensource.docs.scylladb.com/stable/cql/dml/batch.html">BATCH</a> statement. The batch is performed as <a href="https://opensource.docs.scylladb.com/stable/cql/dml/batch.html#unlogged-batches">logged</a> (the default behavior) to ensure that either all insertions complete or none do; this atomic behavior is made possible by the fact that all insertions are targeting the same partition (defined by the feature_key and entity_id columns).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9m2mAOb-X6gAQnPs1F60Xw.png" /><figcaption>Sample Add List Items operation</figcaption></figure><h4>Remove List Items with Value</h4><p>This operation removes all items with a given value in a list. It has the following input parameters:</p><ul><li>entityType: The type of the entity the list belongs to.</li><li>entityID: The identifier of the entity the list belongs to.</li><li>featureName: The name of the list feature.</li><li>featureVersion: The version of the list feature (optional, defaults to &quot;&quot;).</li><li>value: The value to remove.</li></ul><p>The Remove List Items with Value operation returns nothing.</p><p>Unlike all other list operations, which are implemented with a single request to ScyllaDB, the Remove List Items with Value operation has to go through two steps in sequence. The <strong>first step</strong> runs the following ScyllaDB query to fetch the item_key values of the items to delete:</p><pre>SELECT item_key<br>FROM list_items<br>WHERE feature_key = &#39;$entityType#$featureName|$featureVersion&#39;<br>  AND entity_id = $entityID<br>  AND value = $value;</pre><p>This first query relies on the list_items_by_value local secondary index on the list_items table to efficiently identify the items with the specified value. Using this index is expected to be faster than scanning the table as the query is highly selective: the number of list items with the specified value should be very low compared to the total number of list items.</p><p>Once the item_key values have been retrieved, the <strong>second step</strong> runs batches of <a href="https://opensource.docs.scylladb.com/stable/cql/dml/delete.html">DELETE</a> statements to delete the items:</p><pre>-- for each batch of item_key values:<br>DELETE FROM list_items<br>WHERE feature_key = &#39;$entityType#$featureName|$featureVersion&#39;<br>  AND entity_id = $entityID<br>  AND item_key IN ($itemKeyBatch);</pre><p>Each batch contains at most 10 item_key values. This approach is a middle ground between (a) running a single DELETE statement with all the (unbounded) item_key values in the “WHERE … IN …” clause and (b) running one DELETE statement per item to delete. Both (a) and (b) are expected to have performances that degrade non-linearly as the number of items to delete increases.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_8u3Anj0VlpNMdWfSm0T4Q.png" /><figcaption>Sample Remove List Items with Value operation</figcaption></figure><h4>Remove All List Items</h4><p>This operation removes all items in a list. It has the following input parameters:</p><ul><li>entityType: The type of the entity the list belongs to.</li><li>entityID: The identifier of the entity the list belongs to.</li><li>featureName: The name of the list feature.</li><li>featureVersion: The version of the list feature (optional, defaults to &quot;&quot;).</li></ul><p>The Remove All List Items operation returns nothing.</p><p>It is implemented with a single <a href="https://opensource.docs.scylladb.com/stable/cql/dml/delete.html">DELETE</a> statement relying on the partition key of the list_items table (feature_key + entity_id):</p><pre>DELETE FROM list_items<br>WHERE feature_key = &#39;$entityType#$featureName|$featureVersion&#39;<br>  AND entity_id = $entityID;</pre><p>As all the items are in the same partition, ScyllaDB is able to perform the deletion atomically: either all the rows (i.e. the whole partition) will be deleted, or none will.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1uXmoUqk9kd_rwe7iiJ-hw.png" /><figcaption>Sample Remove All List Items operation</figcaption></figure><h3>Recap and next steps</h3><p>Thank you for making it this far! We’ve covered quite a lot of ground, so let’s recap.</p><p><strong>ScyllaDB</strong> is a database designed for use cases requiring high throughput, low latency, and high scalability. In order to enable efficient queries, a ScyllaDB table must define a <strong>primary key</strong> that is appropriate for the table’s data access patterns. A primary key is composed of a <strong>partition key</strong>, which defines how the rows in the table are mapped to partitions, and an optional <strong>clustering key</strong>, which defines how rows are sorted within a partition. Data access patterns relying on a non-primary key column can be made efficient by using <strong>secondary indexes</strong>. Column values in a ScyllaDB table can have an associated <strong>time-to-live (TTL)</strong>, which is a duration after which ScyllaDB will automatically delete the value (and, potentially, the row it belongs to).</p><p>The ScyllaDB <strong>data model</strong> we’ve defined for lists in Medium’s feature store relies on <strong>a single </strong><strong>list_items table</strong> storing all the items for all the lists managed by the feature store. Each row of this table stores the data for a single list item. The table’s <strong>partition key</strong> identifies the list each item belongs to; its values are built from the list’s entity type, feature name, feature version, and entity ID. As a result, all the items of a given list are stored in the same ScyllaDB partition, which enables efficient execution of queries on that list. The table’s <strong>clustering key</strong> is designed with the following goals: (a) enable efficient retrieval of list items in reverse chronological order and (b) support the requirement stating that a given list can hold multiple items with the same timestamp as long as these items all have distinct values. The <strong>list_items_by_value secondary index</strong> enables efficient queries on the table’s value column, which isn’t part of the table’s primary key. Each row of the list_items table has an associated <strong>TTL</strong> which ensures that the size of the table does not grow out of control with data that we don’t care about anymore.</p><p>One <strong>accepted limitation</strong> of the data model is that it provides no efficient way to delete all the items associated with a given list feature or list feature version (for the Delete List Feature and Delete List Feature Version operations). The mandatory row TTLs provide a mitigation strategy by ensuring that these list items will be automatically deleted from the table at some point.</p><p><strong>List operations</strong> are relatively straightforward to implement, thanks to the data model we’ve defined. All operations except Remove List Items with Value perform a <strong>single request</strong> to the ScyllaDB cluster. <strong>Get List Items</strong> relies on the table’s partition key to identify the list and on the table’s clustering key to fetch items in reverse-chronological order with a lower bound on the item timestamps. <strong>Add List Items</strong> atomically inserts the requested list items into the table via a batch statement. <strong>Remove List Items with Value</strong> is the only operation that cannot be implemented with a single request; it first fetches the clustering key values of the items to delete, relying on the list_items_by_value secondary index, then sends batched deletion requests for these items. <strong>Remove All List Items</strong> requests all the rows with a given partition key value to be deleted, which ScyllaDB is able to perform atomically.</p><p>The next installment in the series will describe how we also used DynamoDB to implement the data layer for list features. As we’ll see, there are numerous similarities and some subtle differences between ScyllaDB and DynamoDB. Stay tuned to learn more!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=905299c89392" width="1" height="1" alt=""><hr><p><a href="https://medium.engineering/scylladb-implementation-lists-in-mediums-feature-store-part-2-905299c89392">ScyllaDB implementation: Lists in Medium’s feature store, Part 2</a> was originally published in <a href="https://medium.engineering">Medium Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Laying the foundations: Lists in Medium’s feature store, Part 1]]></title>
            <link>https://medium.engineering/laying-the-foundations-lists-in-mediums-feature-store-part-1-8fc075b5d355?source=rss-5aac9b3c78e5------2</link>
            <guid isPermaLink="false">https://medium.com/p/8fc075b5d355</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[medium-engineering]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[database-design]]></category>
            <category><![CDATA[data-modeling]]></category>
            <dc:creator><![CDATA[Andréas Saudemont]]></dc:creator>
            <pubDate>Mon, 26 Aug 2024 16:20:20 GMT</pubDate>
            <atom:updated>2024-09-23T11:35:17.751Z</atom:updated>
            <content:encoded><![CDATA[<h4>Explore the foundations of the new list feature type in Medium’s feature store.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*X5KnrfbmnJJHuhb9" /><figcaption>Photo by <a href="https://unsplash.com/photos/an-aerial-view-of-a-building-being-constructed-5ZtaGX2cnCk">Iain Kennedy</a> on Unsplash</figcaption></figure><h3>tl;dr</h3><p>This is the first installment of our series on the new list feature type in Medium’s feature store. Central to Medium’s recommendations system, the feature store handles the high-volume data used by machine learning models. The limitations of the existing relational features prompted the development of the new list feature type, which is designed to handle cross-entity relations in an efficient and scalable way.</p><p>See also <a href="https://medium.engineering/scylladb-implementation-lists-in-mediums-feature-store-part-2-905299c89392"><strong>Part 2: ScyllaDB implementation</strong></a>.</p><h3>What is the feature store?</h3><p>The <strong>feature store</strong> is a key component of Medium’s recommendation system. It functions as a repository to store features that the machine learning (ML) models use to power recommendations. It can be thought of as a database with a specialized API designed to handle the high-volume, high-throughput access patterns these ML models require.</p><p>A <strong>feature</strong> represents a property of an entity in the feature store. A feature is defined by:</p><ul><li>The <strong>entity type</strong> the feature is associated with. For instance: user, story.</li><li>Its <strong>name</strong>. For instance: is_member for the user entity type, author for the story entity type.</li><li>Its <strong>version</strong> (optional). We use feature versions to store feature values that were generated at the same time and that should be queried together.</li><li>The <strong>data type</strong> of its values. For instance: integer, string, float vector.</li></ul><p>A <strong>feature value</strong> is the value of a feature for a given <strong>entity ID</strong>. For instance, the value of the title feature for the story entity with ID badcaffe could be the “The Surprising Benefits of Reading Every Self-Help Book Backwards” string.</p><p>Medium’s feature store also supports <strong>relational features</strong>. A relational feature can have multiple values for a given entity ID; each of these values has an associated <strong>relation ID</strong>, which is the ID of the related entity, and a <strong>timestamp</strong>. For instance, the user_has_read relational feature for the story entity type relates with the user entity type and stores boolean values indicating whether and when a given user has already read a given story.</p><p>These concepts and their relationships are illustrated in the following schema:</p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/1*yIv3qUHaBzYvSrEJkkrFKA.png" /></figure><p>As we’ll describe below, the limitations of relational features were the primary driver for introducing the new list feature type.</p><h3>The list feature type</h3><p>Medium’s recommendations team had been constrained for some time by the technical limitations of relational features. Because of the data model used to store relational feature values in the database, each fetch request for a relational feature generates one database query that retrieves the entity IDs matching the request constraints, followed by one additional database query for <em>each</em> entity ID returned by the first query to retrieve the feature values for these entity IDs; obviously, these multiple queries are inefficient. The data model also makes it hard to rely on primary keys and/or indices to optimize these queries, which significantly adds to the inefficiency of relational features. In addition to that, the API exposed by the feature store to manipulate relational features is clunky and outdated.</p><p>The team thus set out to find a better way to handle cross-entity relations in the feature store. We quickly rejected the option of refactoring the existing implementation of relational features. The feature store currently handles significant volumes of relational feature values; refactoring its implementation in-place would have been costly, lengthy, and risky. We instead agreed that it would be more valuable to add a new feature type with a streamlined API and an efficient implementation, then to progressively migrate existing relational features to this new feature type.</p><p>That’s where <strong>list features</strong> came into play. A list feature has the following characteristics:</p><ul><li>Like other features in the feature store, a list feature is associated with an <strong>entity type</strong> and has a <strong>name</strong> and an optional <strong>version</strong>.</li><li>A <strong>list</strong> is the value of a list feature for a given entity ID, consisting of a collection of <strong>items</strong>.</li><li>Each item in a list stores a <strong>value</strong> and a <strong>timestamp</strong>.</li><li>A list feature has a mandatory associated <strong>time-to-live (TTL)</strong> value. Items in a list that are older (based on their timestamp) than the TTL of their list feature are considered expired and will be expunged at some point.</li><li>The data type for item values are not constrained. Two distinct item values in the same list can have <strong>different data types</strong> (integer, string, float vector, etc).</li></ul><p>The following schema illustrates the new list feature type:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BUIt4hvN7a-btKih_lNlNQ.png" /></figure><p>Let’s consider a reading_history list feature on the user entity type as an example. This list feature has a TTL of 6 months. The items of this list feature for the johndoe user ID records the IDs of the stories that this user has read in the last 6 months, along with the timestamps of when these reads occurred. The reads that were recorded more than 6 months ago are automatically deleted from the list; this helps control the storage space used by list items, so that we don’t end up storing (and paying for!) multiple years of data that we don’t need.</p><h3>Operations on list features</h3><p>After having defined the characteristics of list features, we’ve listed the operations to be supported on list features, along with the expected call rate of each of these operations. This information will be a key input when it will come to defining an efficient data model for list features (see the next installments in this series).</p><p>The operations on list features are as follows:</p><p><strong>Create List Feature</strong> — This creates a new list feature for a given entity type and with a given name and TTL. This operation is rarely used, with an expected rate of less than 1 call per day.</p><p><strong>Delete List Feature</strong> — This deletes an existing list feature, specified by its entity type and name. All the versions associated with the list feature, if any, and all the items associated with the list feature are also deleted. This operation is also rarely used, with an expected rate of less than 1 call per day.</p><p><strong>Add List Feature Version</strong> — This adds a new version to an existing list feature. Versions are usually created daily, so this operation has an expected rate of a few calls per day.</p><p><strong>Delete List Feature Version</strong> — This deletes an existing version of a list feature, along with all the items associated with this version. Versions are usually deleted a few days after they’ve been created, so this operation has an expected rate of a few calls per day.</p><p><strong>Get List Items</strong> — This retrieves the items of the list identified by its entity type, feature name, optional feature version, and entity ID. Items are returned in the reverse chronological order of their timestamps. Callers also specify a maximum age for items and a maximum number of items to retrieve. Our estimates showed that we expect callers to retrieve list data at rates comprised between 100k to 1 million items per second, and possibly more in the future. It is thus essential that the implementation of this operation is able to (a) support significant amounts of requests with low latencies and (b) scale to accommodate future traffic increases.</p><p><strong>Add List Items</strong> — This adds items (values and timestamps) to the list identified by its entity type, feature name, optional feature version, and entity ID. Estimates showed that we expect to be writing between 10k to 100k items per second, and possibly more in the future. As with the Get List Items operation, it is essential that the Add List Items implementations is efficient and able to scale in the future.</p><p><strong>Remove List Items with Value</strong> — This removes all the items with a given value from the list identified by its entity type, feature name, optional feature version, and entity ID. This operation has an expected rate of between 1k to 10k calls per second.</p><p><strong>Remove All List Items</strong> — This removes all the items from the list identified by its entity type, feature name, optional feature version, and entity ID. The expected call rate of this operation is unknown.</p><p>This is summarized in the table below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*H0gP1t6tO0YpwwpOS9s-sw.png" /></figure><h3>What’s next?</h3><p>Let’s quickly review the key points we’ve covered so far:</p><ul><li>The feature store powers Medium’s recommendations system by storing and managing features used by machine learning models.</li><li>A feature in the store is defined by its entity type, name, optional version, and data type.</li><li>Relational features handle cross-entity relations. They are limited by inefficiencies in their data model and outdated API.</li><li>We’re introducing a new list feature type to address the limitations of relational features.</li><li>Lists will store collections of items with values and timestamps and have a mandatory time-to-live (TTL) to control storage size.</li><li>The key operations on list features that require high efficiency and scalability are retrieving items from a list and adding items to a list.</li></ul><p>The next installments in this series will cover how we implemented this new list feature type. One of our goals with lists was to use them as an experiment to compare ScyllaDB (see <a href="https://medium.engineering/scylladb-implementation-lists-in-mediums-feature-store-part-2-905299c89392">part 2</a>) and DynamoDB in terms of efficiency and costs using production data. Stay tuned to learn more!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8fc075b5d355" width="1" height="1" alt=""><hr><p><a href="https://medium.engineering/laying-the-foundations-lists-in-mediums-feature-store-part-1-8fc075b5d355">Laying the foundations: Lists in Medium’s feature store, Part 1</a> was originally published in <a href="https://medium.engineering">Medium Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Fixing duplicate stories in Medium’s For You feed]]></title>
            <link>https://medium.engineering/fixing-duplicate-stories-in-mediums-for-you-feed-48e6d4e2b80d?source=rss-5aac9b3c78e5------2</link>
            <guid isPermaLink="false">https://medium.com/p/48e6d4e2b80d</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[medium-engineering]]></category>
            <dc:creator><![CDATA[Andréas Saudemont]]></dc:creator>
            <pubDate>Fri, 14 Apr 2023 07:06:42 GMT</pubDate>
            <atom:updated>2023-04-14T07:06:42.231Z</atom:updated>
            <content:encoded><![CDATA[<p>A few months ago we started getting reports of stories appearing multiple times in the For You feed on Medium mobile apps. See for instance the screenshot below, in which the “Breaking News: Stuff actually costs a lot” story is listed twice:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TJY-6lzU8z2OntuwFXDgjQ.png" /></figure><p>Instrumentation showed that there were around 4K occurrences per day of duplicate stories on iOS and around 3K occurrences per day on Android. We also received reports of duplicate stories appearing in the For You feed in the web app. So we started investigating.</p><h3>The For You feed under the hood</h3><p>Before we dive into how we fixed the issue, let’s take a look at how the For You feed works under the hood.</p><h4>Anatomy of a For You feed request</h4><p>In order to retrieve the content of the For You feed, a client app — web, iOS, or Android — performs a request to Medium’s GraphQL API layer. GraphQL then forwards that request to the rex (recommendations) service, implemented in Go, which computes the feed content (with the help of other downstream services) and returns it to GraphQL. GraphQL then forwards the response to the client app. This is summarized in the diagram below (downstream services called by the rex service aren’t represented as they don’t really matter here):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GCQ9xZWVDRXm6zEzcOr1ew.png" /></figure><p>Requests to retrieve the For You feed are also paginated, as the feed can contain hundreds of stories. When requesting a page, the client app specifies the maximum number of stories to retrieve and, optionally, the cursor returned in response to the request for the previous page. This cursor is used by the rex service as a way to identify where the next page begins.</p><p>So, conceptually, the request to retrieve the first page of the For You feed looks like this:</p><pre>forYou({limit: 10}) {<br>  # ...<br>}</pre><p>In addition to a list of the items in the page, the response to this first request specifies the cursor for the second page:</p><pre>{<br>  items: [...]<br>  nextPage: {cursor: &quot;10&quot;}<br>}</pre><p>The next request to retrieve the second page then passes this cursor information, as follows:</p><pre>forYou({limit: 10, cursor: &quot;10&quot;}) {<br>  # ...<br>}</pre><p>And the response to this second request specifies the cursor for the third page, and so on:</p><pre>{<br>  items: [...]<br>  nextPage: {cursor: &quot;20&quot;}<br>}</pre><h4>Generating and caching For You feed instances</h4><p>Conceptually, the endpoint handling For You feed requests in the rex service is implemented like this (using Go-like pseudo-code):</p><pre>f := FetchFromRedis(ctx, userID)<br>if !f {<br>    f := GenerateFeed(ctx, userID)<br>    StoreInRedis(ctx, userID, feed)<br>}<br>return ExtractPage(f, paging)</pre><p>When the For You feed is requested and no cached value is available, a new feed instance is generated by the rex service. By design, two generation operations for the same user will return two different feed instances; this ensures that you see different story recommendations when you open Medium and when you refresh the feed. Although these two feed instances will be different, they will usually contain at least some of the same stories (though in different positions in the feed).</p><p>Once a feed instance has been generated, it is then stored in a Redis cache owned by the rex service. At the time duplicate stories were reported, the key identifying the feed instance in the Redis cache was built using the following template: $userId:HOMEPAGE (this has changed since then, see below). A cached feed instance also has an associated time-to-live (TTL) value of 30 min (this also has changed since then, see below); after this TTL has been reached, Redis automatically evicts the feed instance from the cache.</p><p>Now that we understand the machinery behind the For You feed, let’s dive into the changes we brought to fix the bug.</p><h3>Change #1: Fix premature cancellation of cache store operations</h3><p>At the time the bug was reported, the rex service (implemented in Go) was delegating the storage of newly generated feed instances in the Redis cache to background <a href="https://go.dev/doc/effective_go#concurrency">goroutines</a>, without waiting for these goroutines to complete. Or, at least, that’s what we thought the rex service was doing… Even though the code was run in a background coroutine as expected, it was using the request context, a <a href="https://pkg.go.dev/context">context</a> associated with the upstream request. One of the defining characteristics of a request context is that it is canceled as soon as the request completes. This implies that the code storing feed instances in Redis would sometimes be canceled in a nondeterministic way, potentially before the Redis cache had been updated, as illustrated below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JlICNaeSKS_9H0gRMo0Ung.png" /></figure><p>This ended being one of the root causes of duplicate stories. See for instance the sequence of events represented below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7XMh0imjd92qX00bco3KWg.png" /></figure><p>When a client requests the first page of the For You feed and no feed instance is available in the cache, the rex service, as described above, generates a new feed instance A, starts a background goroutine to store feed instance A in Redis, and returns the first page of feed instance A. If the request context is canceled before the background goroutine completes its work, feed instance A ends up <em>not</em> being stored in Redis. Later, when the client requests the second page of the For You feed, the rex service generates yet another new feed instance B (because there is no feed instance in the cache), then returns the second page of feed instance B. The client thus retrieves two pages from two distinct feed instances (A and B); as we’ve seen above, these two different feed instances might contain some of the same stories, though in different positions, which would sometimes result in the same story appearing in both pages.</p><p>The fix for this issue was rather simple: create a true <a href="https://pkg.go.dev/context#Background">background context</a> and use this context, instead of the request context, to run the cache store operation in the background goroutine. This is illustrated below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sZ-0KldHsvCFnOiB8dKVpQ.png" /></figure><p>Side note: Using background goroutines to store feed instances in the cache can theoretically create race conditions when the second page of the feed is requested immediately after the first page has been returned. In practice though, the additional time costs incurred by returning the response all the way up to the client and by unmarshaling the response by the client make this an unlikely situation.</p><h3>Change #2: Ensure cached feed instances are reused when available</h3><p>As explained above, a cached feed instance is stored in Redis with a time-to-live (TTL) set to 30 min. Depending on usage patterns, this could easily result in the For You feed listing duplicate stories. Imagine a person opening Medium and starting to read stories in the first page of the For You feed. Imagine then that this person either takes more than 30 minutes to read all the stories in the first page, or is away from Medium for more than 30 minutes and then comes back to where they left. At some point the Medium app will request the second page of the For You feed. As more than 30 minutes have elapsed since the first page was requested, the feed instance that was used to return the first page has been evicted from the cache; thus the rex service generates a new feed instance and returns the second page of this new feed instance. Just as for the issue fixed by change #1, this would then sometimes result in the same story appearing in both the first and second pages. This is illustrated below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0mZHuXARPOhjRRHOjK8CXg.png" /></figure><p>We fixed this situation in two steps: first, rely on feed instance IDs across requests; second, update the TTL logic for cached For You feed instances.</p><h4>Relying on feed instance IDs across requests</h4><p>As we’ve seen earlier, clients requesting a page from the For You feed passed two parameters in the request: a limit (mandatory) and a cursor (optional); these two parameters define a view on the requested feed instance. There was however no notion of <em>which</em> feed instance was being requested. The rex service would always return a page from the <em>current</em> feed instance if there was one, or from a newly generated feed instance otherwise, in which case this feed instance would then become the new current feed instance.</p><p>In order to better support all usage patterns, we updated the request chain so that an ID uniquely identifying the feed instance was returned whenever a page from the For You feed was requested. We extended the format of the cursor parameter to include a feed instance ID; this way, a client app would (automatically, without actually knowing anything about feed instance IDs) pass the feed instance ID received in response to the request for page N when requesting page N+1. Conceptually, the cursor changed from a simple offset (&quot;10&quot;) to a tuple made of a feed instance ID and an offset ({feedId: &quot;1234&quot;, cursor: &quot;10&quot;}). And the rex service was also updated in order to take feed instance IDs into account when serving For You feed requests.</p><p>The cache logic was also updated accordingly. First, the keys used to reference feed instances in the Redis cache were updated to include the ID of the feed instance, with the following key template: $userId:HOMEPAGE:$feedId. This way, the rex service can check whether a given feed instance is available in the cache, and isn’t limited to retrieving the current feed instance. Second, whenever a new feed instance is generated, the key for the Redis entry for this feed instance is stored as the value for the Redis entry with the $userId:HOMEPAGE:current key. This provides an alias to the current feed instance, which the rex service uses when no feed instance ID is specified in the request.</p><p>With these changes, the logic for retrieving a For You feed page in the rex service became as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SDinAlR2fOL4F13V5KdTng.png" /></figure><p>With this new logic, when a feed instance ID is specified but the feed instance isn’t available in the cache (most probably because it has been evicted), a new feed instance is generated only if the request concerns the first page of the feed. Otherwise, an empty page is returned. This is the key change from the previous behavior; it ensures that clients always receive pages from the <em>same</em> feed instance which, in turn, ensures that any story appears at most once in the feed.</p><p>Note also that when no feed instance ID is specified in the request parameters, the rex service behaves in a way that is very similar to how it used to behave prior to the change: create a new feed instance and return it. This is needed for requests for the first page of the feed, which provide no cursor and thus no feed instance ID.</p><h4>Update the TTL logic for cached For You feed instances</h4><p>With the feed instance IDs changes described above in place, it was time to adjust the time-to-live values for cached feed instance IDs and for current feed instance aliases. We had two goals in mind:</p><ul><li>Use as long a TTL as possible for feed instance IDs, in order to allow users to go through their feed at their own pace.</li><li>Set a short-ish TTL for aliases to current feed instances, in order to provide some freshness when a user reopens Medium after some time.</li></ul><p>Our first attempt configured the TTL for feed instance IDs to 24 hours and the TTL for current feed instance aliases to 10 minutes. The For You feed is shown each time a logged-in user opens Medium (on web, iOS, and Android), which implies that a feed instance is cached in Redis for each active logged-in Medium user. Medium has quite a few active users, so we decided to tread carefully and activate the TTL changes for only 5% of the users. After about half a day, the memory usage for the Redis cluster looked like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FaWqyGoa5ys-5lOiFhRJoA.png" /></figure><p><em>Oops.</em></p><p>In just a few hours, memory usage of the Redis cluster doubled because of the 5% roll-out, with about half of the available memory being consumed! Obviously we would not be able to ramp up the TTL changes to 100% of our users without significantly increasing the amount of memory dedicated to the Redis cluster, which we deemed too costly compared to the benefits that would bring.</p><p>We decided to decrease the TTL for cached feed instances to 1 hour (instead of 24 hours). This seemed like an appropriate trade-off between availability of cached feed instances (doubling from the previous 30 minutes TTL) and memory usage of the Redis cluster. We first rolled out the change to 5% of our users, which resulted in a +4% increase in memory usage. The following days we ramped up the change to 25%, then 50%, and finally 100%. Max memory usage stabilized to about 45%, an acceptable +20% increase compared to memory usage prior to the changes. The graph below summarizes the roll-out phases and their impact on memory usage:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aRqcerdDJ6bV2FwA8qSxSQ.png" /></figure><h3>The outcome</h3><p>Let’s recap:</p><ul><li>We fixed a concurrency issue in the rex service preventing some feed instances from being written to the cache. This issue resulted in multiple feed instances sometimes being returned for the same feed, and thus in some stories being listed multiple times within the same feed.</li><li>We updated the cache logic in order to (a) allow multiple feed instances to be stored in the cache for the same user and (b) reference the last generated feed instance as the current one. With this new cache logic, the rex service is now able to ensure the same feed instance is used across page requests for one hour after the feed instance has been generated.</li></ul><p>These changes have been deployed iteratively across a few weeks. The graphs below show the number of occurrences of duplicate stories per day on iOS and Android, grouped by app version, around the time of the last deployment:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6PPtWnNqJKfcS_LSFT5xSA.png" /><figcaption>iOS occurrences/day</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0vUGm28byQ2ndZ2ld2DzPA.png" /><figcaption>Android occurrences/day</figcaption></figure><p>These graphs start at a time when some of the changes had already been deployed; these changes reduced the number of daily occurrences of duplicate stories from around 4K on iOS and 3K on Android to around 2K on iOS and 1K on Android. On November 24 the last change was deployed, in which the rex service returns an empty page instead of generating a new feed when a non-first page is requested on a feed instance ID that isn’t available anymore in the cache. After that the number of daily occurrences basically dropped to zero. And we haven’t received a report of a duplicate story in the For You feed since then.</p><h3>Where to go next?</h3><p>The changes made to fix the duplicate stories bug in the For You feed were successful and significantly improved the user experience. There is always room for improvement, though, and for further optimization to ensure that the For You feed continues to provide users with relevant and engaging content.</p><p>For instance, one limitation of the new caching logic is that if a user navigates back to the For You feed after the feed instance has been evicted from the cache, they will not get more stories past the ones they previously fetched (unless they refresh the whole feed). This could result in users missing out on potentially interesting content. One possible solution to this limitation is to implement a more robust caching strategy that would allow for more long-term storage of feed instances. However, this solution could come with a significant cost, as it would require scaling up memory for the Redis cache. As with any engineering problem, we would need to carefully consider the trade-offs before deciding on a solution.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=48e6d4e2b80d" width="1" height="1" alt=""><hr><p><a href="https://medium.engineering/fixing-duplicate-stories-in-mediums-for-you-feed-48e6d4e2b80d">Fixing duplicate stories in Medium’s For You feed</a> was originally published in <a href="https://medium.engineering">Medium Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A glowing progress ring with rounded ends for Android]]></title>
            <link>https://medium.com/glose-team/a-glowing-progress-ring-with-rounded-ends-for-android-865eb0161cc1?source=rss-5aac9b3c78e5------2</link>
            <guid isPermaLink="false">https://medium.com/p/865eb0161cc1</guid>
            <category><![CDATA[android]]></category>
            <dc:creator><![CDATA[Andréas Saudemont]]></dc:creator>
            <pubDate>Mon, 10 Aug 2020 12:53:12 GMT</pubDate>
            <atom:updated>2020-08-10T12:53:12.419Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O7-5QM-eUlX49BZl1Q8PXg.png" /></figure><p><em>How we created a custom Android view which draws a glowing progress ring with rounded ends.</em></p><p>With <a href="https://play.google.com/store/apps/details?id=com.glose.android">Glose</a> you can set a goal of reading a given number of pages each day. You can then follow your daily progress with the daily goal widget on the home screen:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*gN2fHgW4ZvlypBaaliIwbA.png" /><figcaption>When you haven’t reached your daily goal yet</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*SnErZXro11qrzz_LnnTvSw.png" /><figcaption>When you’ve reached or exceeded your daily goal</figcaption></figure><p>The first implementation of the widget used a circular <a href="https://developer.android.com/reference/android/widget/ProgressBar">ProgressBar</a> to represent the progress ring. This did the job but missed a few features we wanted:</p><ol><li>The ends of the progress ring should be rounded. With the circular ProgressBar the ends are flat and do not match the overall style of the app.</li><li>We should be able to use any drawable for the progress ring, like a gradient for instance, and not be limited to a solid color.</li><li>The progress ring should project a glow when you’ve exceeded your goal. The more the goal has been exceeded, the bigger the glow effect.</li></ol><p>With these features in mind, we set out to update our implementation of the daily goal widget.</p><h3>Rounding the ends</h3><p>We couldn’t find a way to create a drawable for the ProgressBar that would draw rounded ends on the progress ring. So we replaced the ProgressBar with a custom view inspired by <a href="https://stackoverflow.com/a/53830379/276074">this StackOverflow answer</a>.</p><p>This custom view sets up the two Paint objects that will be used to draw the ring:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0b5c9453fa48388606f4ace8ff01778c/href">https://medium.com/media/0b5c9453fa48388606f4ace8ff01778c/href</a></iframe><p>ringPaint is configured with the <a href="https://developer.android.com/reference/android/graphics/Paint.Cap#ROUND">ROUND</a> stroke cap, which is how the progress ring will get its ends rounded.</p><p>The drawing of the ring is then performed by the onDraw() override using simple <a href="https://developer.android.com/reference/android/graphics/Canvas#drawArc(android.graphics.RectF,%20float,%20float,%20boolean,%20android.graphics.Paint)">drawArc()</a> primitives:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4e904039d2741dc94e9d9475eabf13ee/href">https://medium.com/media/4e904039d2741dc94e9d9475eabf13ee/href</a></iframe><p>arcRect is a RectF that caches the bounds of the arc used to draw the ring. It is updated each time onSizeChanged() is called:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/73f22a5a8224e4d0d42331557095c277/href">https://medium.com/media/73f22a5a8224e4d0d42331557095c277/href</a></iframe><p>And that’s all it takes to get nice rounded ends:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*BeYTDheIvWGTQakThFsaIw.png" /><figcaption>Look ma, rounded ends!</figcaption></figure><h3>Using a drawable for the progress ring</h3><p>The progress ring is also used in a popup panel showing historical data. In this popup the ring must be drawn using a gradient that is lighter at the top and darker at the bottom.</p><p>To achieve this, we’ve updated the onDraw() method so that the arc it draws acts as a mask on top of the ring drawable:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7e1ae7bac727573850593321fca4ba5c/href">https://medium.com/media/7e1ae7bac727573850593321fca4ba5c/href</a></iframe><p>The key here is ringMaskPaint, which is used as the paint for the second <a href="https://developer.android.com/reference/android/graphics/Canvas#saveLayer(android.graphics.RectF,%20android.graphics.Paint)">Canvas.saveLayer()</a> call. It is configured with the <a href="https://developer.android.com/reference/android/graphics/PorterDuff.Mode#MULTIPLY">PorterDuff.Mode.MULTIPLY</a> <a href="https://developer.android.com/reference/android/graphics/Xfermode">transfer mode</a>, and as a result anything that is drawn in this layer (the progress ring) will act as a mask over what is drawn in the layer below (the ring drawable). See <a href="http://ssp.impulsetrain.com/porterduff.html">Porter/Duff Compositing and Blend Modes</a> by Søren Sandmann Pedersen for an illustrated explanation of these concepts.</p><p>The onSizeChanged() method is also modified to adjust the bounds of ringDrawable appropriately:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8097eabc5212d488ab289de4351a6a10/href">https://medium.com/media/8097eabc5212d488ab289de4351a6a10/href</a></iframe><p>And here is the result:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/451/1*GcUX_3t65rLwJvsdBUPf9Q.png" /><figcaption>Using a gradient to draw the ring</figcaption></figure><h3>Adding the glow effect</h3><p>The progress ring is expected to glow when you’ve exceeded your reading goal, and the more you’ve exceeded your goal, the more the ring glows. We achieve this in the onDraw() override by drawing an arc with a Paint object configured to draw a <a href="https://developer.android.com/reference/android/graphics/Paint#setShadowLayer(float,%20float,%20float,%20int)">shadow layer</a> below the arc. We’ve also added the following attributes on the custom view:</p><ul><li>inset defines the dimension by which the progress ring is inset inside the view bounds to leave space for the glow effect.</li><li>glowColor is the color used to draw the glow effect.</li><li>glowPeak is the ratio beyond maxProgress where the glow effect reaches its peak.</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/99d3f188accab97afa339311d5699198/href">https://medium.com/media/99d3f188accab97afa339311d5699198/href</a></iframe><p>And that is what it looks like in the daily goal widget:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*BS1_60cJi43iypCUoF15hw.png" /><figcaption>The ✨ glow ✨</figcaption></figure><h3>Animating the ring and putting it all together</h3><p>Lastly, we added a setProgressAnimated() method on the custom view that we use to animate the progress ring from zero to its current value. This uses a <a href="https://developer.android.com/reference/android/animation/ValueAnimator">ValueAnimator</a> that updates the progress value from zero to the desired value. The duration of the animation is adjusted so that the progress ring grows approximately at the same speed across the progress value spectrum.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/dc8fe9f60522c20962c2b9d4f414ba2d/href">https://medium.com/media/dc8fe9f60522c20962c2b9d4f414ba2d/href</a></iframe><p>This is how the progress ring is animated in the popup panel:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*5k8daZ0waBmrdZ_F7jtecQ.gif" /></figure><p>And that is how it is animated in the daily goal widget:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*MN07dVh2FgpKHajsEEr8uQ.gif" /></figure><p>Here’s the same animation in slow-motion:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*NRt2uHzDNomNanEvRtzSEA.gif" /></figure><p>Curious about what it looks like in real life? Go ahead and install <a href="http://play.google.com/store/apps/details?id=com.glose.android">Glose for Android</a>, and let us know what you think!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=865eb0161cc1" width="1" height="1" alt=""><hr><p><a href="https://medium.com/glose-team/a-glowing-progress-ring-with-rounded-ends-for-android-865eb0161cc1">A glowing progress ring with rounded ends for Android</a> was originally published in <a href="https://medium.com/glose-team">Glose Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>