We have changed how we store reblogs in the redis for bigint IDs. This process is done by 1) scan all entries in users feed, and 2) re-store reblogs by 3 write commands.

However, this operation is really slow for large instances. e.g. 1hrs on friends.nico (w/ 50k users). So I have tried below tweaks.

* It checked non-reblogs by `entry[0] == entry[1]`, but this condition won't work because `entry[0]` is String while `entry[1]` is Float. Changing `entry[0].to_i == entry[1]` seems work.
  -> about 4-20x faster (feed with less reblogs will be faster)
* Write operations can be batched by pipeline
  -> about 6x faster
* Wrap operation by Lua script and execute by EVALSHA command. This really reduces packets between Ruby and Redis.
  -> about 3x faster

I've taken Lua script way, though doing other optimizations may be enough.

Reported at
https://don.inux39.me/@inux39/1406082
https://don.inux39.me/@inux39/1406134

* Add foreign key constraint to column `account` in `account_moderation_notes`

* Change account_id and target_account_id to non-nullable in account_moderation_notes

* Add dependent: :destroy to account and target_account in account_moderation_notes

* Add moderation note

* Add frozen_string_literal

* Make rspec pass

* Encode custom emojis as resolveable objects in ActivityPub

* Improve code style

* Implement BlacklistedEmailDomain

* Use Faker::Internet.domain_name

* Remove note column

* Add frozen_string_literal comment

* Delete unnecessary codes

* Sort alphabetically

* Change of wording

* Rename BlacklistedEmailDomain to EmailDomainBlock

* Use non-serial IDs

This change makes a number of nontrivial tweaks to the data model in
Mastodon:

* All IDs are now 8 byte integers (rather than mixed 4- and 8-byte)
* IDs are now assigned as:
  * Top 6 bytes: millisecond-resolution time from epoch
  * Bottom 2 bytes: serial (within the millisecond) sequence number
  * See /lib/tasks/db.rake's `define_timestamp_id` for details, but
    note that the purpose of these changes is to make it difficult to
    determine the number of objects in a table from the ID of any
    object.
* The Redis sorted set used for the feed will have values used to look
  up toots, rather than scores. This is almost always the same as the
  existing behavior, except in the case of boosted toots. This change
  was made because Redis stores scores as double-precision floats,
  which cannot store the new ID format exactly. Note that this doesn't
  cause problems with sorting/pagination, because ZREVRANGEBYSCORE
  sorts lexicographically when scores are tied. (This will still cause
  sorting issues when the ID gains a new significant digit, but that's
  extraordinarily uncommon.)

Note a couple of tradeoffs have been made in this commit:

* lib/tasks/db.rake is used to enforce many/most column constraints,
  because this commit seems likely to take a while to bring upstream.
  Enforcing a post-migrate hook is an easier way to maintain the code
  in the interim.
* Boosted toots will appear in the timeline as many times as they have
  been boosted. This is a tradeoff due to the way the feed is saved in
  Redis at the moment, but will be handled by a future commit.

This would effectively close Mastodon's #1059, as it is a
snowflake-like system of generating IDs. However, given how involved
the changes were simply within Mastodon, it may have unexpected
interactions with some clients, if they store IDs as doubles
(or as 4-byte integers). This was a problem that Twitter ran into with
their "snowflake" transition, particularly in JavaScript clients that
treated IDs as JS integers, rather than strings. It therefore would be
useful to test these changes at least in the web interface and popular
clients before pushing them to all users.

* Fix JavaScript interface with long IDs

Somewhat predictably, the JS interface handled IDs as numbers, which in
JS are IEEE double-precision floats. This loses some precision when
working with numbers as large as those generated by the new ID scheme,
so we instead handle them here as strings. This is relatively simple,
and doesn't appear to have caused any problems, but should definitely
be tested more thoroughly than the built-in tests. Several days of use
appear to support this working properly.

BREAKING CHANGE:

The major(!) change here is that IDs are now returned as strings by the
REST endpoints, rather than as integers. In practice, relatively few
changes were required to make the existing JS UI work with this change,
but it will likely hit API clients pretty hard: it's an entirely
different type to consume. (The one API client I tested, Tusky, handles
this with no problems, however.)

Twitter ran into this issue when introducing Snowflake IDs, and decided
to instead introduce an `id_str` field in JSON responses. I have opted
to *not* do that, and instead force all IDs to 64-bit integers
represented by strings in one go. (I believe Twitter exacerbated their
problem by rolling out the changes three times: once for statuses, once
for DMs, and once for user IDs, as well as by leaving an integer ID
value in JSON. As they said, "If you’re using the `id` field with JSON
in a Javascript-related language, there is a very high likelihood that
the integers will be silently munged by Javascript interpreters. In most
cases, this will result in behavior such as being unable to load or
delete a specific direct message, because the ID you're sending to the
API is different than the actual identifier associated with the
message." [1]) However, given that this is a significant change for API
users, alternatives or a transition time may be appropriate.

1: https://blog.twitter.com/developer/en_us/a/2011/direct-messages-going-snowflake-on-sep-30-2011.html

* Restructure feed pushes/unpushes

This was necessary because the previous behavior used Redis zset scores
to identify statuses, but those are IEEE double-precision floats, so we
can't actually use them to identify all 64-bit IDs. However, it leaves
the code in a much better state for refactoring reblog handling /
coalescing.

Feed-management code has been consolidated in FeedManager, including:

* BatchedRemoveStatusService no longer directly manipulates feed zsets
* RemoveStatusService no longer directly manipulates feed zsets
* PrecomputeFeedService has moved its logic to FeedManager#populate_feed

(PrecomputeFeedService largely made lots of calls to FeedManager, but
didn't follow the normal adding-to-feed process.)

This has the effect of unifying all of the feed push/unpush logic in
FeedManager, making it much more tractable to update it in the future.

Due to some additional checks that must be made during, for example,
batch status removals, some Redis pipelining has been removed. It does
not appear that this should cause significantly increased load, but if
necessary, some optimizations are possible in batch cases. These were
omitted in the pursuit of simplicity, but a batch_push and batch_unpush
would be possible in the future.

Tests were added to verify that pushes happen under expected conditions,
and to verify reblog behavior (both on pushing and unpushing). In the
case of unpushing, this includes testing behavior that currently leads
to confusion such as Mastodon's #2817, but this codifies that the
behavior is currently expected.

* Rubocop fixes

I could swear I made these changes already, but I must have lost them
somewhere along the line.

* Address review comments

This addresses the first two comments from review of this feature:

https://github.com/tootsuite/mastodon/pull/4801#discussion_r139336735
https://github.com/tootsuite/mastodon/pull/4801#discussion_r139336931

This adds an optional argument to FeedManager#key, the subtype of feed
key to generate. It also tests to ensure that FeedManager's settings are
such that reblogs won't be tracked forever.

* Hardcode IdToBigints migration columns

This addresses a comment during review:
https://github.com/tootsuite/mastodon/pull/4801#discussion_r139337452

This means we'll need to make sure that all _id columns going forward
are bigints, but that should happen automatically in most cases.

* Additional fixes for stringified IDs in JSON

These should be the last two. These were identified using eslint to try
to identify any plain casts to JavaScript numbers. (Some such casts are
legitimate, but these were not.)

Adding the following to .eslintrc.yml will identify casts to numbers:

~~~
  no-restricted-syntax:
  - warn
  - selector: UnaryExpression[operator='+'] > :not(Literal)
    message: Avoid the use of unary +
  - selector: CallExpression[callee.name='Number']
    message: Casting with Number() may coerce string IDs to numbers
~~~

The remaining three casts appear legitimate: two casts to array indices,
one in a server to turn an environment variable into a number.

* Only implement timestamp IDs for Status IDs

Per discussion in #4801, this is only being merged in for Status IDs at
this point. We do this in a migration, as there is no longer use for
a post-migration hook. We keep the initialization of the timestamp_id
function as a Rake task, as it is also needed after db:schema:load (as
db/schema.rb doesn't store Postgres functions).

* Change internal streaming payloads to stringified IDs as well

This is equivalent to 591a9af356faf2d5c7e66e3ec715502796c875cd from
#5019, with an extra change for the addition to FeedManager#unpush.

* Ensure we have a status_id_seq sequence

Apparently this is not a given when specifying a custom ID function,
so now we ensure it gets created. This uses the generic version of this
function to more easily support adding additional tables with timestamp
IDs in the future, although it would be possible to cut this down to a
less generic version if necessary. It is only run during db:schema:load
or the relevant migration, so the overhead is extraordinarily minimal.

* Transition reblogs to new Redis format

This provides a one-way migration to transition old Redis reblog entries
into the new format, with a separate tracking entry for reblogs.

It is not invertible because doing so could (if timestamp IDs are used)
require a database query for each status in each users' feed, which is
likely to be a significant toll on major instances.

* Address review comments from @akihikodaki

No functional changes.

* Additional review changes

* Heredoc cleanup

* Run db:schema:load hooks for test in development

This matches the behavior in Rails'
ActiveRecord::Tasks::DatabaseTasks.each_current_configuration, which
would otherwise break `rake db:setup` in development.

It also moves some functionality out to a library, which will be a good
place to put additional related functionality in the near future.

* Make IdsToBigints (mostly!) non-blocking

This pulls in GitLab's MigrationHelpers, which include code to make
column changes in ways that Postgres can do without locking. In general,
this involves creating a new column, adding an index and any foreign
keys as appropriate, adding a trigger to keep it populated alongside
the old column, and then progressively copying data over to the new
column, before removing the old column and replacing it with the new
one.

A few changes to GitLab's MigrationHelpers were necessary:

* Some changes were made to remove dependencies on other GitLab code.
* We explicitly wait for index creation before forging ahead on column
  replacements.
* We use different temporary column names, to avoid running into index
  name length limits.
* We rename the generated indices back to what they "should" be after
  replacing columns.
* We rename the generated foreign keys to use the new column names when
  we had to create them. (This allows the migration to be rolled back
  without incident.)

# Big Scary Warning

There are two things here that may trip up large instances:

1. The change for tables' "id" columns is not concurrent. In
   particular, the stream_entries table may be big, and does not
   concurrently migrate its id column. (On the other hand, x_id type
   columns are all concurrent.)
2. This migration will take a long time to run, *but it should not
   lock tables during that time* (with the exception of the "id"
   columns as described above). That means this should probably be run
   in `screen` or some other session that can be run for a long time.
   Notably, the migration will take *longer* than it would without
   these changes, but the website will still be responsive during that
   time.

These changes were tested on a relatively large statuses table (256k
entries), and the service remained responsive during the migration.
Migrations both forward and backward were tested.

* Rubocop fixes

* MigrationHelpers: Support ID columns in some cases

This doesn't work in cases where the ID column is referred to as a
foreign key by another table.

* MigrationHelpers: support foreign keys for ID cols

Note that this does not yet support foreign keys on non-primary-key
columns, but Mastodon also doesn't yet have any that we've needed to
migrate.

This means we can perform fully "concurrent" migrations to change ID
column types, and the IdsToBigints migration can happen with effectively
no downtime. (A few operations require a transaction, such as renaming
columns or deleting them, but these transactions should not block for
noticeable amounts of time.)

The algorithm for generating foreign key names has changed with this,
and therefore all of those changed in schema.rb.

* Provide status, allow for interruptions

The MigrationHelpers now allow restarting the rename of a column if it
was interrupted, by removing the old "new column" and re-starting the
process.

Along with this, they now provide status updates on the changes which
are happening, as well as indications about when the changes can be
safely interrupted (when there are at least 10 seconds estimated to be
left before copying data is complete).

The IdsToBigints migration now also sorts the columns it migrates by
size, starting with the largest tables. This should provide
administrators a worst-case scenario estimate for the length of
migrations: each successive change will get faster, giving admins a
chance to abort early on if they need to run the migration later. The
idea is that this does not force them to try to time interruptions
between smaller migrations.

* Fix column sorting in IdsToBigints

Not a significant change, but it impacts the order of columns in the
database and db/schema.rb.

* Actually pause before IdsToBigints

* Fix #117 - Add ability to specify alternative text for media attachments

- POST /api/v1/media accepts `description` straight away
- PUT /api/v1/media/:id to update `description` (only for unattached ones)
- Serialized as `name` of Document object in ActivityPub
- Uploads form adjusted for better performance and description input

* Add tests

* Change undo button blend mode to difference

* Fix the migration error when deprecated_preview_cards has deleted

* Re-run Travis CI

This addresses a comment during review:
https://github.com/tootsuite/mastodon/pull/4801#discussion_r139337452

This means we'll need to make sure that all _id columns going forward
are bigints, but that should happen automatically in most cases.

* Custom emoji

- In OStatus: `<link rel="emoji" name="coolcat" href="http://..." />`
- In ActivityPub: `{ type: "Emoji", name: ":coolcat:", href: "http://..." }`
- In REST API: Status object includes `emojis` array (`shortcode`, `url`)
- Domain blocks with reject media stop emojis
- Emoji file up to 50KB
- Web UI handles custom emojis
- Static pages render custom emojis as `<img />` tags

Side effects:

- Undo #4500 optimization, as I needed to modify it to restore
  shortcode handling in emojify()
- Formatter#plaintext should now make sure stripped out line-breaks
  and paragraphs are replaced with newlines

* Fix emoji at the start not being converted

* Improve OpenGraph tags for about pages

* Add thumbnail admin setting

* Fix error

* Fix up

* Decouple Status#local? from uri being nil

* Replace on-the-fly URI generation with stored URIs

- Generate URI in after_save hook for local statuses
- Use static value in TagManager when available, fallback to tag format
- Make TagManager use ActivityPub::TagManager to understand new format
- Adjust tests

* Use other heuristic for locality of old statuses, do not perform long query

* Exclude tombstone stream entries from Atom feed

* Prevent nil statuses from landing in Pubsubhubbub::DistributionWorker

* Fix URI not being saved (#4818)

* Add more specs for Status

* Save generated uri immediately

and also fix method order to minimize diff.

* Fix alternate HTML URL in Atom

* Fix tests

* Remove not-null constraint from statuses migration to speed it up

* Make PreviewCard records reuseable between statuses

**Warning!** Migration truncates preview_cards tablec

* Allow a wider thumbnail for link preview, display it in horizontal layout (#4648)

* Delete preview cards files before truncating

* Rename old table instead of truncating it

* Add mastodon:maintenance:remove_deprecated_preview_cards

* Ignore deprecated_preview_cards in schema definition

* Fix null behaviour

We only look up status_pins by account_id, or account_id and status_id,
never by status_id

* Allow multiple pinned statuses to be shown and make them be ordered by pinned date

* Set timestamps NOT NULL

* Make single-line pinned_statuses

* Spec for pinned_statuses

* Remove redundant empty line

* Pinned statuses

* yarn manage:translations

* Add code for creating/managing apps to settings section

* Add specs for app changes

* Fix controller spec

* Fix view file I pasted over by mistake

* Add locale strings. Add 'my apps' to nav

* Add Client ID/Secret to App page. Add some visual separation

* Fix rubocop warnings

* Fix embarrassing typo

I lost an `end` statement while fixing a merge conflict.

* Add code for creating/managing apps to settings section

- Add specs for app changes
- Add locale strings. Add 'my apps' to nav
- Add Client ID/Secret to App page. Add some visual separation
- Fix some bugs/warnings

* Update to match code standards

* Trigger notification

* Add warning about not sharing API secrets

* Tweak spec a bit

* Cleanup fixture creation by using let!

* Remove unused key

* Add foreign key for application<->user

* Fix #2672 - Connect signed PuSH subscription requests to instance domain

Resolves #2739

* Fix return of locate_subscription

* Fix tests

* feat: Register push subscription

* feat: Notify when mentioned

* feat: Boost, favourite, reply, follow, follow request

* feat: Notification interaction

* feat: Handle change of public key

* feat: Unsubscribe if things go wrong

* feat: Do not send normal notifications if push is enabled

* feat: Focus client if open

* refactor: Move push logic to WebPushSubscription

* feat: Better title and body

* feat: Localize messages

* chore: Fix lint errors

* feat: Settings

* refactor: Lazy load

* fix: Check if push settings exist

* feat: Device-based preferences

* refactor: Simplify logic

* refactor: Pull request feedback

* refactor: Pull request feedback

* refactor: Create /api/web/push_subscriptions endpoint

* feat: Spec PushSubscriptionController

* refactor: WebPushSubscription => Web::PushSubscription

* feat: Spec Web::PushSubscription

* feat: Display first media attachment

* feat: Support direction

* fix: Stuff broken while rebasing

* refactor: Integration with session activations

* refactor: Cleanup

* refactor: Simplify implementation

* feat: Set VAPID keys via environment

* chore: Comments

* fix: Crash when no alerts

* fix: Set VAPID keys in testing environment

* fix: Follow link

* feat: Notification actions

* fix: Delete previous subscription

* chore: Temporary logs

* refactor: Move migration to a later date

* fix: Fetch the correct session activation and misc bugs

* refactor: Move migration to a later date

* fix: Remove follow request (no notifications)

* feat: Send administrator contact to push service

* feat: Set time-to-live

* fix: Do not show sensitive images

* fix: Reducer crash in error handling

* feat: Add badge

* chore: Fix lint error

* fix: Checkbox label overlap

* fix: Check for payload support

* fix: Rename action "type" (crash in latest Chrome)

* feat: Action to expand notification

* fix: Lint errors

* fix: Unescape notification body

* fix: Do not allow boosting if the status is hidden

* feat: Add VAPID keys to the production sample environment

* fix: Strip HTML tags from status

* refactor: Better error messages

* refactor: Handle browser not implementing the VAPID protocol (Samsung Internet)

* fix: Error when target_status is nil

* fix: Handle lack of image

* fix: Delete reference to invalid subscriptions

* feat: Better error handling

* fix: Unescape HTML characters after tags are striped

* refactor: Simpify code

* fix: Modify to work with #4091

* Sort strings alphabetically

* i18n: Updated Polish translation

it annoys me that it's not fully localized :P

* refactor: Use current_session in PushSubscriptionController

* fix: Rebase mistake

* fix: Set cacheName to mastodon

* refactor: Pull request feedback

* refactor: Remove logging statements

* chore(yarn): Fix conflicts with master

* chore(yarn): Copy latest from master

* chore(yarn): Readd offline-plugin

* refactor: Use save! and update!

* refactor: Send notifications async

* fix: Allow retry when push fails

* fix: Save track for failed pushes

* fix: Minify sw.js

* fix: Remove account_id from fabricator

* Fix boolean columns sometimes having a null value

* Fix wrong value being set instead of null

* Add overview of active sessions

* Better display of browser/platform name

* Improve how browser information is stored and displayed for sessions overview

* Fix test

* Fix #2347 - Bind web UI access token to session

When you logout, session also destroys the access token, so it's no longer
valid. If access token is destroyed some other way, the session is also
destroyed, requiring a re-login.

Fix #1681 - Add scheduler to remove revoked access tokens and grants

* Fix test

* Add overview of active sessions

* Better display of browser/platform name

* Improve how browser information is stored and displayed for sessions overview

* Fix test

* feat: Revocable sessions

* fix: Tests using sign_in

* feat: Configuration entry for the maximum number of session activations

* Default to nil for statuses.language

* Language detection defaults to nil instead of instance UI default

* Sort results by the name
* Switch search method to simple `LIKE` matching instead of tsvector/tsquery

Previously we used scores from ts_rank_cd() to sort results, but it didn't work
because the function returns same score for all results. It's not for calculate
similarity of single words. Sometimes this bug even push out exact matching tag
from results.

Additionally, PostgreSQL supports prefix searching with standard btree index.
Using it offers simpler code, but also less index size and some speed.

* Fix #3550 - Add all missing foreign keys

* Add missing foreign keys

Since Rails 5.1 missing migration version results in following error:

```
StandardError: Directly inheriting from ActiveRecord::Migration is not supported. Please specify the Rails release the migration was written for:
```

This PR fixes all migration files.

* Remove allowed_languages and add filtered_languages

* Use filtered_languages instead of allowed_languages

* Add <ostatus:conversation /> tag to Atom input/output

Only uses ref attribute (not href) because href would be
the alternate link that's always included also.

Creates new conversation for every non-reply status. Carries
over conversation for every reply. Keeps remote URIs verbatim,
generates local URIs on the fly like the rest of them.

* Conversation muting - prevents notifications that reference a conversation
(including replies, favourites, reblogs) from being created. API endpoints
/api/v1/statuses/:id/mute and /api/v1/statuses/:id/unmute

Currently no way to tell when a status/conversation is muted, so the web UI
only has a "disable notifications" button, doesn't work as a toggle

* Display "Dismiss notifications" on all statuses in notifications column, not just own

* Add "muted" as a boolean attribute on statuses JSON

For now always false on contained reblogs, since it's only relevant for
statuses returned from the notifications endpoint, which are not nested

Remove "Disable notifications" from detailed status view, since it's
only relevant in the notifications column

* Up max class length

* Remove pending test for conversation mute

* Add tests, clean up

* Rename to "mute conversation" and "unmute conversation"

* Raise validation error when trying to mute/unmute status without conversation

* Adding account domain blocks that filter notifications and public timelines

* Add tests for domain blocks in notifications, public timelines
Filter reblogs of blocked domains from home

* Add API for listing and creating account domain blocks

* API for creating/deleting domain blocks, tests for Status#ancestors
and Status#descendants, filter domain blocks from them

* Filter domains in streaming API

* Update account_domain_block_spec.rb